leetcode_contest_195

1496. 判断路径是否相交

思路：
按照题目意思模拟即可。

class Solution:
    def isPathCrossing(self, path: str) -> bool:
        path_set = set([(0,0)])
        pre = (0,0)
        for p in path:
            x, y = pre
            if p == 'N':
                y += 1
            elif p == 'S':
                y -= 1
            elif p == 'E':
                x += 1
            elif p == 'W':
                x -= 1
            # print(x,y)
            if (x,y) in path_set:
                return True
            path_set.add((x,y))
            pre = (x,y)
        return False

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

思路：
使用一个长度为k的数组存储不同取模后余数的个数，如果恰好满足条件，

1. 余数为i和余数为k-i的个数应该正好相等，0<i<k
2. 余数为0的数字个数为偶数才能凑对。

class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        num_map = [0] * k
        for i in range(len(arr)):
            arr[i] = (arr[i] % k + k) % k
            num_map[arr[i]] += 1
        # print(num_map)
        if num_map[0] % 2:
            return False
        for i in range(1, k // 2+1):
            if num_map[i] != num_map[k-i]:
                return False
        return True

1498. 满足条件的子序列数目

思路：
子序列最值与顺序无关，首先对数组排序，然后使用双指针寻找满足条件长度为n的区间[min,num1,num2,…,max]，满足条件的非空子序列为$[min],[min,num1],[min,num1,num2],[min,num2]…[min,max]$，从$num1$到$max$一共n-1个数字中至少选择一个，一共有$2^{n-1}-1$个，加上[min]一共有$2^{n-1}$中情况。剩下的工作就是寻找满足条件的区间即可，使用双指针，指针两数之和小于等于target，左端点往后，否则右端点往前。

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

1499. 满足不等式的最大值

思路：
由于题目中$x_i$严格单调递增，对于$j>i$，条件$y_i+y_j+|x_i-x_j|$可转化为$x_j+y_j+y_i-x_i$，因此对于任一点，取满足k范围中 $y_i-x_i$最大之即可。因此可使用单调队列实现。

class Solution:
    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:
        q = collections.deque()
        q.append((points[0], points[0][1] - points[0][0]))
        res = -1e9
        for point in points[1:]:
            # 不在区间范围内的点从队列中删除
            while len(q) and point[0] - q[0][0][0] > k:
                q.popleft()
            # 根绝当前点数据更新结果 
            if len(q):
                res = max(res, q[0][1]+ point[1]+point[0])
            # 将当前点加入单调队列中，需根据 yi-xi 满足单调性
            while len(q) and q[-1][1] < point[1] - point[0]:
                q.pop()
            q.append((point, point[1] - point[0]))
        return res