目录

判断路径是否相交

给你一个字符串 path，其中 path[i] 的值可以是 ‘N’、‘S’、‘E’ 或者 ‘W’，分别表示向北、向南、向东、向西移动一个单位。
机器人从二维平面上的原点 (0, 0) 处开始出发，按 path 所指示的路径行走。
如果路径在任何位置上出现相交的情况，也就是走到之前已经走过的位置，请返回 True ；否则，返回 False 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-crossing

示例

输入：path = “NES”
输出：false
解释：该路径没有在任何位置相交。

思路1

用哈希表存储每个字符代表的位移，用集合存储访问过的坐标。
遍历path，每一步更新一次坐标，如果在集合内则返回True，否则将新的坐标添加进集合内。走完path还未返回True则返回False。时间复杂度O(n)

代码1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def isPathCrossing(self, path: str) -> bool:
        m = {"N":[0,1],"S":[0,-1],"E":[1,0],"W":[-1,0]}
        start = (0,0)
        tmp = {start}
        x = start[0]
        y = start[1]
        for p in path:
            x += m[p][0]
            y += m[p][1]
            if (x,y) in tmp:
                return True
            tmp.add((x,y))
        return False

检查数组对是否可以被k整除

给你一个整数数组 arr 和一个整数 k ，其中数组长度是偶数，值为 n 。
现在需要把数组恰好分成 n / 2 对，以使每对数字的和都能够被 k 整除。
如果存在这样的分法，请返回 True ；否则，返回 False 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/check-if-array-pairs-are-divisible-by-k

示例

输入：arr = [1,2,3,4,5,10,6,7,8,9], k = 5
输出：true
解释：划分后的数字对为 (1,9),(2,8),(3,7),(4,6) 以及 (5,10) 。

思路1

存在数字对的前提是整个数组的和都能被k整除。因为比赛时用例很弱，仅凭该条件也可AC。此思路没有任何技术意义，只做记录。

代码1

1
2
3

class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        return sum(arr) / k == sum(arr) // k

思路2

记录数组中每个数模k的余数，并统计获得这些余数的数的个数。只有余数为i和余数为k-i的数的个数相同时才能凑成被k整除的数字对，最后还要检查能被k整除的数的个数是否有偶数个，从而凑成数字对。

代码2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        mod = [0] * k
        for num in arr:
            # mod[(num % k + k) % k] += 1 # Cpp和Java中对负数取模的处理
            mod[num % k] += 1
        for i in range(1, k):
            if mod[i] != mod[k-i]:
                return False
        return mod[0] % 2 == 0

满足条件的子序列数目

给你一个整数数组 nums 和一个整数 target 。
请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。
由于答案可能很大，请将结果对 10^9 + 7 取余后返回。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition

示例

输入：nums = [3,5,6,7], target = 9
输出：4
解释：有 4 个子序列满足该条件。
[3] -> 最小元素 + 最大元素 <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

思路1

参考自：https://leetcode-cn.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/solution/python-pai-xu-shuang-zhi-zhen-by-irruma/

先对数组排序，然后用双指针指向数组头尾。
都双指针范围内的数的最大最小值满足条件时，则双指针范围内包含最小值的子集都可以满足条件，故求该范围内包含最小值的子集个数即可。
首先需要知道一个包含n个数的子集个数为2^n（包括空集）。设双指针范围内的数的个数为n,去掉最小值后的n-1个数的子集个数为2^(n-1)。故每个满足条件的双指针范围[left, right]中满足条件的子集个数为2^((right-left+1)-1)。
当双指针范围满足条件时，应增大最小值继续查询，此时左指针往右移；不满足条件时，说明最大值过大，此时右指针往左移。

代码1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        if nums[0] * 2 > target:
            return 0
        left, right = 0, len(nums) - 1
        res = 0
        mod = 10**9 + 7
        while left <= right:
            if nums[left] + nums[right] <= target:
                res += 2**(right - left)
                left += 1
            else:
                right -= 1
        return res % mod

满足不等式的最大值

给你一个数组 points 和一个整数 k 。数组中每个元素都表示二维平面上的点的坐标，并按照横坐标 x 的值从小到大排序。也就是说 points[i] = [xi, yi] ，并且在 1 <= i < j <= points.length 的前提下， xi < xj 总成立。

请你找出 yi + yj + |xi - xj| 的 最大值，其中 |xi - xj| <= k 且 1 <= i < j <= points.length。

题目测试数据保证至少存在一对能够满足 |xi - xj| <= k 的点。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/max-value-of-equation

示例

输入：points = [[1,3],[2,0],[5,10],[6,-10]], k = 1
输出：4
解释：前两个点满足 |xi - xj| <= 1 ，带入方程计算，则得到值 3 + 0 + |1 - 2| = 4 。第三个和第四个点也满足条件，得到值 10 + -10 + |5 - 6| = 1 。
没有其他满足条件的点，所以返回 4 和 1 中最大的那个。

思路1

参考自：https://leetcode-cn.com/problems/max-value-of-equation/solution/dan-diao-dui-lie-by-acw_wangdh15/

首先将yi+yj+abs(xi-xj)转换为(yj-xj)+(xi+yi)，即在满足xi-xj <= k的情况下找最大的yj-xj。

用双端队列实现一个单调栈，第一个while循环队首保留满足xi-xj <= k最远的点(xi, yi)，并用此点更新res；第二个while循环时典型的单调栈操作，保证新入栈的点的yi-xi值最大。

代码1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import collections

class Solution:
    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:
        dq = collections.deque()
        dq.append([points[0][0], points[0][1] - points[0][0]])
        res = float("-inf")
        for i in range(1, len(points)):
            while dq and points[i][0] - dq[0][0] > k:
                dq.popleft()
            if dq:
                res = max(res, dq[0][1] + points[i][0] + points[i][1])
            while dq and dq[-1][1] <= points[i][1] - points[i][0]:
                dq.pop()
            dq.append([points[i][0], points[i][1] - points[i][0])
        return res

总结

AC前两题。
因为全球Leetcode服务器宕机，提交被耽误了，同时大概很多参赛者都因此放弃了比赛，故只AC两题也获得了不错的成绩。
得分7/20，完成时间0:39:24，全国排名 449/3399，全球排名 844/11467。
1、08:00，二维坐标模拟题，用了哈希表+集合，应该达到了最优解。
2、39:24，早早写了前提条件，但迟迟没有进一步的思路，因为用例很弱，直接提交前提条件居然通过了。这题主要是利用余数的数学性质。
3、排序+双指针；比赛时以为子序列顺序应与原数组顺序一致，于是用两个单调栈+双指针，做不出来。
4、用数学转换问题，用双端队列实现单调栈解决问题。比赛时用暴力模拟过程，超时。
目前全国排名2567，全球排名12510。