LeetCode算法题整理（数组篇）Array

Posted on | In | | Visitors

26. Remove Duplicates from Sorted Array

删除排序数组中重复的元素, 在原数组上操作，返回一个长度，标识前n个元素为目标数组。原题

1
2
3
4
5
Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.
1
2
3
4
5
6
7
8
9
def remove_duplicates(nums):
    if not nums:
        return 0
    index = 1
    for i in range(len(nums)-1):
        if nums[i] != nums[i+1]:
            nums[index] = nums[i+1]
            index += 1
    return index

80. Remove Duplicates from Sorted Array II

和上题一样，但是可以允许重复两次。原题

方法一：双指针调了半天。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def removeDuplicates(self, nums: List[int]) -> int:
    left = right = cnt = 0
    last_left = None
    n = len(nums)
    while right < n:
        while right<n and nums[right]==last_left and cnt:
            right += 1
        if right >= n: break
        nums[left] = nums[right]
        cnt = last_left==nums[left]
        last_left = nums[left]
        left += 1
        right += 1
    return left
方法二：stefan的方法原来这么简单。i作为待插入的索引位置，用n和他前两位比较，如果一样的话，保持插入位置不动，而nums[i-2]是不变的，一直可以用来作比较。 
1
2
3
4
5
6
7
def removeDuplicates(self, nums: List[int]) -> int:
    i = 0
    for n in nums:
        if i<2 or n>nums[i-2]:
            nums[i] = n
            i += 1
    return i

66. Plus One

给数组加一，元素为非负整数，不以0开头，每个元素只有一个数字。原题

1
2
3
Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
方法一：转成字符串再转成数字 
1
2
3
def plusOne(self, digits: 'List[int]') -> 'List[int]':
    num = int(''.join(map(str, digits)))
    return [int(d) for d in str(num + 1)]

方法二：Math 进位

1
2
3
4
5
6
7
8
9
10
11
12
def plus_one(digits):
    d = digits[:]  
    plused = []
    carry = 1
    while d or carry:
        if d:
            v = d.pop()
        else:
            v = 0
        carry, val = divmod(carry+v, 10)
        plused.append(val)
    return plused[::-1]
方法三：数组进位。 
1
2
3
4
5
6
7
8
9
def plusOne(self, digits: 'List[int]') -> 'List[int]':
    d = digits[:]
    d[-1] += 1
    for i in range(len(d)-1, -1, -1):
        carry, d[i] = divmod(d[i], 10)
        if i: d[i-1] += carry
    if carry:
        d.insert(0, carry)
    return d

989. Add to Array-Form of Integer

和66题很相似。不同的是这个K会大于10，以至于余数也会大于10。原题

1
2
3
Input: A = [2,7,4], K = 181
Output: [4,5,5]
Explanation: 274 + 181 = 455

方法一：竞赛写法。

1
2
3
def addToArrayForm(self, A: 'List[int]', K: 'int') -> 'List[int]':
    a = int(''.join(map(str, A)))
    return [int(c) for c in str(a + K)]

方法二：原理实现。

1
2
3
4
5
6
7
8
def addToArrayForm(self, A: 'List[int]', K: 'int') -> 'List[int]':
    A[-1] += K
    for i in range(len(A)-1, -1, -1):
        carry, A[i] = divmod(A[i], 10) 
        if i: A[i-1] += carry
    if carry:
        A = list(map(int, str(carry))) + A
    return A

88. Merge Sorted Array

合并两个有序数组，在nums1上修改。原题

1
2
3
4
5
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]
1
2
3
4
5
6
7
8
9
10
def merge(self, nums1, m, nums2, n):
    while m>0 and n>0:
        if nums1[m-1] > nums2[n-1]:
            nums1[n+m-1] = nums1[m-1]
            m -= 1
        else:
            nums1[n+m-1] = nums2[n-1]
            n -= 1
    if n > 0:
        nums1[:n] = nums2[:n]

118. Pascal’s Triangle

杨辉三角。原题

1
2
3
4
5
6
7
8
9
Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]
方法一: 错位相加。这里也可以使用zip，值得注意的是，res需要➕一个二维数组，而不是一维。结尾的切片是为了0的情况。 
1
2
3
4
5
6
def generate(self, numRows: 'int') -> 'List[List[int]]':
    ans = [[1]]
    for _ in range(numRows-1):
        ans += [[a+b for a, b in zip([0]+ans[-1], ans[-1]+[0])]]
        # ans.append(list(map(lambda x, y: x + y, [0]+ans[-1], ans[-1]+[0])))
    return ans[:numRows]

方法二

1
2
3
4
5
6
7
8
9
def generate(num):
    triangle = []
    inner = [1]
    for _ in range(num):
        triangle.append(list(inner))
        inner.append(0)
        right = [inner[i]+inner[i+1] for i in range(len(inner)-1)]
        inner = [1] + right
    return triangle

119.Pascal’s Triangle II

杨辉三角，只打印一层。原题

1
2
3
4
5
def getRow(self, rowIndex: 'int') -> 'List[int]':
    ans = [1]
    for _ in range(rowIndex):
        ans = [a+b for a, b in zip([0]+ans, ans+[0])]
    return ans

169. Majority Element

找出数组中出现次数超过一半的元素。原题

方法一：排序. Time-O(nlogn), Space-O(n)

1
2
def majority_element(nums):
    return sorted(nums)[len(nums)//2]

方法二：Counter Time-O(n), Space-O(n)

1
2
3
4
5
def majority_element(nums):
    from collections import Counter
    c = Counter(nums)
    # return max(c.keys(), key=c.get)
    return c.most_common(1)[0][0]
方法三：Boyer-Moore Voting Algorithm. 书中的算法说的就是这个，这里附上自己的见解。 波义尔摩尔投票算法 
1
2
3
4
5
6
7
8
def majorityElement(self, nums):
    count = 0
    candidate = None
    for num in nums:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)
    return candidate

229. Majority Element II

找到数组中出现超过n/3次的元素。原题

1
2
Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

方法一：波义尔摩尔投票法同样可用，但是我一开始想一次遍历求，发现好像不可以，最后都要遍历一次判断是否满足条件。循环中是elif，两个候选人开始设为不同的值以用来区分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def majorityElement(self, nums: List[int]) -> List[int]:
    count1, count2, candidate1, candidate2 = 0, 0, 0, 1
    for n in nums:
        if n == candidate1:
            count1 += 1
        elif n == candidate2:
            count2 += 1
        elif count1 == 0:
            candidate1, count1 = n, 1
        elif count2 == 0:
            candidate2, count2 = n, 1
        else:
            count1, count2 = count1 - 1, count2 - 1
    return [n for n in (candidate1, candidate2)
            if nums.count(n) > len(nums) // 3]

方法二：Counter. by Stefan.

1
2
3
4
5
6
7
def majorityElement(self, nums: List[int]) -> List[int]:
    ctr = Counter()
    for n in nums:
        ctr[n] += 1
        if len(ctr)==3:
            ctr -= Counter(set(ctr))  # 均-1
    return [n for n in ctr if nums.count(n) > len(nums)//3]

189. Rotate Array

旋转数组。进阶：使用O(1)空间实现。原题

1
2
3
4
5
6
Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
方法一：slicing。使用生成器而不是单纯的切片可以使复杂度降到常数。这里也是抱着试试看的态度，发现可以直接将chain的生成器对象赋值给nums。 
1
2
3
4
def rotate(self, nums: List[int], k: int) -> None:
    n = len(nums)
    k = k % n
    nums[:] = chain(islice(nums, n-k, n), islice(nums, n-k))

方法二：reverse的方法很新颖，不过要遍历两次数组。

1
2
3
4
5
6
7
8
9
10
11
12
def rotate(self, nums: List[int], k: int) -> None:
    def reverse(ary, lo, hi):
        while lo < hi: 
            ary[lo], ary[hi] = ary[hi], ary[lo]
            lo += 1
            hi -= 1

    N = len(nums)
    k = k % N
    reverse(nums, 0, N-1)
    reverse(nums, 0, k-1)
    reverse(nums, k, N-1)
方法三: 想这种要求常数空间复杂度的并且允许修改原数组的，可以使用这种思想，把每个数放到应该放到的位置。 
1
2
3
4
5
6
7
8
9
10
11
12
13
def rotate(self, nums: List[int], k: int) -> None:
    N = len(nums)
    k %= N

    start = count = 0
    while count < N:
        cur, prev = start, nums[start]
        while True:
            cur = (cur + k) % N
            nums[cur], prev = prev, nums[cur]
            count += 1
            if cur == start: break
        start += 1

217. Contains Duplicate

数组中是否包含重复元素。原题

1
2
Input: [1,2,3,1]
Output: true

方法一：set

1
2
def contains_duplicate(nums):
    return len(set(nums)) < len(nums)

方法二：hash

1
2
3
4
5
6
7
8
def containsDuplicate(self, nums: 'List[int]') -> 'bool':
    seen = set()
    for num in nums:
        if num in seen:
            return True
        else:
            seen.add(num)
    return False

219. Contains Duplicate II

数组中是否包含重复元素，且元素下标差小于等于k。原题

1
2
3
4
Input: nums = [1,2,3,1], k = 3
Output: true
Input: nums = [1,0,1,1], k = 1
Output: true

思路：开始想用set作切片来判断，同上题方法一，但是效率太低。故使用字典。

1
2
3
4
5
6
7
8
9
def containsNearbyDuplicate(self, nums, k):
    n = len(nums)
    seen = {}
    for i, num in enumerate(nums):
        if num in seen:
            if i-seen[num] <= k:
                return True
        seen[num] = i
    return False

220. Contains Duplicate III

是否存在索引差k范围内的绝对值不大于t的两个值。原题

1
2
3
4
Input: nums = [1,2,3,1], k = 3, t = 0
Output: true
Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

方法一：实际上是桶排序的原理，每个桶的size为t。两个差值为t的的数，只可能出现在同一个桶或者两边的桶中。每个桶只维护一个值就行了，因为如果有两个值，那么肯定就返回了。

1
2
3
4
5
6
7
8
9
10
11
12
13
def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
    if k < 1 or t < 0:
        return False
    dic = collections.OrderedDict()
    for n in nums:
        key = n if not t else n // t
        for m in (dic.get(key - 1), dic.get(key), dic.get(key + 1)):
            if m is not None and abs(n - m) <= t:
                return True
        if len(dic) == k:
            dic.popitem(False)
        dic[key] = n
    return False

283. Move Zeroes

将数组0元素移动到末尾，保证其他元素顺序。原题

1
2
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

方法一：two pointers

1
2
3
4
5
6
7
8
def move_zero(nums):
    l, r = 0, len(nums)-1
    while l < r:
        if nums[l] == 0:
            nums[:] = nums[:l] + nums[l+1:] + [0]
            r -= 1
        else:
            l += 1

方法二： slicing

1
2
def move_zero(nums):
    nums[:] = [x for x in nums if x != 0] + [x for x in nums if x == 0]
方法三：最后0的位置，感觉像冒泡。 
1
2
3
4
5
6
def moveZeroes(self, nums: 'List[int]') -> 'None':
    p = 0
    for i, num in enumerate(nums):
        if num != 0:
            nums[p], nums[i] = nums[i], nums[p]
            p += 1

方法四：排序。时间复杂度略高。

1
2
def moveZeroes(self, nums: 'List[int]') -> 'None':
    nums.sort(key=lambda x: 1 if x==0 else 0)

54. Spiral Matrix

螺旋矩阵，顺时针打印矩阵。原题

这里注意一点matrix.pop(0)需要转成list，因为zip函数中的每个元素是一个tuple，如果不转变成了一个tuple+list，会抛出异常。

ps: 此题解法为LeetCode一位大神，经常能看到此人的答案，不过这个是我认为最pythonic的一个，没有为了强行one-line而one-line。brilliant!

1
TypeError: can only concatenate tuple (not "list") to tuple
1
2
def spiralOrder(self, matrix):
    return matrix and list(matrix.pop(0))+self.spiralOrder(list(zip(*matrix))[::-1])

方法二：迭代写法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
    if not matrix: return []
    M, N = len(matrix), len(matrix[0])
    ans = []
    seen = [[False]*N for _ in range(M)]
    x, y, di, dj = 0, 0, 0, 1
    while len(ans) < M*N:
        seen[x][y] = True
        ans.append(matrix[x][y])        
        nx, ny = x+di, y+dj
        if not (0<=nx<M and 0<=ny<N and not seen[nx][ny]):
            di, dj = dj, -di
        x, y = x+di, y+dj
    return ans

此题有个变形，如果逆时针该如何打印。这样的话情况稍微复杂一些。

1
2
3
4
5
6
7
def anti_clock_wise(self, matrix)
    if not matrix:
        return []
    clock_wise = list(zip(*(matrix[::-1])))
    a = list(clock_wise.pop(0))[::-1]
    b = self.anti_clock_wise(clock_wise)
    return a + b

59. Spiral Matrix II

按照顺时针的顺序生成一个矩阵。原题

1
2
3
4
5
6
7
Input: 3
Output:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

方法一：自己的方法。使用了一个控制方向，如果超范围或者有值就换方向。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def generateMatrix(self, n: int) -> List[List[int]]:
    ans = [[0]*n for _ in range(n)]
    op = itertools.cycle([(0, 1), (1, 0), (0, -1), (-1, 0)])
    d = next(op)
    x, y = (0, 0)
    for k in range(1, n**2+1):
        ans[x][y] = k
        i, j = x+d[0], y+d[1]
        if not 0<=i<n or not 0<=j<n or ans[i][j]:
            d = next(op)
            x, y = x+d[0], y+d[1]
        else:
            x, y = i, j
    return ans

方法二：stefan的旋转法，我往这边想了，zip也想到了，没想到的是，从里往外遍历，还有一点是根据A的长度确定起始点。

1
2
3
||  =>  |9|  =>  |8|      |6 7|      |4 5|      |1 2 3|
                 |9|  =>  |9 8|  =>  |9 6|  =>  |8 9 4|
                                     |8 7|      |7 6 5|
1
2
3
4
5
6
def generateMatrix(self, n: int) -> List[List[int]]:
    A, lo = [], n**2+1
    while lo > 1:
        lo, hi = lo - len(A), lo
        A = [range(lo, hi)] + list(zip(*A[::-1]))
    return A

885. Spiral Matrix III

从二维数组中的某一个点开始顺时针旋转输出所有的坐标。原题

方法一：还是通过生成器控制方向，当处于水平位置时步数增加1。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def spiralMatrixIII(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:
    direction = itertools.cycle([(0, 1), (1, 0), (0, -1), (-1, 0)])
    ans = [(r0, c0)]
    step = 0
    while len(ans) < R*C:
        di, dj = next(direction)        
        if di==0:
            step += 1
        for _ in range(step):
            r0 += di
            c0 += dj
            if 0<=r0<R and 0<=c0<C:
                ans.append((r0, c0))
    return ans
方法二：Lee的方法。使用了di, dj = dj, -di刚好是这个右转的方向。然后用一个n来计算步数。 
1
2
3
4
5
6
7
8
9
10
def spiralMatrixIII(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:
    ans = []
    di, dj, step = 0, 1, 0
    while len(ans) < R*C:
        for s in range(step//2+1):
            if 0<=r0<R and 0<=c0<C:
                ans.append((r0, c0))
            r0, c0 = r0+di, c0+dj
        di, dj, step = dj, -di, step+1
    return ans

方法三：Lee的几何方法。根据到目标点的距离大小排序。

1
2
3
4
5
def spiralMatrixIII(self, R, C, r, c):
    def key((x, y)):
        x, y = x - r, y - c
        return (max(abs(x), abs(y)), -((math.atan2(-1, 1) - math.atan2(x, y)) % (math.pi * 2)))
    return sorted([(i, j) for i in xrange(R) for j in xrange(C)], key=key)

53. Maximum Subarray

连续子数组的最大和。原题

1
2
3
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

方法一：书中的思想。

1
2
3
4
5
6
def maxSubArray(self, nums):
    cp_nums = nums[:]
    for i in range(1, len(nums)):
        if cp_nums[i-1] > 0:
            cp_nums[i] += cp_nums[i-1]
    return max(cp_nums)
方法二：one-liner。注意accumulate是把函数放到后面的。 
1
2
3
def maxSubArray(self, nums):
    from itertools import accumulate
    return max(accumulate(nums, lambda x, y: x+y if x > 0 else y))

918. Maximum Sum Circular Subarray

连续数组的最大和，数组可以首位相连，但是最大长度不能超过一个数组。原题

1
2
3
Input: [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3

方法一：by @Lee215。看完这个解法豁然开朗，只需要同时找到一个累加和最小的子数组，再用总数减掉。

1
2
3
4
5
6
7
8
9
10
def maxSubarraySumCircular(self, A: List[int]) -> int:
    total = cur_max = cur_min = 0
    sum_max, sum_min = float('-inf'), float('inf')
    for a in A:
        cur_max = max(cur_max+a, a)
        sum_max = max(sum_max, cur_max)
        cur_min = min(cur_min+a, a)
        sum_min = min(sum_min, cur_min)
        total += a
    return max(sum_max, total-sum_min) if sum_max > 0 else sum_max

904. Fruit Into Baskets

实际上该题抽象为求最大滑动窗口的长度，滑动窗口不同元素最多不超过两个。原题

1
2
3
4
tree = [3,3,3,1,2,1,1,2,3,3,4]   # 5
tree = [1,0,1,4,1,4,1,2,3]  # 5
tree = [1,2,3,2,2]  # 4
tree = [0,1,6,6,4,4,6]  # 5

一开始没有找到滑动窗口的左边界，老是想直接删除一个key，后来看别人代码受到启发，可以用一个内循环来解决，可以逐个删除，然后判断是否为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
def totalFruit(self, tree):
    from collections import Counter
    basket = Counter()
    l, res = 0, 0
    for r in range(len(tree)):
        basket[tree[r]] += 1
        while len(basket) > 2:
            basket[tree[l]] -= 1
            if basket[tree[l]] == 0:
                basket.pop(tree[l])
            l += 1
        res = max(res, r-l+1)
    return res

27. Remove Element

从数组中删除元素，在原数组修改，要求返回一个长度。原题

1
2
Given nums = [0,1,2,2,3,0,4,2], val = 2,
Your function should return length = 5,

方法一：前后指针，r要从n开始，以n-1作比较，这里r不是从n-1开始是因为nums=[]的情况，否则l+1将超出数组范围。

1
2
3
4
5
6
7
8
9
def removeElement(self, nums, val):
    l, r = 0, len(nums)
    while l < r:
        if nums[l] == val:
            nums[l], nums[r-1] = nums[r-1], nums[l]
            r -= 1
        else:
            l += 1
    return l
方法二：快慢指针，几乎和283题中的方法一样。 
1
2
3
4
5
6
7
def removeElement(self, nums, val):
    i = 0
    for j in range(len(nums)):
        if nums[j] != val:
            nums[i] = nums[j]
            i += 1
    return i

349. Intersection of Two Arrays

求两个数组的交集。返回的数组必须元素唯一，可以无序。原题

思路：一开始看到这题以为是两个链表求相交点。最后发现Intersection不应该理解为“十字路口”而应该是“交集”。这里翻了一下discuss，大部分都是使用方法一，其它方法要么太繁琐，要么效率低。值得注意的是，此题的相关话题还有一项是Binary Search也就是说，可能会有一个较为高效的二分搜索法的实现方式。

1
2
3
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
方法一：最快的方法。 
1
2
def intersection(self, nums1, nums2):
    return list(set(nums1) & set(nums2))
方法二：Sort & Two Pointers. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def intersection(self, nums1: 'List[int]', nums2: 'List[int]') -> 'List[int]':
    nums1.sort()
    nums2.sort()
    i, n1 = 0, len(nums1)
    j, n2 = 0, len(nums2)
    ans, last = [], None
    while i < n1 and j < n2:
        if nums1[i] == nums2[j]:
            if nums1[i] != last:
                ans.append(nums1[i])
                last = nums1[i]
            i += 1
            j += 1
        elif nums1[i] > nums2[j]:
            j += 1
        elif nums1[i] < nums2[j]:
            i += 1
    return ans

350. Intersection of Two Arrays II

和上题不同的是要返回所有的交集元素。原题

1
2
3
4
Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
方法一：Counter实现了&操作可以直接取交集。 
1
2
3
4
def intersect(self, nums1, nums2):
    from collections import Counter
    a, b = map(Counter, (nums1, nums2))
    return list((a & b).elements())

方法二：不使用Counter。

1
2
3
4
5
6
7
8
9
10
11
def intersect(self, nums1, nums2):
    from collections import defaultdict
    counter = defaultdict(int)
    res = []
    for num1 in nums1:
        counter[num1] += 1
    for num2 in nums2:
        if counter[num2] != 0:
            res.append(num2)
            counter[num2] -= 1
    return res
方法三：可以采用上题349的方法，只需要去掉last即可。

905. Sort Array By Parity

将一个数组重新排列，是偶数在前奇数在后。原题

1
2
3
Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.
方法一：双指针。 
1
2
3
4
5
6
7
8
9
def sortArrayByParity(self, A):
    l, r = 0, len(A)-1
    while l < r:
        while l<r and A[l]&1==0:
            l += 1
        while l<r and A[r]&1==1:
            r -= 1
        A[l], A[r] = A[r], A[l]
    return A

方法二：列表生成式。

1
2
3
4
def sortArrayByParity(self, A):
    even = [num for num in A if num & 1 == 0]
    odd = [num for num in A if num & 1 == 1]
    return even + odd

922. Sort Array By Parity II

输入一个奇数偶数数量相同的数组，返回下标和其对应的值都是奇数或偶数，即奇偶交叉。和905相似。原题

方法一：使用切片的特性赋值。 
1
2
3
4
5
def sortArrayByParityII(self, A):
    res = [None] * len(A)
    res[::2] = (num for num in A if num & 1 == 0)
    res[1::2] = (num for num in A if num & 1 == 1)
    return res
方法二：双指针。 
1
2
3
4
5
6
7
8
def sortArrayByParityII(self, A: 'List[int]') -> 'List[int]':
    j = 1
    for i in range(0, len(A), 2):
        if A[i] & 1 == 1:
            while A[j] & 1 == 1:
                j += 2
            A[i], A[j] = A[j], A[i]
    return A

933. Number of Recent Calls

输入一个时间t，返回3000毫秒内所有的请求个数。原题

方法一：deque.

1
2
3
4
5
6
7
8
9
10
class RecentCounter:

    def __init__(self):
        self.q = collections.deque()

    def ping(self, t: 'int') -> 'int':
        self.q.append(t)
        while self.q[0] < t - 3000:
            self.q.popleft()
        return len(self.q)

937. Reorder Log Files

按照规则将log文件排序。原题

1
2
Input: ["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"]
Output: ["g1 act car","a8 act zoo","ab1 off key dog","a1 9 2 3 1","zo4 4 7"]

方法一：列表生成式。

1
2
3
4
5
def reorderLogFiles(self, logs):
    letter_logs = [l for l in logs if l.split()[1].isalpha()]
    digit_logs = [l for l in logs if not l.split()[1].isalpha()]
    letter_logs.sort(key=lambda x: x.split()[1:])
    return letter_logs + digit_logs
方法二：sort. 
1
2
3
4
5
def reorderLogFiles(self, logs: 'List[str]') -> 'List[str]':
    def f(log):
        pk, text = log.split(" ", 1)
        return (0, text) if text[0].isalpha() else (1, )
    return sorted(logs, key=f)

485. Max Consecutive Ones

输入一个二进制数组，返回最大的连续1的长度。原题

1
2
3
4
Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
    The maximum number of consecutive 1s is 3.
方法一：不使用标准库。末尾补0是因为，如果原数组末尾是1的情况下，还需要计算一次max的值。缺点是改变了原数组。也可以使用再计算一次的方式。 
1
2
3
4
5
6
7
8
9
def findMaxConsecutiveOnes(self, nums: 'List[int]') -> 'int':
    ans = count = 0
    for num in nums+[0]:
        if num == 1:
            count += 1
        else:
            ans = max(ans, count)
            count = 0
    return ans

方法二：使用groupby。

1
2
3
4
5
6
7
def findMaxConsecutiveOnes(self, nums):
    from itertools import groupby
    max_con = 0
    for d, group in groupby(nums):
        if d == 1:
            max_con = max(max_con, len(list(group)))
    return max_con

方法三：split。不过这个效率不高。

1
2
3
4
def findMaxConsecutiveOnes(self, nums):
    nums_str = ''.join(map(str, nums))
    ones = nums_str.split('0')
    return len(max(ones))
方法四：使用accumulate。Space-complex O(n)。 
1
2
3
def findMaxConsecutiveOnes(self, nums):
    from itertools import accumulate
    return max(accumulate(nums, lambda x, y: x+y if y==1 else y))
方法五：二进制的方法，将一个数不断左移并按位与，直到它为0，次数就是连续的1的个数。不过由于给的是数组不是数字，所以总体比方法四慢一丢丢。 
1
2
3
4
5
6
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
    ans, b = 0, int(''.join(map(str, nums)), 2)
    while b:
        b = b & (b<<1)
        ans += 1
    return ans

1004. Max Consecutive Ones III

与上题不同的是，有K次机会可以将0变成1. 原题

1
2
3
4
5
Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
Output: 10
Explanation: 
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.

方法一：这题竞赛时没想出来，受上题影响，思路跑到了groupby那里，想着怎么分组后操作。实际上此题完全不同，应该使用滑动窗口。

1
2
3
4
5
6
7
8
9
def longestOnes(self, A: List[int], K: int) -> int:
    ans = i = 0
    for j in range(len(A)):
        K -= A[j]==0
        while K < 0:
            K += A[i]==0
            i += 1
        ans = max(ans, j-i+1)
    return ans

496. Next Greater Element I

找出数组nums2中对应的nums1元素的位置之后的第一个比nums1大的元素。nums1是nums2的子集，二者均无重复的元素。原题

1
2
3
4
5
6
7
8
9
10
11
12
Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
    For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
    For number 1 in the first array, the next greater number for it in the second array is 3.
    For number 2 in the first array, there is no next greater number for it in the second array, so output -1.
    
Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
    For number 2 in the first array, the next greater number for it in the second array is 3.
    For number 4 in the first array, there is no next greater number for it in the second array, so output -1.

方法一：暴力法，因为题中给了范围数组长度小于1000，所以也没有超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def nextGreaterElement(self, nums1, nums2):
    res = []
    for num1 in nums1:
        index = nums2.index(num1)
        if not nums2[index+1:]:
            res.append(-1)
        else:
            for num2 in nums2[index+1:]:
                if num2 > num1:
                    res.append(num2)
                    break
            else:
                res.append(-1)
    return res

方法二：one-liner，生成器一开始想到了，没想到next函数还可以设默认值。

1
2
3
def nextGreaterElement(self, nums1, nums2):
    return [next((y for y in nums2[nums2.index(x):] if y > x), -1) 
            for x in nums1]
方法三：Time: O(n). 
1
2
3
4
5
6
7
def nextGreaterElement(self, nums1, nums2):
    st, d = [], {}
    for n in nums2:
        while st and st[-1] < n:
            d[st.pop()] = n
        st.append(n)
    return list(map(lambda x: d.get(x, -1), nums1))

953. Verifying an Alien Dictionary

判断一个字符串数组是否按照特定的字典顺序排序。原题

1
2
3
4
5
6
7
8
9
Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true
Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.
Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
Output: false
Explanation: As 'd' comes after 'l' in this language, then words[0] > words[1], hence the sequence is unsorted.
Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
Output: false
Explanation: The first three characters "app" match, and the second string is shorter (in size.) According to lexicographical rules "apple" > "app", because 'l' > '∅', where '∅' is defined as the blank character which is less than any other character (More info).
方法一：这道题想了很久，最后还是没有做出来，一开始想用zip来自己实现，也想到了sort，但是key里面的匿名函数一直没有想对，关键是二维数组也能排序这点没有想到。 
1
2
3
def isAlienSorted(self, words: 'List[str]', order: 'str') -> 'bool':
    d = dict(zip(order, range(26)))
    return words == sorted(words, key=lambda w: [d[c] for c in w])
方法二：传统方法，优点在于提前退出。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def isAlienSorted(self, words: 'List[str]', order: 'str') -> 'bool':
    d = dict(zip(order, range(26)))
    
    for i in range(len(words)-1):
        word1, word2 = words[i:i+2]

        for c1, c2 in zip(word1, word2):
            if c1 != c2:
                if d[c1] > d[c2]:
                    return False
                break
        else:
            if len(word1) > len(word2):
                return False
    return True

506. Relative Ranks

根据得分，返回排名。前三要用奖牌表示。原题

1
2
3
4
Input: [5, 4, 3, 2, 1]
Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
Explanation: The first three athletes got the top three highest scores, so they got "Gold Medal", "Silver Medal" and "Bronze Medal". 
For the left two athletes, you just need to output their relative ranks according to their scores.

方法一：先生成一个排行榜单，再根据每个得分把排序映射上去。

1
2
3
4
5
def findRelativeRanks(self, nums):
    ranks = list(map(str,range(1, len(nums)+1)))
    ranks[:3] = ["Gold Medal", "Silver Medal", "Bronze Medal"]
    sorted_nums = sorted(nums, reverse=True)
    return [ranks[sorted_nums.index(num)] for num in nums]  # slow
方法二：使用map映射。 
1
2
3
4
5
6
7
def findRelativeRanks(self, nums):
    ranks = list(map(str,range(1, len(nums)+1)))
    ranks[:3] = ["Gold Medal", "Silver Medal", "Bronze Medal"]
    sorted_nums = sorted(nums, reverse=True)
    # map_rank = {num: ranks[i] for i, num in enumerate(sorted_nums)}
    # return list(map(map_rank.get, nums))
    return list(map(dict(zip(sorted_nums, ranks)).get, nums))

532. K-diff Pairs in an Array

找出差为k的不重复的成对元素的个数。原题

1
2
3
4
Input: [3, 1, 4, 1, 5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

方法一：Counter，一开始没想到，想sort或是set，然后实现不了。

1
2
3
4
5
6
7
8
def findPairs(self, nums, k):
    from collections import Counter
    c = Counter(nums)
    res = 0
    for num, count in c.items():
        if (k == 0 and count > 1) or (k > 0 and num+k in c):
            res += 1
    return res

961. N-Repeated Element in Size 2N Array

找出2N长的数组中重复N次的数字，其它数字均只出现一次。此题不能用波义尔摩尔投票因为数量没有大于半数。原题

1
2
Input: [2,1,2,5,3,2]
Output: 2
方法一：这题本意我看是哈希表，所以大部分答案都是Counter之类的，我看排行榜签名的Python选手也是这么用的，我是灵机一动一动动想出了一个数学方法。看上去迭代了两次数组，并使用了一些空间，但其实速度很快。 
1
2
def repeatedNTimes(self, A):
    return (sum(A)-sum(set(A))) // (len(A)//2-1)
方法二：其实是找重复的数字，那么就数量是一定的话，其他数字的相邻两位中可能会有重复，其他一种不重复情况，2234和2342。此方法不能用于169题，因为169题中的其它元素是可能重复的。 
1
2
3
4
5
def repeatedNTimes(self, A: 'List[int]') -> 'int':
    for i in range(2, len(A)):
        if A[i] == A[i-1] or A[i] == A[i-2]:
            return A[i]
    return A[0]

967. Numbers With Same Consecutive Differences

根据规则生成一组数组，数字长度为N，每两位的差为K。原题

方法一：迭代生成，其实此题本是一道动态规划题，但由于解法不是，暂时归到数组里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def numsSameConsecDiff(self, N, K):
    ans = {x for x in range(1, 10)}
    for _ in range(N-1):
        ans2 = set()
        for digit in ans:
            d = digit % 10
            if d - K >= 0:
                ans2.add(digit*10 + d - K)
            if d + K <= 9:
                ans2.add(digit*10 + d + K)
        ans = ans2
    if N == 1:
        ans.add(0)
    return list(ans)
方法二：简化。 
1
2
3
4
5
6
def numsSameConsecDiff(self, N, K):
    ans = range(10)
    for _ in range(N-1):
        ans = {x*10+y for x in ans for y in (x%10-K, x%10+K) 
               if x and 0<=y<10}
    return list(ans)

561. Array Partition I

将数组两两分成一组，累加每组的最小值，使之尽量大。原题

1
2
3
4
Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).
1
2
def arrayPairSum(self, nums):
    return sum(sorted(nums)[::2])

566. Reshape the Matrix

改变矩阵的形状，如果元素超出或不足，返回原矩阵。原题

1
2
3
4
5
6
7
8
9
Input: 
nums = 
[[1,2],
 [3,4]]
r = 1, c = 4
Output: 
[[1,2,3,4]]
Explanation:
The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.

方法一：扁平化后重组。

1
2
3
4
5
6
def matrixReshape(self, nums, r, c):
    a = [x for row in nums for x in row]
    n = len(a)
    if r*c != n:
        return nums
    return [a[i*c:i*c+c] for i in range(r)]
方法二：使用itertools. 
1
2
3
4
5
6
def matrixReshape(self, nums, r, c):
    if r*c != len(nums)*len(nums[0]):
        return nums
    from itertools import islice, chain
    it = chain(*nums)
    return [list(islice(it, c)) for _ in range(r)]

575. Distribute Candies

给姐姐弟弟分糖，两人数量一样，保证姐姐的种类最多，求姐姐最多能分到多少种。原题

1
2
3
4
5
6
Input: candies = [1,1,2,2,3,3]
Output: 3
Explanation:
There are three different kinds of candies (1, 2 and 3), and two candies for each kind.
Optimal distribution: The sister has candies [1,2,3] and the brother has candies [1,2,3], too. 
The sister has three different kinds of candies.
1
2
def distributeCandies(self, candies):
    return min(len(candies)//2, len(set(candies)))

594. Longest Harmonious Subsequence

最长的和谐子数组，即元素的最大值和最小值正好相差一的子数组，元素顺序无关，求最大子数组长度。原题

1
2
3
Input: [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

方法一：开始想错了，后来发现子数组只能包含两个元素。

1
2
3
4
5
6
7
8
def findLHS(self, nums):
    from collections import Counter
    res = 0
    c = Counter(nums)
    for num, count in c.items():
        sum_count = count+c[num+1] if c[num+1] else 0
        res = max(res, sum_count)
    return res
方法二：one-liner. 
1
2
3
4
5
def findLHS(self, nums):
    from collections import Counter
    c = Counter(nums)
    return max([count+c[num+1] for num, count in c.items() 
                if num+1 in c] or [0])

598. Range Addition II

这题看上去挺长，其实抽象起来很简单，把整个矩阵想象成一个积木，然后每次往上叠加，每次叠放的矩形都会和左上角对齐，所以最后完成的时候，左上角的一小块一定是最“厚”的，问题就变成和左上一样的厚度的面积。实际上等于叠放的所有矩形的最小长度和最小宽度的乘积。原题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Input: 
m = 3, n = 3
operations = [[2,2],[3,3]]
Output: 4
Explanation: 
Initially, M = 
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]

After performing [2,2], M = 
[[1, 1, 0],
 [1, 1, 0],
 [0, 0, 0]]

After performing [3,3], M = 
[[2, 2, 1],
 [2, 2, 1],
 [1, 1, 1]]

So the maximum integer in M is 2, and there are four of it in M. So return 4.
1
2
3
4
5
def maxCount(self, m, n, ops):
    if not ops:
        return m*n
    length, width = list(zip(*ops))
    return min(length) * min(width)

599. Minimum Index Sum of Two Lists

找出两个人共同最喜欢的餐厅。如果有多个输出多个。原题

1
2
3
4
Input:
["Shogun","Tapioca Express","Burger King","KFC"]
["Piatti","The Grill at Torrey Pines","Tapioca Express","Shogun"]
Output: ['Shogun', 'Tapioca Express']

方法一：这里做了一个优化，以原list1的顺序输出数组，如果索引太大超出了最小索引和，这样即使是map2使用第一个元素也无法满足条件，直接退出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def findRestaurant(self, list1, list2):
    map2 = {x: i for i, x in enumerate(list2)}
    res, min_sum = [], float('inf')
    for i, rest in enumerate(list1):
        # optimize 
        if i > min_sum: 
            break
        if rest in map2:
            if i+map2[rest] < min_sum:
                res = [rest]
                min_sum = i+map2[rest]
            elif i+map2[rest] == min_sum:
                res += [rest]
    return res

605. Can Place Flowers

是否可以种下给定数量的花。两颗花不能挨着，给定的数组中满足这一条件。原题

1
2
Input: flowerbed = [1,0,0,0,1], n = 2
Output: False
1
2
3
4
5
6
7
8
9
def canPlaceFlowers(self, flowerbed, n):
    plots = [0] + flowerbed + [0]
    p = 1
    while p <= len(flowerbed) and n > 0:
        if plots[p] == 0 and plots[p-1] == 0 and plots[p+1] == 0:
            plots[p] = 1
            n -= 1
        p += 1
    return n == 0

643. Maximum Average Subarray I

最大的连续的长度为k的子数组的平均值。原题

1
2
3
Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75

方法一：参考了stefen大神的答案，自己写的滑动窗口居然超时了。accumulate也不是想不到，此答案厉害的地方在于 补0 和map操作。像这种固定长度的滑动窗口使用补0的accumulate，可以用到其他的题上。

1
2
3
def findMaxAverage(self, nums, k):
    sums = [0] + list(itertools.accumulate(nums))
    return max(map(operator.sub, sums[k:], sums)) / k

661. Image Smoother

使图片平滑模糊，一个矩阵使每个点的值为周围所有点的平均值，包括自己。原题

1
2
3
4
5
6
7
8
9
10
11
12
Input:
[[1,1,1],
 [1,0,1],
 [1,1,1]]
Output:
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]
Explanation:
For the point (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0
For the point (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0
For the point (1,1): floor(8/9) = floor(0.88888889) = 0

方法一：参考了评论区一位朋友的写法，不过效率不是很高，800ms，Solution给出的方法也是这个速度，看来如果优化的话，可能使用numpy会好一点。

1
2
3
4
5
6
7
8
9
10
11
def imageSmoother(self, M):
    import itertools
    R, C = len(M), len(M[0]) 
    res = [[0]*C for _ in range(R)]
    offset = list(itertools.product([-1, 0, 1], [-1, 0, 1]))
    for i in range(R):
        for j in range(C):
            points = [M[i+x][j+y] for x, y in offset
                      if 0<=i+x<R and 0<=j+y<C]
            res[i][j] = sum(points) // len(points)
    return res

665. Non-decreasing Array

判断是否改变一个数，可使其变成单调递增数组。原题

1
2
3
Input: [4,2,3]
Output: True
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.
1
2
3
4
5
6
7
8
9
10
def checkPossibility(self, nums):
    n = len(nums)
    p = None
    for i in range(n-1):
        if nums[i] > nums[i+1]:
            if p is not None:
                return False
            p = i
    return (not p) or p == n-2 or nums[p-1] <= nums[p+1] or \
           nums[p] <= nums[p+2]
  • If p = 0, then we could make the array good by setting A[p] = A[p+1]
  • if p = len(A) - 2, then we could make the array good by setting A[p+1] = A[p]
  • Otherwise, A[p-1], A[p], A[p+1], A[p+2] all exist, and:
    • change A[p] to be between A[p-1] and A[p+1] if possible, or: [4, 8, 6]
    • change A[p+1] to be between A[p] and A[p+2] if possible. [4, 5, 3, 6]

674. Longest Continuous Increasing Subsequence

最长连续递增子数组长度。原题

1
2
3
4
Input: [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3. 
Even though [1,3,5,7] is also an increasing subsequence, it's not a continuous one where 5 and 7 are separated by 4.
1
2
3
4
5
6
7
8
def findLengthOfLCIS(self, nums: 'List[int]') -> 'int':
    ans = anchor = 0
    for i in range(len(nums)):
        if i and nums[i] <= nums[i-1]:
            anchor = i
        else:
            ans = max(ans, i-anchor+1)
    return ans

682. Baseball Game

棒球游戏，给了一些积分规则。原题

1
2
3
4
5
6
7
8
Input: ["5","2","C","D","+"]
Output: 30
Explanation: 
Round 1: You could get 5 points. The sum is: 5.
Round 2: You could get 2 points. The sum is: 7.
Operation 1: The round 2's data was invalid. The sum is: 5.  
Round 3: You could get 10 points (the round 2's data has been removed). The sum is: 15.
Round 4: You could get 5 + 10 = 15 points. The sum is: 30.
1
2
3
4
5
6
7
8
9
10
11
12
def calPoints(self, ops):
    stack = []
    for op in ops:
        if op == 'C':
            stack.pop()
        elif op == 'D':
            stack.append(stack[-1]*2)
        elif op == '+':
            stack.append(stack[-1] + stack[-2])
        else:
            stack.append(int(op))
    return sum(stack)

690. Employee Importance

员工重要值。原题

1
2
3
4
Input: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
Output: 11
Explanation:
Employee 1 has importance value 5, and he has two direct subordinates: employee 2 and employee 3. They both have importance value 3. So the total importance value of employee 1 is 5 + 3 + 3 = 11.
方法一：iteratively. 
1
2
3
4
5
6
7
8
def getImportance(self, employees, id):
    emp_dict = {ep.id: (ep.importance, ep.subordinates) for ep in employees}
    res, stack = 0, [id]
    while stack:
        value, subs = emp_dict.get(stack.pop())
        res += value
        stack += subs
    return res

方法二：recursively.

1
2
3
4
5
def getImportance(self, employees, id):
    emp_dict = {ep.id: (ep.importance, ep.subordinates) for ep in employees}
    def dfs(pk):
        return emp_dict[pk][0] + sum(dfs(sub) for sub in emp_dict[pk][1])
    return dfs(id)

724. Find Pivot Index

找到中心索引，使得左右两边和相等。左右求和时均不包含该索引。原题

1
2
3
4
5
6
7
8
9
10
Input: 
nums = [1, 7, 3, 6, 5, 6]
Output: 3
Explanation: 
The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3.
Also, 3 is the first index where this occurs.

Input:
nums = [1,0]
Output: 0

方法一：指针。

1
2
3
4
5
6
7
8
9
def pivotIndex(self, nums):
    left, right, i = 0, sum(nums), 0
    while i < len(nums):
        left += nums[i-1] if i > 0 else 0
        right -= nums[i] 
        if left == right:
            return i
        i += 1
    return -1
方法二：不使用指针。 
1
2
3
4
5
6
7
def pivotIndex(self, nums):
    S, left = sum(nums), 0
    for i, num in enumerate(nums):
        if left == S-left-num:
            return i
        left += num
    return -1

985. Sum of Even Numbers After Queries

计算Queries后，累加所有的偶数。原题

1
2
3
4
5
6
7
8
Input: A = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
Output: [8,6,2,4]
Explanation: 
At the beginning, the array is [1,2,3,4].
After adding 1 to A[0], the array is [2,2,3,4], and the sum of even values is 2 + 2 + 4 = 8.
After adding -3 to A[1], the array is [2,-1,3,4], and the sum of even values is 2 + 4 = 6.
After adding -4 to A[0], the array is [-2,-1,3,4], and the sum of even values is -2 + 4 = 2.
After adding 2 to A[3], the array is [-2,-1,3,6], and the sum of even values is -2 + 6 = 4.
1
2
3
4
5
6
7
8
9
10
11
def sumEvenAfterQueries(self, A: 'List[int]', queries: 'List[List[int]]') -> 'List[int]':
    res = []
    sum_even = sum(x for x in A if x & 1 == 0)
    for v, i in queries:
        if A[i] & 1 == 0:
            sum_even -= A[i]
        A[i] += v
        if A[i] & 1 == 0:
            sum_even += A[i]
        res.append(sum_even)
    return res

986. Interval List Intersections

两个区间列表求相交。原题

1
2
3
Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists.
1
2
3
4
5
6
7
8
9
10
11
12
13
def intervalIntersection(self, A: 'List[Interval]', B: 'List[Interval]') -> 'List[Interval]':
    i = j = 0
    res = []
    while i < len(A) and j < len(B):
        lo = max(A[i].start, B[j].start)
        hi = min(A[i].end, B[j].end)
        if lo <= hi:
            res.append(Interval(lo, hi))
        if A[i].end > B[j].end:
            j += 1
        else:
            i += 1
    return res

747. Largest Number At Least Twice of Others

最大的数是否大于等于所有其它数的两倍。原题

1
2
3
4
Input: nums = [3, 6, 1, 0]
Output: 1
Explanation: 6 is the largest integer, and for every other number in the array x,
6 is more than twice as big as x.  The index of value 6 is 1, so we return 1.
1
2
3
4
5
def dominantIndex(self, nums: 'List[int]') -> 'int':
    max_v = max(nums)
    if all(max_v >= 2*x for x in nums if x!=max_v):
        return nums.index(max_v)
    return -1

766. Toeplitz Matrix

Toeplitz矩阵，即对角矩阵，斜角具有相同的值，判断一个矩阵是否是对角矩阵。原题

1
2
3
4
5
6
7
8
9
10
11
Input:
matrix = [
  [1,2,3,4],
  [5,1,2,3],
  [9,5,1,2]
]
Output: True
Explanation:
In the above grid, the diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
In each diagonal all elements are the same, so the answer is True.

方法一：嵌套循环。

1
2
3
4
def isToeplitzMatrix(self, matrix: 'List[List[int]]') -> 'bool':
    return all(x==0 or y==0 or matrix[x-1][y-1]==val
               for x, rows in enumerate(matrix)
               for y, val in enumerate(rows))
方法二：切片，与上述方法在效率空间上没有差距，更喜欢这个方法。 
1
2
3
def isToeplitzMatrix(self, matrix: 'List[List[int]]') -> 'bool':
    return all(matrix[i][1:]==matrix[i-1][:-1]
               for i in range(1, len(matrix)))

830. Positions of Large Groups

根据指定字符串分组，超过三个元素的称为大组，求所有大组的位置。原题

1
2
Input: "abcdddeeeeaabbbcd"
Output: [[3,5],[6,9],[12,14]]

方法一：groupby.

1
2
3
4
5
6
7
8
9
def largeGroupPositions(self, S: 'str') -> 'List[List[int]]':
    groups = itertools.groupby(S)
    index, ans = 0, []
    for s, group in groups:
        count = len(list(group))
        if count >= 3:
            ans.append([index, index+count-1])
        index += count
    return ans

方法二：two pointers.

1
2
3
4
5
6
7
8
9
def largeGroupPositions(self, S: 'str') -> 'List[List[int]]':
    i = 0 # start of each group
    ans = []
    for j in range(len(S)):
        if j == len(S)-1 or S[j] != S[j+1]:
            if j - i >= 2:
                ans.append([i, j])
            i = j + 1
    return ans

832. Flipping an Image

水平翻转一张图片并反转(invert). 原题

1
2
3
4
Input: [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]
1
2
def flipAndInvertImage(self, A: 'List[List[int]]') -> 'List[List[int]]':
    return [[x ^ 1 for x in reversed(row)] for row in A]

840. Magic Squares In Grid

找出grid中数独的个数。原题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Input: [[4,3,8,4],
        [9,5,1,9],
        [2,7,6,2]]
Output: 1
Explanation: 
The following subgrid is a 3 x 3 magic square:
438
951
276

while this one is not:
384
519
762

In total, there is only one magic square inside the given grid.

方法一：Brute Force.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def numMagicSquaresInside(self, grid: 'List[List[int]]') -> 'int':
    digits = set(range(1, 10))
    ans = 0
    
    def is_sudoku(matrix):
        if matrix[1][1] != 5:   # for optimization
            return False
        if set(sum(matrix, [])) != digits:
            return False
        if {sum(row) for row in matrix} != {15}:
            return False
        if {sum(col) for col in zip(*matrix)} != {15}:
            return False
        if matrix[0][0] + matrix[1][1] + matrix[2][2] != 15 or \
           matrix[2][0] + matrix[1][1] + matrix[0][2] != 15:
            return False
        return True
    
    for i in range(len(grid)-2):
        for j in range(len(grid[0])-2):
            matrix = [rows[j:j+3] for rows in grid[i:i+3]]
            # print(matrix)
            if is_sudoku(matrix):
                ans += 1
    return ans

方法二：参考了大神的解法。外层循环中只把左上角的点传入子方法进行判断，并在外循环判断中心点是否为5；

另外一个规律就是，满足条件数独的9宫格中，4个角都是偶数，4个边都是奇数，并且沿着一个方向必然是’43816729’的正序或者倒序。所以当左上角为偶数时，并满足顺序要求，另两个条件也自然满足了。

1
2
3
4
5
6
7
8
9
10
11
def numMagicSquaresInside(self, g: 'List[List[int]]') -> 'int':

    def is_sudoku(i, j):
        # clockwise begin i, j
        s = ''.join(str(g[i + x//3][j + x%3])
                    for x in (0, 1, 2, 5, 8, 7, 6, 3))
        return g[i][j] & 1 == 0 and (
            s in '43816729'*2 or s in '43816729'[::-1]*2)
    
    return sum(is_sudoku(i, j) for i in range(len(g)-2)
               for j in range(len(g[0])-2) if g[i+1][j+1] == 5)

849. Maximize Distance to Closest Person

一排电影院座位，离人的最远距离。数组中必含有一个1和0。原题

1
2
3
4
5
6
Input: [1,0,0,0,1,0,1]
Output: 2
Explanation: 
If Alex sits in the second open seat (seats[2]), then the closest person has distance 2.
If Alex sits in any other open seat, the closest person has distance 1.
Thus, the maximum distance to the closest person is 2.
方法一：groupby。需要注意两个地方：一个是group是一个生成器，必须转成list才可以求长度；另一个地方是reversed(seats)也是一个生成器，所以这里要用切片。 
1
2
3
4
5
6
7
def maxDistToClosest(self, seats: 'List[int]') -> 'int':
    ans = 0
    groups = itertools.groupby(seats)
    for seat, group in groups:
        if not seat:
            ans = max(ans, (len(list(group))+1) // 2)
    return max(ans, seats.index(1), seats[::-1].index(1))

方法二：two pointers. 在第一个1出现之前长度都是j。直到第二个1出现时，计算方式变为平均数。这里使用i = j + 1而不是i = j是因为有根据i判断的条件，在计算平均距离时又将其加了回来。最后的len(seats)-i是为了[1, 0, 0, 0]末尾的0作结算。

1
2
3
4
5
6
7
8
9
10
11
12
def maxDistToClosest(self, seats: 'List[int]') -> 'int':
    ans = i = 0
    for j in range(len(seats)):
        # print(j, i, ans)
        if seats[j] == 1:
            dis = (j - i + 1) // 2
            if i == 0:
                dis = j    
            ans = max(ans, dis)
            i = j + 1
    # print(ans)
    return max(ans, len(seats)-i)
方法三：方法二的简洁写法。 
1
2
3
4
5
6
7
def maxDistToClosest(self, seats: 'List[int]') -> 'int':
    ans = i = 0
    for j in range(len(seats)):
        if seats[j] == 1:
            ans = max(ans, ((j-i+1)//2, j)[i==0])
            i = j + 1
    return max(ans, len(seats)-i)

867. Transpose Matrix

转置矩阵。原题

1
2
Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]

方法一：zip。 这里testcase并没有检测其中的元素是否为list。所以不需要转换。

1
2
def transpose(self, A: 'List[List[int]]') -> 'List[List[int]]':
    return list(zip(*A))

方法二：zip原理。

1
2
def transpose(self, A: 'List[List[int]]') -> 'List[List[int]]':
    return list(map(lambda *arg: arg, *A))

方法三：列表生成式。

1
2
3
def transpose(self, A: 'List[List[int]]') -> 'List[List[int]]':
    return [[A[i][j] for i in range(len(A))]
           for j in range(len(A[0]))]

方法四：numpy.

1
2
3
def transpose(self, A):
    import numpy as np
    return np.transpose(A).tolist()

888. Fair Candy Swap

公平的糖果交换。两个人有很多糖果酒吧，交换其中一间使，糖果相同，可能有多个答案，返回任意一个。原题

1
2
Input: A = [1,1], B = [2,2]
Output: [1,2]

方法一：Solution中的答案。

1
2
3
4
5
6
def fairCandySwap(self, A: 'List[int]', B: 'List[int]') -> 'List[int]':
    diff = (sum(B) - sum(A)) // 2
    set_b = set(B)
    for a in A:
        if diff + a in set_b:
            return a, diff + a

896. Monotonic Array

判断一个数组是不是单调递增或递减。原题

1
2
3
4
5
Input: [1,2,2,3]
Output: true

Input: [6,5,4,4]
Output: true
方法一：迭代两次。但是由于是生成器，平均效率比下面要高。 
1
2
3
def isMonotonic(self, A: 'List[int]') -> 'bool':
    return all(A[i] <= A[i+1] for i in range(len(A)-1)) or \
           all(A[i] >= A[i+1] for i in range(len(A)-1))

方法二：迭代一次。

1
2
3
4
5
6
7
8
9
10
def isMonotonic(self, A: 'List[int]') -> 'bool':
    increasing = decreasing = True
    for i in range(len(A)-1):
        if A[i+1] > A[i]:
            decreasing = False
        if A[i+1] < A[i]:
            increasing = False
        if not decreasing and not increasing:
            return False
    return True

方法三：python2的一种写法。

1
2
def isMonotonic(self, A):
    return not {cmp(i, j) for i, j in zip(A, A[1:])} >= {1, -1}

977. Squares of a Sorted Array

求一个有序数组，平方后的有序结果。原题

1
2
Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

方法一：双指针填充数组。

1
2
3
4
5
6
7
8
9
10
11
12
def sortedSquares(self, A: 'List[int]') -> 'List[int]':
    answer = [0] * len(A)
    l, r = 0, len(A) - 1
    while l <= r:
        left, right = abs(A[l]), abs(A[r])
        if left > right:
            answer[r - l] = left * left
            l += 1
        else:
            answer[r - l] = right * right
            r -= 1
    return answer

941. Valid Mountain Array

验证是否是山峰数组，前段单调增（不重复），后段单调减，必须是单峰值。原题

1
2
Input: [0,3,2,1]
Output: true

方法一：传统迭代方式。

1
2
3
4
5
6
7
8
9
10
11
12
def validMountainArray(self, A: 'List[int]') -> 'bool':
    increasing = True
    for i in range(len(A)-1):
        if A[i] == A[i+1]:
            return False
        if A[i] > A[i+1]:
            increasing = False
        if not increasing and (A[i] < A[i+1] or i ==0):
            return False
        if i == len(A)-2 and increasing:
            return False
    return len(A) >= 3
方法二：这个方法挺新颖，根据值来递增索引。中途暂停一下判断峰值是否在首位点。 
1
2
3
4
5
6
7
8
9
def validMountainArray(self, A: 'List[int]') -> 'bool':
    l, r = 0, len(A)-1
    while l < r and A[l] < A[l+1]:
        l += 1
    if l==0 or l == r:
        return False
    while l < r and A[l] > A[l+1]:
        l += 1
    return l == r
方法三：Lee神的双指针，想象两个人同时从左右两边爬山，最终是否相遇在一点。 
1
2
3
4
5
def validMountainArray(self, A: 'List[int]') -> 'bool':
    l, r, n = 0, len(A)-1, len(A)
    while l < r and A[l] < A[l+1]: l += 1
    while r > 0 and A[r] < A[r-1]: r -= 1
    return 0 < l==r < n-1

845. Longest Mountain in Array

数组中最长的山峰。题和字符串篇821一样的解法。

1
2
3
Input: [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

方法一：左右各遍历一次。此题有很多相似题都有这个解法。53 Maximum Subarray，121 Best Time to Buy and Sell Stock，152 Maximum Product Subarray，238 Product of Array Except Self，739 Daily Temperatures，769 Max Chunks to Make Sorted，770 Max Chunks to Make Sorted II，821 Shortest Distance to a Character，845 Longest Mountain in Array

1
2
3
4
5
6
7
8
9
10
11
12
13
def longestMountain(self, A: List[int]) -> int:
    N = len(A)
    left = [0] * N
    right = [0] * N
    for i in range(1, N):
        if A[i] > A[i-1]:
            left[i] += left[i-1] + 1

    for i in range(N-1, 0, -1): 
        if A[i] < A[i-1]:
            right[i-1] += right[i] + 1

    return max((l+r+1 for l, r in zip(left, right) if l and r), default=0)
方法二：时间复杂度还可以优化，空间可以降到O(1)， 一次遍历。使用两个数字来表示上坡和下坡，当有下拨并且再次上坡时，或者相等的时候重置up,down为0。 
1
2
3
4
5
6
7
8
9
def longestMountain(self, A: List[int]) -> int:
    res = up = down = 0
    for i in range(1, len(A)):
        if down and A[i]>A[i-1] or A[i]==A[i-1]:
            up = down = 0
        up += A[i] > A[i-1]
        down += A[i] < A[i-1]
        if up and down: res = max(res, up+down+1)
    return res

942. DI String Match

根据一个”IDID”字符串（I表示增加，D表示减少）生成一个数组，数组元素不能重复，答案不唯一。原题

1
2
Input: "IDID"
Output: [0,4,1,3,2]
1
2
3
4
5
6
7
8
9
10
11
def diStringMatch(self, S: 'str') -> 'List[int]':
    l = r = 0
    ans = [0]
    for s in S:
        if s == 'I':
            r += 1
            ans.append(r)
        else:
            l -= 1
            ans.append(l)
    return [x-l for x in ans]

1007. Minimum Domino Rotations For Equal Row

旋转最小次，是上下的多米诺骨牌有一行全部相同。原题

方法一：竞赛时写的Brute Force.当时觉得炒鸡硬核。

1
2
3
4
5
6
7
8
def minDominoRotations(self, A: List[int], B: List[int]) -> int:
    ans = reduce(lambda x, y: set(x) & set(y), zip(A, B))
    if not ans:
        return -1
    else:
        a = set(ans).pop()
        dul = sum(a==c==d for c, d in zip(A, B))
        return min(A.count(a), B.count(a)) - dul
方法二：Lee神的方法。有个地方想错了，想要算出重复的值，实际上就是求非目标值的最小值就行了。 
1
2
3
4
5
6
7
def minDominoRotations(self, A: List[int], B: List[int]) -> int:
    ans = reduce(lambda x, y: x & y, map(set, zip(A, B)))
    if not ans:
        return -1
    else:
        a = ans.pop()
        return min(len(A)-A.count(a), len(B)-B.count(a))

48. Rotate Image

矩阵顺时针旋转90度。原题

1
2
3
4
5
6
7
8
9
10
11
12
13
Given input matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

方法一：使用zip。

1
2
def rotate(self, matrix: List[List[int]]) -> None:
	matrix[:] = list(zip(*reversed(matrix)))

方法二：通用写法。

1
2
3
4
5
def rotate(self, matrix: List[List[int]]) -> None:
    matrix.reverse()
    for i in range(len(matrix)):
        for j in range(i+1, len(matrix[0])):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

方法三：找到四个点，直接互换。

1
2
3
4
5
6
def rotate(self, A: List[List[int]]) -> None:
    n = len(A)
    for i in range(n//2):
        for j in range(n-n//2):
            A[i][j], A[~j][i], A[~i][~j], A[j][~i] = \
                     A[~j][i], A[~i][~j], A[j][~i], A[i][j]

1020. Partition Array Into Three Parts With Equal Sum

一个数组是否可以分成三个和相同的部分。原题

1
2
3
Input: [0,2,1,-6,6,-7,9,1,2,0,1]
Output: true
Explanation: 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

方法一：竞赛时写的Time: O(n²)的方法。

1
2
3
4
5
6
7
8
def canThreePartsEqualSum(self, A: List[int]) -> bool:
    a = list(itertools.accumulate(A))
    n, a_set = len(a), set(a)
    for i, total in enumerate(a):
        if total==a[-1]//3 and total*2 in a_set:
            if n-1-a[::-1].index(total*2) > i:
                return True
    return False
方法二：其实不需要遍历。每部分的和可以通过总和/3得到。比如每部分和为3，只要找到3和6，并且3在6的左边。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def canThreePartsEqualSum(self, A: List[int]) -> bool:
    a = list(itertools.accumulate(A))
    total = sum(A)
    if total % 3 != 0:
        return False
    one = total // 3
    two = one * 2
    if one in a:
        l_index = a.index(one)
    else:
        return False
    if two in a[l_index:]:
        return True
    else:
        return False

1021. Best Sightseeing Pair

得分最高的两个景点。原题

两个景点之间有距离。

1
2
3
Input: [8,1,5,2,6]
Output: 11
Explanation: i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11

方法一：cur保存着一个上一次最好的景点。

1
2
3
4
5
6
def maxScoreSightseeingPair(self, A: List[int]) -> int:
    cur = res = 0
    for a in A:
        res = max(res, cur + a)
        cur = max(cur, a) - 1
    return res

56. Merge Intervals

合并时间段。如果时间段有重叠，则将其合并成一个。原题

1
2
3
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

方法一：先排序，在根据条件判断是合并还是修改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:
    def merge(self, intervals: List[Interval]) -> List[Interval]:
        intervals.sort(key=operator.attrgetter('start'))
        ans = []
        for interval in intervals:
            if not ans or ans[-1].end < interval.start:
                ans.append(interval)
            else:
                ans[-1].end = max(ans[-1].end, interval.end)
        return ans

57. Insert Interval

有一个排好序的时间段，并且没有重复，现在有一个新的段，要求插入其中，如果有重合需要合并。原题

1
2
3
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

方法一：用56的方法合并，使用二分法将其插入。140ms。这题本来想用二分法找到索引，然后前后切片做，后来发现边界太多不好判断，还是从头到尾遍历一遍比较稳。

1
2
3
4
5
6
7
8
9
10
11
def insert(self, inter: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    n = len(inter)
    i = bisect.insort(inter, [*newInterval])
    # print(inter, i)
    stack = []
    for j in range(0, n+1):
        if not stack or stack[-1][1] < inter[j][0]:
            stack.append(inter[j])
        else:
            stack[-1][1] = max(stack[-1][1], inter[j][1])
    return stack
方法二：stefan的方法1，我改了点，条件语句改成长度比较了。启发1，用长度记录索引，简洁明了。72ms 
1
2
3
4
5
6
7
8
def insert(self, inter: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    s, e = newInterval
    left = [i for i in inter if i[1] < s]
    right = [i for i in inter if i[0] > e]
    if len(left) + len(right) != len(inter):
        s = min(s, inter[len(left)][0])
        e = max(e, inter[~len(right)][1])
    return left + [[s, e]] + right
方法三：stefan的方法2，和方法二思路一样，写法上不同。right里添加时索引是-1。还有一种一次遍历的实现就是每次都求一下s, e。 
1
2
3
4
5
6
7
8
9
def insert(self, inter: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    s, e = newInterval
    parts = merge, left, right = [], [], []
    for start, end in inter:
        parts[(end<s) - (start>e)].append((start, end))
    if merge:
        s = min(s, merge[0][0])
        e = max(e, merge[-1][-1])
    return left + [[s, e]] + right

1030. Matrix Cells in Distance Order

矩阵坐标距离指定点的排序。原题

1
2
3
4
Input: R = 2, C = 2, r0 = 0, c0 = 1
Output: [[0,1],[0,0],[1,1],[1,0]]
Explanation: The distances from (r0, c0) to other cells are: [0,1,1,2]
The answer [[0,1],[1,1],[0,0],[1,0]] would also be accepted as correct.
1
2
3
def allCellsDistOrder(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:
    cells = [[x, y] for x in range(R) for y in range(C)]
    return sorted(cells, key=lambda x: abs(x[0]-r0)+abs(x[1]-c0))

1033. Moving Stones Until Consecutive

三个石子移到连续的位置，最少和最多需要几步。原题

1
2
3
4
5
6
Input: a = 1, b = 2, c = 5
Output: [1,2]
Explanation: Move the stone from 5 to 3, or move the stone from 5 to 4 to 3.
Input: a = 4, b = 3, c = 2
Output: [0,0]
Explanation: We cannot make any moves.
1
2
3
4
5
6
7
8
def numMovesStones(self, a: int, b: int, c: int) -> List[int]:
    a, b, c = sorted((a, b, c))
    if c-b==1 and b-a==1:
        return 0, c-a-2
    elif c-b<=2 or b-a<=2:
        return 1, c-a-2
    else:
        return 2, c-a-2

1051. Height Checker

高度检查。原题

1
2
def heightChecker(self, heights: List[int]) -> int:
    return sum(a!=b for a, b in zip(heights, sorted(heights)))

1052. Grumpy Bookstore Owner

这题描述的比较抽象，其实就是一个滑动窗口的问题。原题

方法一：一开始我用的双端队列，并且使用了compress.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
    from itertools import compress
    from collections import deque
    base_satisfied = sum(compress(customers, map(lambda x: x^1, grumpy)))
    q = deque([customers[i] if grumpy[i]==1 else 0  for i in range(X)])
    cur_sum = 0
    max_sum = cur_sum
    for i in range(len(grumpy)):
        if grumpy[i] == 1:
            q.append(customers[i])
            cur_sum += q[-1]
        else:
            q.append(0)
        cur_sum -= q.popleft()
        max_sum = max(max_sum, cur_sum)
    return max_sum + base_satisfied
方法二：其实不需要双端队列。 
1
2
3
4
5
6
7
8
9
def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
    n = len(grumpy)
    base = sum(c for c, g in zip(customers, grumpy) if g == 0)
    max_added = added = sum(c for c, g in zip(customers, grumpy[:X]) if g == 1)
    for i in range(X, n):
        added -= customers[i-X] * grumpy[i-X]
        added += customers[i] * grumpy[i]
        max_added = max(max_added, added)
    return max_added + base

1139. Largest 1-Bordered Square

最大的以1为边长的正方形。原题

1
2
Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: 9

方法一：开始以为像其他小岛问题那样，要回溯延伸。其实此题是暴力法。先对数组进行一个预处理，判断每个点上面和左面连续的1的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def largest1BorderedSquare(self, g: List[List[int]]) -> int:
    R, C = len(g), len(g[0])
    from copy import deepcopy
    top, left = deepcopy(g), deepcopy(g)
    for i in range(R):
        for j in range(C):
            if g[i][j]:
                if i: top[i][j] = top[i - 1][j] + 1
                if j: left[i][j] = left[i][j - 1] + 1
    for w in range(min(R, C), 0, -1):
        for i in range(R-w+1):
            for j in range(C-w+1):
                if top[i+w-1][j] >= w and top[i+w-1][j+w-1] >= w:
                    if left[i][j+w-1] >= w and left[i+w-1][j+w-1] >= w:
                        return w * w
    return 0

1078. Occurrences After Bigram

打印第三个单词。原题

1
2
Input: text = "alice is a good girl she is a good student", first = "a", second = "good"
Output: ["girl","student"]
1
2
3
4
5
6
7
def findOcurrences(self, text: str, first: str, second: str) -> List[str]:
    words = text.split()
    ans = []
    for i in range(len(words)-2):
        if words[i] == first and words[i+1] == second:
            ans.append(words[i+2]) 
    return ans

1144. Decrease Elements To Make Array Zigzag

每次操作某个元素-1，多少次操作后，可以使数组称为一个zigzag。原题

1
2
Input: nums = [9,6,1,6,2]
Output: 4

方法一：暴力的方法。遍历两次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def movesToMakeZigzag(self, nums: List[int]) -> int:
    n = len(nums)
    even_sum = 0
    for i in range(1, n, 2):
        left = float('inf') if i == 0 else nums[i-1]
        right = float('inf') if i == n-1 else nums[i+1]
        to_add = nums[i]-min(left, right)+1
        even_sum += to_add if to_add > 0 else 0
    
    odd_sum = 0
    for i in range(0, n, 2):
        left = float('inf') if i == 0 else nums[i-1]
        right = float('inf') if i == n-1 else nums[i+1]
        to_min = nums[i]-min(left, right)+1
        odd_sum += to_min if to_min > 0 else 0
    return min(even_sum, odd_sum)
方法二：利用奇偶性，整合到一次循环。 
1
2
3
4
5
6
def movesToMakeZigzag(self, nums: List[int]) -> int:
    ans = [0, 0]
    ary = [float('inf')] + nums + [float('inf')]
    for i in range(1, len(ary)-1):  
        ans[i % 2] += max(0, ary[i]-min(ary[i-1], ary[i+1])+1)
    return min(ans)

1089. Duplicate Zeros

复制数组中的0，数组长度不变，多出的元素将被“挤掉”。要求在原数组上修改。原题

1
2
3
Input: [1,0,2,3,0,4,5,0]
Output: null
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]

方法一：竞赛时的方法，需要注意末尾不要多加0。空间复杂度过高。

1
2
3
4
5
6
7
8
9
10
11
def duplicateZeros(self, arr: List[int]) -> None:
    # arr_reversed = arr[::-1]
    # ans = []
    # while len(ans) < len(arr):
    #     val = arr_reversed.pop()
    #     if val == 0 and len(ans) < len(arr)-1:
    #         ans.extend([0, 0])
    #     else:
    #         ans.append(val)
    # arr[:] = ans
    arr[:] = [x for a in arr for x in ([a] if a else [0, 0])][:len(arr)]
方法二：双指针的O(1)Space。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def duplicateZeros(self, arr: List[int]) -> None:
    zero_c = arr.count(0)
    n = len(arr)
    j = n + zero_c - 1
    i = n - 1
    while i >= 0:
        if arr[i] != 0:
            if j < n:
                arr[j] = arr[i]
        else:
            if j < n:
                arr[j] = arr[i]
            j -= 1
            if j < n:
                arr[j] = arr[i]
        j -= 1
        i -= 1

1169. Invalid Transactions

非法交易，单笔金额大于1000，或者60分钟内有异地交易，那么为非法交易。列出所有的非法交易。原题

1
2
3
Input: transactions = ["alice,20,800,mtv","alice,50,100,beijing"]
Output: ["alice,20,800,mtv","alice,50,100,beijing"]
Explanation: The first transaction is invalid because the second transaction occurs within a difference of 60 minutes, have the same name and is in a different city. Similarly the second one is invalid too.

方法一：暴力法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def invalidTransactions(self, transactions: List[str]) -> List[str]:
    ts = []
    for line in transactions:
        name, time, amount, city = line.split(',')
        ts.append((name, time, amount, city))
    city_times = collections.defaultdict(list)
    for t in ts:
        city_times[t[0]+','+t[3]].append(int(t[1]))
    ans = []
    for t in ts:
        if int(t[2]) > 1000:
            ans.append(','.join(t))
        else:
            diff_cities = (c for c in city_times.keys() if c!=t[0]+','+t[3] and c.startswith(t[0]+','))
            for d_c in diff_cities:
                if any(abs(tt-int(t[1])) <= 60 for tt in city_times[d_c]):
                    ans.append(','.join(t))
                    break
    return ans

1170. Compare Strings by Frequency of the Smallest Character

比较最小字符的频率。原题

1
2
3
Input: queries = ["cbd"], words = ["zaaaz"]
Output: [1]
Explanation: On the first query we have f("cbd") = 1, f("zaaaz") = 3 so f("cbd") < f("zaaaz").

方法一：暴力法。

1
2
3
4
def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
    qq = [q.count(min(q)) for q in queries]
    ww = [w.count(min(w)) for w in words]
    return [sum(q < w for w in ww) for q in qq]
方法二：二分法 
1
2
3
4
5
6
def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
    qq = [q.count(min(q)) for q in queries]
    ww = [w.count(min(w)) for w in words]
    ww.sort()
    n = len(ww)
    return [n-bisect.bisect_right(ww, q) for q in qq]

1122. Relative Sort Array

按照数组2的相对位置给另一个数组排序。原题

方法一：和Lee神写法不谋而合，只不过自己用了乘法，其实加法就可以了。

1
2
3
def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
    index = {d: i for i, d in enumerate(arr2)}
    return sorted(arr1, key=lambda x: index.get(x, 1000+x))

1176. Diet Plan Performance

燃烧你的卡路里，卡路里和体重的关系。原题

1
2
3
4
5
Input: calories = [1,2,3,4,5], k = 1, lower = 3, upper = 3
Output: 0
Explanation: Since k = 1, we consider each element of the array separately and compare it to lower and upper.
calories[0] and calories[1] are less than lower so 2 points are lost.
calories[3] and calories[4] are greater than upper so 2 points are gained.
1
2
3
4
5
6
7
8
9
10
11
12
def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:
    ans = 0
    calories.insert(0, 0)
    cur_sum = sum(calories[:k])
    for i in range(1, len(calories)-k+1):
        cur_sum -= calories[i-1]
        cur_sum += calories[i+k-1]
        if cur_sum > upper:
            ans += 1
        elif cur_sum < lower:
            ans -= 1
    return ans

1395. Count Number of Teams

数字分组计数。原题

1
2
3
Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def numTeams(self, rating: List[int]) -> int:
    from collections import defaultdict
    n = len(rating)
    greater = defaultdict(int)
    less = defaultdict(int)
    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            if rating[i] > rating[j]:
                less[i] += 1
            else:
                greater[i] += 1
    
    for i in range(n-2):
        for j in range(i+1, n):
            if rating[i] > rating[j]:
                ans += less[j]
            else:
                ans += greater[j]
                
    return ans

1375. Bulb Switcher III

灯泡开关，记录灯泡全部变蓝的次数。原题

1
2
3
Input: light = [2,1,3,5,4]
Output: 3
Explanation: All bulbs turned on, are blue at the moment 1, 2 and 4.

方法一：使用堆。其实没必要增加O(n)的空间

1
2
3
4
5
6
7
8
9
10
def numTimesAllBlue(self, light: List[int]) -> int:
    import heapq as hq
    s = []
    hq.heapify(s)
    ans = 0
    for i, b in enumerate(light, 1):
        hq.heappush(s, -b)
        if -s[0] == i:
            ans += 1
    return ans
方法二：只需要维护一个最大值变量即可 
1
2
3
4
5
6
7
def numTimesAllBlue(self, light: List[int]) -> int:
    cur_max = ans = 0
    for i, b in enumerate(light, 1):
        cur_max = max(cur_max, b)
        if cur_max == i:
            ans += 1
    return ans
方法三：一行 
1
2
def numTimesAllBlue(self, light: List[int]) -> int:
    return sum(i==b for i, b in enumerate(itertools.accumulate(light, max), 1))

498. Diagonal Traverse

对角线z字形遍历。原题

方法一：费劲心思去找i,j的关系，其实只需要知道一点，i和j都是越来越大的就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
    if not matrix:
        return []
    dd = collections.defaultdict(list)
    ans = []
    m, n = len(matrix), len(matrix[0])
    for i in range(m):
        for j in range(n):
            dd[i+j].append(matrix[i][j])
    for k in range(m+n-1):
        if k % 2 == 0:
            dd[k].reverse()
        ans.extend(dd[k])
    return ans

1424. Diagonal Traverse II

对角线遍历，每行长度可能不一样。原题

1
2
3
4
5
6
7
8
def findDiagonalOrder(self, g: List[List[int]]) -> List[int]:
    res = []
    for i, r in enumerate(g):
        for j, a in enumerate(r):
            if len(res) <= i + j:
                res.append([])
            res[i + j].append(a)
    return [a for r in res for a in reversed(r)]

1365. How Many Numbers Are Smaller Than the Current Number

数组中比当前数小的个数。原题

方法一：排序。T=O(n*lgn)

1
2
3
4
5
def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
    indices = {}
    for i, d in enumerate(sorted(nums)):
        indices.setdefault(d, i)
    return [indices[d] for d in nums]

方法二：利用了数的范围在1~100之间。

1
2
3
4
5
6
def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
    count = [0] * 102
    for num in nums:
        count[num+1] += 1
    count = list(itertools.accumulate(count))
    return [count[num] for num in nums]

1366. Rank Teams by Votes

投票选举。首先按照排名，然后按照字母顺序。原题

1
2
3
4
5
6
7
8
9
10
Input: votes = ["ABC","ACB","ABC","ACB","ACB"]
Output: "ACB"
Explanation: Team A was ranked first place by 5 voters. No other team was voted as first place so team A is the first team.
Team B was ranked second by 2 voters and was ranked third by 3 voters.
Team C was ranked second by 3 voters and was ranked third by 2 voters.
As most of the voters ranked C second, team C is the second team and team B is the third.

Input: votes = ["WXYZ","XYZW"]
Output: "XWYZ"
Explanation: X is the winner due to tie-breaking rule. X has same votes as W for the first position but X has one vote as second position while W doesn't have any votes as second position.

方法一：列举了所有的票数，然后对tuple进行排序。

1
2
3
4
5
6
7
8
9
10
11
def rankTeams(self, votes: List[str]) -> str:
    from collections import Counter, defaultdict
    cc = defaultdict(lambda : [0]*26)
    i = 0
    for w in zip(*votes):
        for k, v in Counter(w).items():
            cc[k][i] = v
        i += 1
    # print(cc)
    cmp = (tuple(p) + (-ord(a), a) for a, p in cc.items())
    return ''.join(x[-1] for x in sorted(cmp, reverse=True))
方法二：忽略了一个问题，其实每个人都需要对所有人投票。根据第一个来进行初始化。数组同样可以比较大小，无须转化为tuple 
1
2
3
4
5
6
def rankTeams(self, votes: List[str]) -> str:
    count = {c: [0] * len(votes[0]) + [c] for c in votes[0]}
    for vote in votes:
        for i, v in enumerate(vote):
            count[v][i] -= 1
    return ''.join(sorted(votes[0], key=count.get))

1331. Rank Transform of an Array

将数组转化为排行。原题

1
2
3
Input: arr = [40,10,20,30]
Output: [4,1,2,3]
Explanation: 40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest.

方法一：setdefault的妙用。 by Lee215

1
2
3
4
5
def arrayRankTransform(self, arr: List[int]) -> List[int]:
    rank = {}
    for a in sorted(arr):
        rank.setdefault(a, len(rank)+1)
    return map(rank.get, arr)

1306. Jump Game III

跳跃游戏，从start开始，可以沿着value向前向后跳，求是否可以跳到0.原题

1
2
3
4
5
6
Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation: 
All possible ways to reach at index 3 with value 0 are: 
index 5 -> index 4 -> index 1 -> index 3 
index 5 -> index 6 -> index 4 -> index 1 -> index 3

方法一：Bfs.

1
2
3
4
5
6
7
8
9
10
11
def canReach(self, arr: List[int], start: int) -> bool:
    q, seen = collections.deque([start]), {start}
    while q:
        i = q.popleft()
        if arr[i] == 0:
            return True
        for nxt in (i-arr[i], i+arr[i]):
            if nxt not in seen and 0<=nxt<len(arr):
                q.append(nxt)
                seen.add(nxt)
    return False

方法二：数组中元素均为非负数，所以用负数来标记已经跳过的点。

1
2
3
4
5
def canReach(self, arr: List[int], i: int) -> bool:
    if 0<=i<len(arr) and arr[i]>=0:
        arr[i] = -arr[i]
        return arr[i]==0 or self.canReach(arr, i+arr[i]) or self.canReach(arr, i-arr[i])
    return False

1696. Jump Game VI

跳跃游戏，从数组开头跳跃到数组末尾，数组中元素可能包含负数，每次跳的距离为1~k，跳到哪里可以获得对应的分，问跳到最后最多能得多少分。

1
2
3
Input: nums = [1,-1,-2,4,-7,3], k = 2
Output: 7
Explanation: You can choose your jumps forming the subsequence [1,-1,4,3] (underlined above). The sum is 7.

方法一：比赛时只想到了O(n^2)的dp方法，啥也不是。这题用单调队里，维护一个最长为k的队列，队列中记录索引，有点像剑指offer中滑动窗口的最大值。

def maxResult(self, nums: List[int], k: int) -> int:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def maxResult(self, nums: List[int], k: int) -> int:
    n = len(nums)
    best = [nums[0]] + [-inf] * (n-1)
    q = deque([0])

    for i in range(1, n):
        while q and q[0] < i-k:
            q.popleft()
        best[i] = best[q[0]] + nums[i]
        # maintain the mono dec deque
        while q and best[q[-1]] <= best[i]:
            q.pop()
        q.append(i)

    return best[-1]

1297. Maximum Number of Occurrences of a Substring

出现次数最多的子串。滑动窗口可伸缩，最多包含maxLetters个字母。原题

1
2
3
def maxFreq(self, s: str, maxLetters: int, k: int, maxSize: int) -> int:
    c = collections.Counter(s[i:i+k] for i in range(len(s)-k+1))
    return max([n for sub, n in c.items() if len(set(sub)) <= maxLetters] + [0])

1291. Sequential Digits

按序求组区间中的顺子。原题

1
2
Input: low = 1000, high = 13000
Output: [1234,2345,3456,4567,5678,6789,12345]

方法一：开始时用的转化字符串的方式。不优雅，借鉴了他人解法。生成器有个好处是你可以暂时先不关心顺序。因为low>=10，所以一开始不会以9开头。

1
2
3
4
5
6
7
8
9
10
11
def sequentialDigits(self, low: int, high: int) -> List[int]:
    
    def gen(digit):
        num = digit
        while num <= high and digit < 10:
            if num >= low:
                yield num
            digit += 1
            num = num*10 + digit
            
    return sorted(num for i in range(1, 9) for num in gen(i))

1275. Find Winner on a Tic Tac Toe Game

三子棋的游戏，谁先连到3个子谁就赢。原题

1
2
3
4
5
6
Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"
Explanation: "A" wins, he always plays first.
"X  "    "X  "    "X  "    "X  "    "X  "
"   " -> "   " -> " X " -> " X " -> " X "
"   "    "O  "    "O  "    "OO "    "OOX"

方法一：这题是为数不多easy里面想了时间那么长的，除了暴力法没有想到什么思路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def tictactoe(self, moves: List[List[int]]) -> str:
    line = collections.defaultdict(list)
    for i, (x, y) in enumerate(moves):
        p = 'A' if i&1==0 else 'B' 
        xk, yk = 'x_{}'.format(x), 'y_{}'.format(y)
        line[xk].append(p)
        line[yk].append(p)
        if x == y:
            line['d_0'].append(p)
        if x + y == 2:
            line['d_1'].append(p)
        if any(len(l)==3 and len(set(l))==1 for l in (line[xk], line[yk], line['d_0'], line['d_1'])):
            return p
    return 'Draw' if len(moves) == 9 else 'Pending'
方法二：将A, B分为2组，这样比较时更简单一点。 
1
2
3
4
5
6
7
8
9
10
11
12
def tictactoe(self, moves: List[List[int]]) -> str:
    row, col = [[0] * 3 for _ in range(2)], [[0] * 3 for _ in range(2)]
    d1, d2, p = [0] * 2, [0] * 2, 0
    for r, c in moves:
        row[p][r] += 1
        col[p][c] += 1
        d1[p] += r==c
        d2[p] += r+c==2
        if 3 in (row[p][r], col[p][c], d1[p], d2[p]):
            return 'AB'[p]
        p ^= 1
    return 'Draw' if len(moves)==9 else 'Pending'

面试题 16.04. 井字游戏

比1275简单一点，给定棋盘，判断谁赢。

方法一：自己用if写的，评论有个正则的写法不错，学习一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
def tictactoe(self, board: List[str]) -> str:
    N = len(board)
    pattern = re.compile(r'^([XO])\1*$')
    col = map(''.join, zip(*board))
    l_dig = (''.join(board[i][i] for i in range(N))), 
    r_dig = (''.join(board[N-i-1][i] for i in range(N))), 
    for line in itertools.chain(board, col, l_dig, r_dig):
        match_obj = pattern.match(line)
        if match_obj:
            return match_obj.group(1)
    if ' ' in itertools.chain.from_iterable(board):
        return 'Pending'
    return 'Draw'

1260. Shift 2D Grid

2D滑动，每次列右移一次，首列下移一次。原题

1
2
Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[9,1,2],[3,4,5],[6,7,8]]

方法一：deque。最直观的方法。

1
2
3
4
5
6
7
def shiftGrid(self, g: List[List[int]], k: int) -> List[List[int]]:
    m, n = len(g), len(g[0])
    q = collections.deque(zip(*g))
    for _ in range(k):
        head = q.pop()
        q.appendleft(head[-1:]+head[:-1])
    return [a for a in zip(*q)]

方法二：调了半天，找了一些规律，然而并没有方法一快多少，时间上差不多，反而是更难理解了。

1
2
3
4
5
6
def shiftGrid(self, g: List[List[int]], k: int) -> List[List[int]]:
    m, n = len(g), len(g[0])
    mk = k % n
    a = list(zip(*g))
    a = a[-mk:] + a[:-mk]
    return zip(*[row[-((k//n+(i<mk))%m):] + row[:-((k//n+(i<mk))%m)] for i, row in enumerate(a)])
方法三：看来时间效率应该是差不多了，将数组转成一维，会发现规律。 
1
2
3
4
5
def shiftGrid(self, g: List[List[int]], k: int) -> List[List[int]]:
    col, nums = len(g[0]), sum(g, [])
    k = k % len(nums)
    nums = nums[-k:] + nums[:-k]
    return [nums[i:i+col] for i in range(0, len(nums), col)]

1252. Cells with Odd Values in a Matrix

根据坐标每次将所在的行和列+1，这个点+2，统计所有的奇数个数。原题

1
2
3
4
5
Input: n = 2, m = 3, indices = [[0,1],[1,1]]
Output: 6
Explanation: Initial matrix = [[0,0,0],[0,0,0]].
After applying first increment it becomes [[1,2,1],[0,1,0]].
The final matrix will be [[1,3,1],[1,3,1]] which contains 6 odd numbers.

方法一：异或。

1
2
3
4
5
6
def oddCells(self, n: int, m: int, indices: List[List[int]]) -> int:
    row, col = [0] * n, [0] * m
    for x, y in indices:
        row[x] ^= 1
        col[y] ^= 1
    return sum(r ^ c for r in row for c in col)

1248. Count Number of Nice Subarrays

找到包含k个奇数的子数组个数。原题

1
2
3
Input: nums = [1,1,2,1,1], k = 3
Output: 2
Explanation: The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].

方法一：找到所有的奇数索引，然后滑动窗口累加值。

1
2
3
4
5
6
7
8
9
def numberOfSubarrays(self, nums: List[int], k: int) -> int:
    n = len(nums)
    odd = [i for i, num in enumerate(nums) if num&1==1]
    ans = 0
    for i in range(len(odd)-k+1):
        pre = -1 if not i else odd[i-1]
        hi = n if i==len(odd)-k else odd[i+k]
        ans += (odd[i]-pre) * (hi-odd[i+k-1])
    return ans

方法二：遍历一次

1
2
3
4
5
6
7
8
9
10
11
12
def numberOfSubarrays(self, A: List[int], k: int) -> int:
    i = count = res = 0
    for j in range(len(A)):
        if A[j] & 1:
            k -= 1
            count = 0
        while k == 0:
            k += A[i] & 1
            i += 1
            count += 1
        res += count
    return res

1234. Replace the Substring for Balanced String

将每个QWER出现的次数变为一样，最少需要修改的子串长度是多少。原题

1
2
3
Input: s = "QQWE"
Output: 1
Explanation: We need to replace a 'Q' to 'R', so that "RQWE" (or "QRWE") is balanced.

方法一：例子有地不好，子串必须是连续的。和lee大佬解法差不多。

1
2
3
4
5
6
7
8
9
10
11
12
def balancedString(self, s: str) -> int:
    diff = Counter(s) - Counter({c: len(s)//4 for c in 'QWER'})
    ans = float('inf')
    c = Counter()
    i = 0
    for j, a in enumerate(s):
        c[a] += 1
        while i!=len(s) and not diff-c:
            ans = min(ans, j-i+1)
            c[s[i]] -= 1
            i += 1
    return ans

1208. Get Equal Substrings Within Budget

将字符串s变为t。需要ascii码的差，问在指定的差中，最长的可以变成的子串长度是多少。原题

1
2
3
Input: s = "abcd", t = "bcdf", maxCost = 3
Output: 3
Explanation: "abc" of s can change to "bcd". That costs 3, so the maximum length is 3.

方法一：滑动窗口问题。比赛的答案。

1
2
3
4
5
6
7
8
9
10
11
def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
    diff = [abs(ord(a)-ord(b)) for a, b in zip(s, t)]
    q = collections.deque()
    cur_sum = ans = 0
    for d in diff:
        q.append(d)
        cur_sum += d
        while cur_sum > maxCost:
            cur_sum -= q.popleft()
        ans = max(ans, len(q))
    return ans

方法二：Lee215，开始比较迷惑为什么i, j 不用max来求值，看了评论发现有人和我有一样的疑惑，并且给了解释，对于此题而言，滑动窗口的长度不会缩短。因为只用了if 而不是while

1
2
3
4
5
6
7
8
def equalSubstring(self, s: str, t: str, cost: int) -> int:
    i = 0
    for j in range(len(s)):
        cost -= abs(ord(s[j]) - ord(t[j]))
        if cost < 0:
            cost += abs(ord(s[i]) - ord(t[i]))
            i += 1
    return j - i + 1

Sort Colors

0,1,2的数组排序。原题

1
2
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

方法一：没想到有快排的思想。维持三个区间[0,i) [i,j),[j,k)分别表示0，1，2的区间。

1
2
3
4
5
6
7
8
9
10
11
def sortColors(self, nums: List[int]) -> None:
    i, j = 0, 0
    for k in range(len(nums)):
        v = nums[k]
        nums[k] = 2
        if v < 2:
            nums[j] = 1
            j += 1
        if v == 0:
            nums[i] = 0
            i += 1

1191. K-Concatenation Maximum Sum

求k*arr的连续数组最大和。原题

1
2
3
4
Input: arr = [1,2], k = 3
Output: 9
Input: arr = [1,-2,1], k = 5
Output: 2

方法一：想到了卡登算法，但是没想明白为啥要加(k-2)个数组的和，因为首位数组中间可以夹带(k-2)个数组，如果数组和是正数的话，就将它算进去

1
2
3
4
def kConcatenationMaxSum(self, arr: List[int], k: int, mod=10**9+7) -> int:
    def acc(nums):
        return max(accumulate(nums+[0], lambda x, y: x+y if x>0 else y))
    return ((k-2)*max(sum(arr), 0) + acc(arr*2)) % mod if k > 1 else acc(arr) % mod

448. Find All Numbers Disappeared in an Array

找出n长度的数组中1-n缺失的数字，有的数字会出现多次。原题

1
2
3
4
5
Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

方法一：这道题解法挺新颖，看着这题和剑指offer中的有点类似，但是那道题是其它数字出现一次。这个题的解法是出现的位置的数变成负的，最后找正数的索引。

1
2
3
4
5
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
    for i in range(len(nums)):
        index = abs(nums[i]) - 1
        nums[index] = -abs(nums[index])
    return [i+1 for i, num in enumerate(nums) if num>0]

11. Container With Most Water

最大的水容积，用坐标轴装水，有点像木桶原理。原题

方法一：双指针，开始没有想到指针如何移动。其实这样想，如果一个坐标比较矮，那就将其舍弃，因为宽度是越来越小的，所以需要更高的木桶才能弥补。

def maxArea(self, height: List[int]) -> int:
    lo, hi = 0, len(height)-1
    ans = 0
    while lo < hi:
        ans = max(ans, (hi-lo)*min(height[hi], height[lo]))
        if height[lo] < height[hi]:
            lo += 1
        else:
            hi -= 1
    return ans

1498. Number of Subsequences That Satisfy the Given Sum Condition

给定一个数组，返回最大值最小值和小于目标值的子序列，可以不连续，的个数。原题

1
2
3
4
5
6
7
Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

方法一：一开始思路相对了，但是指针移动没想好。来自Lee215，累加的时候要计算一下mod否则效率会变很慢。

1
2
3
4
5
6
7
8
9
10
11
def numSubseq(self, nums: List[int], target: int) -> int:
    nums.sort()
    lo, hi = 0, len(nums)-1
    res = 0
    while lo <= hi:
        if nums[lo] + nums[hi] > target:
            hi -= 1
        else:
            res += pow(2, hi - lo, 10**9+7)
            lo += 1
    return res % (10**9+7)

463. Island Perimeter

小岛的周长，小岛中间没有湖。原题

1
2
3
4
5
6
7
Input:
[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]

Output: 16

方法一：stefan、因为中间没有湖，所以呢周长等于所以相邻格子不相等的个数。这里将列也放在一起计算了

1
2
3
def islandPerimeter(self, grid: List[List[int]]) -> int:
    cols = list(map(list, zip(*grid)))
    return sum(sum(map(ne, [0]+row, row+[0])) for row in grid + cols)

15. 3Sum

找出数组中3个数相加为0，返回所有的组合非重复。原题

1
2
3
4
5
6
7
Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

方法一：这里看了提示后用的2sum的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def threeSum(self, nums: List[int]) -> List[List[int]]:
    nums.sort()
    ans = []
    seen = set()
    n = len(nums)
    for i in range(n):
        a = nums[i]
        if a in seen:
            continue
        seen.add(a)
        d = {}
        for j in range(i+1, n):
            b = nums[j]
            if b in d and (not(ans) or (ans[-1][0]!=a or ans[-1][2]!=b)):
                ans.append((a, -a-b, b))
            else:
                d[-a-b] = 0
    return ans

方法二：讨论区看到的一个方法。明白了还有许多可以优化的地方。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def threeSum(self, nums: List[int]) -> List[List[int]]:
    nums.sort()
    ans, n = [], len(nums)
    for i in range(n-2):
        a = nums[i]
        if a > 0:
            break # 因为a>0, b,c>0，所以不可能和为0
        if i and a == nums[i-1]:
            continue
        lo, hi = i+1, n-1
        while lo < hi:
            total = nums[lo] + nums[hi]
            if total > -a:
                hi -= 1
            elif total < -a:
                lo += 1
            else:
                while lo<hi and nums[lo]==nums[lo+1]:
                    lo += 1
                while lo<hi and nums[hi]==nums[hi-1]:
                    hi -= 1
                ans.append((a, nums[lo], nums[hi]))
                lo += 1
                hi -= 1
    return ans

1508. Range Sum of Sorted Subarray Sums

数组的累加和排序，取区间中的数字和。原题

1
2
3
Input: nums = [1,2,3,4], n = 4, left = 1, right = 5
Output: 13 
Explanation: All subarray sums are 1, 3, 6, 10, 2, 5, 9, 3, 7, 4. After sorting them in non-decreasing order we have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 1 to ri = 5 is 1 + 2 + 3 + 3 + 4 = 13.

方法一：O(n^2)的方法。比赛的时候还用了accumulate， 但是其实没必要。

1
2
3
4
5
6
7
8
9
10
11
def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
    mod = 10**9 + 7
    n = len(nums)
    ans = []
    for i in range(n):
        cur = 0
        for j in range(i, n):
            cur += nums[j]
            ans.append(cur)
    ans.sort()
    return sum(ans[left-1: right]) % mod

1509. Minimum Difference Between Largest and Smallest Value in Three Moves

删除3个数，数组的最大值最小值差最小是多少。原题

方法一：首次ac的方法。思路很直观，但是写法却有点复杂。

1
2
3
4
5
6
7
8
9
10
11
def minDifference(self, nums: List[int]) -> int:
    nums.sort()
    n = len(nums)
    if n <= 3:
        return 0
    # print(nums)
    ans = float('inf')
    for i in range(4):
        tmp = nums[i:n-3+i]
        ans = min(ans, max(tmp) - min(tmp))
    return ans
方法二：2行就可以搞定。 
1
2
3
def minDifference(self, nums: List[int]) -> int:
    nums.sort()
    return min(b-a for a, b in zip(nums[:4], nums[-4:]))
方法三：堆求也可以。 
1
2
3
def minDifference(self, nums: List[int]) -> int:
    nums.sort()
    return min(a - b for a,b in zip(heapq.nlargest(4, nums), heapq.nsmallest(4, nums)[::-1]))

1529. Bulb Switcher IV

灯泡开关，每次只能开关从后开始的连续的n个，问变成目标状态，最少需要几次操作。原题

1
2
3
4
5
6
7
Input: target = "10111"
Output: 3
Explanation: Initial configuration "00000".
flip from the third bulb:  "00000" -> "00111"
flip from the first bulb:  "00111" -> "11000"
flip from the second bulb:  "11000" -> "10111"
We need at least 3 flip operations to form target.

方法一：竞赛时的方法。 分组。

1
2
3
4
5
6
7
8
9
10
def minFlips(self, target: str) -> int:
    ans = 0
    first = True
    for l, g in itertools.groupby(target):
        if l == '0' and first:
            continue
        else:
            ans += 1
        first = False
    return ans
方法二：上诉方法补0 优化。 
1
2
def minFlips(self, target: str) -> int:
    return len(list(itertools.groupby('0' + target))) - 1
方法三：不分组，一次遍历。 
1
2
3
4
5
6
7
def minFlips(self, target: str) -> int:
    ans, b = 0, 1
    for c in target:
        if int(c) == b:
            ans += 1
            b = 1 - b
    return ans

442. Find All Duplicates in an Array

找到所有重复的元素，数组中的元素都在1~n之间，n为数组的长度。原题

方法一：要求在O(n)时间，O(1)空间实现，那么就考虑修改原数组来节省空间。以负值来记录是否出现过。

1
2
3
4
5
6
7
8
def findDuplicates(self, nums: List[int]) -> List[int]:
    res = []
    for x in nums:
        if nums[abs(x)-1] < 0:
            res.append(abs(x))
        else:
            nums[abs(x)-1] *= -1
    return res

713. Subarray Product Less Than K

连续子数组乘积小于k的个数，元素为正数。原题

1
2
3
4
Input: nums = [10, 5, 2, 6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6].
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

方法一：一开始想到了双端队列，但是累加时end-start+1数量没想到。此题用双指针即可

1
2
3
4
5
6
7
8
9
10
11
12
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
    if k == 0:
        return 0
    start = ans = 0
    prod = 1
    for end, num in enumerate(nums):
        while start<=end and prod*num>=k:
            prod //= nums[start]
            start += 1
        prod = 1 if start>end else prod*num
        ans += (end-start+1) * (start<=end)
    return ans

915. Partition Array into Disjoint Intervals

将数组拆成两个非空数组，要求左侧的每个元素都小于等于右侧的每个元素，求左侧最小的长度，假设答案一定存在。原题

1
2
3
Input: [5,0,3,8,6]
Output: 3
Explanation: left = [5,0,3], right = [8,6]

方法一：蛮简单的，two-pass的方法，这个累加函数的生成器不能直接reversed，要将其转换成数组，这里产生了一次遍历。

1
2
3
4
5
6
7
def partitionDisjoint(self, A: List[int]) -> int:
    left = itertools.accumulate(A, max)
    right = reversed(list(itertools.accumulate(reversed(A), min)))
    next(right, None)
    for i, (a, b) in enumerate(zip(left, right)):
        if a <= b:
            return i + 1
方法二：one-pass. 这个方法不是很好想，思路是这样的，当当前数小于之前的最大值，那么久将其算入左侧的数组中。 
1
2
3
4
5
6
7
8
9
def partitionDisjoint(self, A: List[int]) -> int:
    p = 0
    cur_max = left_max = A[0]
    for i, a in enumerate(A):
        cur_max = max(cur_max, a)
        if a < left_max:
            left_max = cur_max
            p = i
    return p + 1

1562. Find Latest Group of Size M

将一个全是0的字符串按照arr的索引顺序变为1，整体被0分割成若干段，问最后有m个长度的”1”的段时是第几步、原题

1
2
3
4
5
6
7
8
9
Input: arr = [3,5,1,2,4], m = 1
Output: 4
Explanation:
Step 1: "00100", groups: ["1"]
Step 2: "00101", groups: ["1", "1"]
Step 3: "10101", groups: ["1", "1", "1"]
Step 4: "11101", groups: ["111", "1"]
Step 5: "11111", groups: ["11111"]
The latest step at which there exists a group of size 1 is step 4.

方法一：比赛时没做出来，Lee的方法。length表示第i个bit的长度，count表示这么长的group有多少个。严格来说length[a-left]和lenght[a+right]区间内都应该变成left+right+1。但是由于中间的后续用不到，所以不必赋值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def findLatestStep(self, arr: List[int], m: int) -> int:
    length = [0] * (len(arr)+2)
    count = [0] * (len(arr)+1)
    ans = -1
    for i, a in enumerate(arr):
        left, right = length[a-1], length[a+1]
        length[a] = length[a-left] = length[a+right] = left + right + 1
        count[left] -= 1
        count[right] -= 1
        count[length[a]] += 1
        # print(length, count)
        if count[m]:
            ans = i + 1
    return ans

334. Increasing Triplet Subsequence

数组中是否有三个元素递增。原题

1
2
3
4
Input: [1,2,3,4,5]
Output: true
Input: [1,5,3,4,2]
Output: true

方法一：首次ac的方法，看了要求在O(n)时间O(1)空间实现。

1
2
3
4
5
6
7
def increasingTriplet(self, nums: List[int]) -> bool:
    a = b = float('inf')
    for num in nums:
        if num > b: return True
        a = min(a, num)
        if a<num<b: b=num
    return False
方法二：这个stefan的方法，具有泛化性，如果求4，5个元素递增可以直接修改变量。 
1
2
3
4
5
6
7
inc = [float('inf')] * 2
    for x in nums:
        i = bisect.bisect_left(inc, x)
        if i >= 2:
            return True
        inc[i] = x
    return False

926. Flip String to Monotone Increasing

将一个二进制字符串翻转成单调递增最少要几步。原题

1
2
3
Input: "010110"
Output: 2
Explanation: We flip to get 011111, or alternatively 000111.

方法一：看了一眼讨论区，就明白了，遍历时找到递增的点，也就是第一个1，记录后边的0和前边的1。这里我是在后面补1，也可以将ans初始化为len(S)-suffix_0。

1
2
3
4
5
6
7
8
9
10
11
def minFlipsMonoIncr(self, S: str) -> int:
    S += '1'
    suffix_0, prefix_1 = S.count('0'), 0
    ans = float('inf')
    for c in S:
        if c == '0':
            suffix_0 -= 1
        else:
            ans = min(ans, suffix_0+prefix_1)
            prefix_1 += 1
    return ans

424. Longest Repeating Character Replacement

由26个大写字母组成的字符串，在k次替换范围内，产生的最长的重复字符串是多少。原题

1
2
3
4
5
6
7
8
Input:
s = "ABAB", k = 2

Output:
4

Explanation:
Replace the two 'A's with two 'B's or vice versa.

方法一：滑动窗口加数组计数。time- O(26N)。while是没有必要的，left+1后 左边等号就会刚好=k, 不过这里的left, right表示的区间意义变了，表示的是最大的滑动窗口，窗口内的字符串不一定是可以满足条件的。

1
2
3
4
5
6
7
8
9
10
11
def characterReplacement(self, s: str, k: int) -> int:
    cnt = [0] * 26
    left = ans = 0
    for right, d in enumerate(s):
        cnt[ord(d)-ord('A')] += 1
        # while right-left+1-max(cnt) > k:
        if right-left+1-max(cnt) > k:
            cnt[ord(s[left])-ord('A')] -= 1
            left += 1
        ans = max(ans, right-left+1)
    return ans

方法二：研究了很久也没弄明白，为什么maxf曾经最大的值，可以替代max(cnt)。理论上时间确实比上述快了。Time-O(N)。我试了一个特殊的例子，”BBBCADEF”1，在某些情况maxf > max(cnt)的，但即便这样也没有影响if判断，猜测可能为right-left+1区间为最大区间。不过又将if改成while循环，依然没有影响。此解法还是有些疑惑。

1
2
3
4
5
6
7
8
9
10
11
12
13
def characterReplacement(self, s: str, k: int) -> int:
    cnt = [0] * 26
    left = ans = maxf = 0
    for right, d in enumerate(s):
        cnt[ord(d)-ord('A')] += 1
        maxf = max(maxf, cnt[ord(d)-ord('A')])
        # while right-left+1-max(cnt) > k:
        # print(maxf, max(cnt), left, right, ans)
        if right-left+1-maxf > k:
            cnt[ord(s[left])-ord('A')] -= 1
            left += 1
        ans = max(ans, right-left+1)
    return ans

398. Random Pick Index

有这样一个数组，我想随机的去一个目标的元素，找到和目标相等的这些元素随机返回一个索引。原题

1
2
3
4
5
6
7
8
int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);

// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);

方法一：直接放到defaultdict中也没有超过空间限制。

1
2
3
4
5
6
7
8
9
class Solution:

    def __init__(self, nums: List[int]):
        self.p = collections.defaultdict(list)
        for i, d in enumerate(nums):
            self.p[d].append(i)

    def pick(self, target: int) -> int:
        return random.choice(self.p[target])

方法二：一个新的方法叫作蓄水池取样，当遇见了一个目标数，就将它放到池子中，然后随机一个数。并在随到当前数时更新索引。

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

    def __init__(self, nums: List[int]):
        self.nums = nums
        
    def pick(self, target: int) -> int:
        ans = None
        count = 0
        for i, num in enumerate(self.nums):
            if num == target:
                count += 1
                chance = random.randint(1, count)
                if chance == count:
                    ans = i
        return ans

382. Linked List Random Node

在一个链表上随机取一个节点值。原题

方法一：和398一样。假设链表无限大，不能够获取它的长度。这是非常经典的一个题。一个很大的数据流，对数据流的内容只能访问一次，随机算法使数据流中所有的被选中的概率相等。

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

    def __init__(self, nums: List[int]):
        self.nums = nums
        
    def pick(self, target: int) -> int:
        ans = None
        count = 0
        for i, num in enumerate(self.nums):
            if num == target:
                count += 1
                chance = random.randint(1, count)
                if chance == count:
                    ans = i
        return ans

209. Minimum Size Subarray Sum

累加和大于s的最短的子数组长度。原题

1
2
3
Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

方法一：滑动窗口。注意A为空的情况。

1
2
3
4
5
6
7
8
9
def minSubArrayLen(self, s: int, A: List[int]) -> int:
    i, ans = 0, len(A)+1
    for j in range(len(A)):
        s -= A[j]
        while s <= 0:
            ans = min(ans, j-i+1)
            s += A[i]
            i += 1
    return ans % (len(A)+1)

930. Binary Subarrays With Sum

求和我S的子数组个数，数组元素只包含0，1。原题

1
2
3
4
5
6
7
8
Input: A = [1,0,1,0,1], S = 2
Output: 4
Explanation: 
The 4 subarrays are bolded below:
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]

方法一：这种题要求at_most. 滑动窗口，用和小于等于S的子数组个数减去小于等于S-1的子数组个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def numSubarraysWithSum(self, A: List[int], S: int) -> int:
    
    def at_most(S):
        if S < 0: return 0
        res = i = 0
        for j in range(len(A)):
            S -= A[j]
            while S < 0:
                S += A[i]
                i += 1
            res += j-i+1
        return res
    
    return at_most(S) - at_most(S-1)

969. Pancake Sorting

煎饼排序。由1~n组成，没次只能reverse前k个，求k的数组，答案不唯一。原题

1
2
3
4
5
6
7
8
9
10
Input: A = [3,2,4,1]
Output: [4,2,4,3]
Explanation: 
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: A = [3, 2, 4, 1]
After 1st flip (k = 4): A = [1, 4, 2, 3]
After 2nd flip (k = 2): A = [4, 1, 2, 3]
After 3rd flip (k = 4): A = [3, 2, 1, 4]
After 4th flip (k = 3): A = [1, 2, 3, 4], which is sorted.
Notice that we return an array of the chosen k values of the pancake flips.

方法一：例子中的做法不是很好，只需要每次找最大的，然后翻到首位，然后再全翻转使其到达末尾。

1
2
3
4
5
6
7
8
9
10
11
def pancakeSort(self, A: List[int]) -> List[int]:
    ans, n = [], len(A)
    for i in range(n, -1, -1):
        if A[i] != i+1:
            j = A.index(i+1)
            if j:
                ans.append(j+1)
                A = A[:j+1][::-1] + A[j+1:]
            ans.append(i+1)
            A = A[:i+1][::-1] + A[i+1:]
    return ans
方法二：Lee的方法，这种方法把1也放进去了。其实是无所谓的。 
1
2
3
4
5
6
7
def pancakeSort(self, A: List[int]) -> List[int]:
    ans, n = [], len(A)
    for x in range(n, 1, -1):
        i = A.index(x)
        ans.extend((i+1, x))
        A = A[:i:-1] + A[:i]
    return ans

1566. Detect Pattern of Length M Repeated K or More Times

判断数组中是否有k次以上个重复的M大小的组。原题

1
2
3
Input: arr = [1,2,4,4,4,4], m = 1, k = 3
Output: true
Explanation: The pattern (4) of length 1 is repeated 4 consecutive times. Notice that pattern can be repeated k or more times but not less.

方法一：暴力。

1
2
3
4
5
6
7
8
9
10
def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
    n = len(arr)
    for i in range(n):
        end = i + m*k
        if end > n: return False
        tmp = arr[i:i+m]
        # if all(arr[i+m*j:i+m*j+m] == tmp for j in range(1, k)):
        if arr[i:i+m*k] == tmp*k:
            return True
    return False
方法二：这个方法挺难想，为什么是(k-1)*m因为第一个用来比较，不算在内，如果在达到之前有一个不相等，则归零。 
1
2
3
4
5
6
def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
    streak = 0
    for i in range(len(arr)-m):
        streak = streak + 1 if arr[i] == arr[i+m] else 0
        if streak == (k-1)*m: return True
    return False

228. Summary Ranges

格式化一段range。原题

1
2
3
Input:  [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: 0,1,2 form a continuous range; 4,5 form a continuous range.

方法一：很简单，记录这题主要是学到了一个新的写法。先贴自己的解法。

1
2
3
4
5
6
7
8
9
10
def summaryRanges(self, nums: List[int]) -> List[str]:
    stack = []
    for d in nums:
        if not stack or stack[-1][-1]+1<d:
            stack.append([d])
        else:
            if len(stack[-1]) == 2:
                stack[-1].pop()
            stack[-1].append(d)
    return ['->'.join(map(str, p)) for p in stack]

方法二：stefan的写法。[][1:] = 1,数组会变成[1]。

1
2
3
4
5
6
7
def summaryRanges(self, nums: List[int]) -> List[str]:
    stack = []
    for d in nums:
        if not stack or stack[-1][-1]+1<d:
            stack.append([])
        stack[-1][1:] = d, 
    return ['->'.join(map(str, p)) for p in stack]

769. Max Chunks To Make Sorted

可以将一个数组分成几块小数组，然后使每个小数组排序后连接起来，整个大数组有序，问最多可以分成多少块。原题

1
2
3
4
5
Input: arr = [1,0,2,3,4]
Output: 4
Explanation:
We can split into two chunks, such as [1, 0], [2, 3, 4].
However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.

方法一：直白来看，如果某一段包含了排序后应该有的所有的数，那么久将其分成一段。

1
2
3
4
5
6
7
8
def maxChunksToSorted(self, arr: List[int]) -> int:
    ans, n = 0, len(arr)
    start = 0
    for end in range(1, n+1):
        if sorted(arr[start:end]) == list(range(start, end)):
            ans += 1
            start = end
    return ans
方法二：Lee的方法。当max(A[0]~A[i])==i时分割，其中包含了一个原理，如果更大的数参入到之前的段中，最大值就会更新，想要在某点和索引相等，就必须将比它小的数全找到。 
1
2
3
4
5
6
def maxChunksToSorted(self, arr: List[int]) -> int:
    cur_max, ans = -1, 0
    for i, num in enumerate(arr):
        cur_max = max(num, cur_max)
        ans += cur_max==i
    return ans

390. Elimination Game

消除游戏，从1~n的数组，每次从左到右隔一个删除，然后从右到左隔一个删除。最后剩下一个数字是哪个。原题

1
2
3
4
5
6
7
8
9
Input:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6

Output:
6

方法一：在用切片方法发现n能到1亿时，超时了；然后想到其实只需要控制一个范围即可。每次操作后，数组中的等差变为原来的2倍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def lastRemaining(self, n: int) -> int:
    start, end, d = 1, n, 1
    op = 1
    while start < end:
        # print(start, end, d, op)
        num = (end-start)//d + 1
        if op:
            start += d
            end -= (num&1) * d
        else:
            start += (num&1) * d
            end -= d
        op ^= 1
        d *= 2
    return start
方法二：整理代码。end其实无用，用一个num表示剩余的数字个数。 
1
2
3
4
5
6
7
8
9
def lastRemaining(self, n: int) -> int:
    start = d = left = 1
    num = n
    while num > 1:
        start += (left or (num&1)) * d
        left ^= 1
        d *= 2
        num //= 2
    return start

853. Car Fleet

超车车队，说有这么一些车向同一个目的地出发，起始位置和速度不同，当快车遇见慢车时不能超过，而是跟在后面变成一个车队。问最后到达终点时有几个车队，1辆车也算一个车队。原题

1
2
3
4
5
6
7
Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
The cars starting at 10 and 8 become a fleet, meeting each other at 12.
The car starting at 0 doesn't catch up to any other car, so it is a fleet by itself.
The cars starting at 5 and 3 become a fleet, meeting each other at 6.
Note that no other cars meet these fleets before the destination, so the answer is 3.

方法一：思路很快想出来了，就是排序，但是根据什么排序，怎么比较想了半天。问题出在这个例子上：10, [0,4,2],[2,1,3]这个排序后时[(4, 6), (2, 2.6), (0, 5)]，以起始点位置排序，当一个时间小于等于之前的时间时，那么这辆车就能追上之前的，变成一个车队；反之，则形成一个单独的车队。这个“之前的时间”指的不是挨着的前面的一个时间，而是之前最慢的一个车。也就是时间最大的。

1
2
3
4
5
6
7
8
def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
    cars = ((target-p)/s for p, s in sorted(zip(position, speed), reverse=True))
    ans = cur_t = 0
    for t in cars:
        if t > cur_t:
            cur_t = t
            ans += 1
    return ans

1574. Shortest Subarray to be Removed to Make Array Sorted

删除一个最短的子数组使整个数组有序。问最短数组长度为多少。原题

1
2
3
4
Input: arr = [1,2,3,10,4,2,3,5]
Output: 3
Explanation: The shortest subarray we can remove is [10,4,2] of length 3. The remaining elements after that will be [1,2,3,3,5] which are sorted.
Another correct solution is to remove the subarray [3,10,4].

方法一：这个题竞赛时没做出来，只想到从左到右找坏的点，没想到从右到左也需要找一次。而且找完之后，要控制两个指针，从0和j出发遍历，自己想的是从中间往两边遍历。边界条件非常多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
    n = len(arr)
    i = 0
    while i+1<n and arr[i]<=arr[i+1]: i += 1
    if i == n-1: return 0
        
    j = n-1
    while j > i and arr[j-1] <= arr[j]: j -= 1

    if j == 0: return n-1
    ans = min(n-i-1, j)
    left = 0
    right = j
    while left <= i and right < n:
        if arr[right] >= arr[left]:
            ans = min(ans, right-left-1)
            left += 1
        else:
            right += 1
    return ans

835. Image Overlap

图片覆盖。两个二维矩阵，A可以向一个方向滑动N个单位，然后放到B上，如果都为1，则表示某个像素是覆盖的。求最多有多少个像素覆盖。原题

1
2
3
4
5
6
7
8
Input: A = [[1,1,0],
            [0,1,0],
            [0,1,0]]
       B = [[0,0,0],
            [0,1,1],
            [0,0,1]]
Output: 3
Explanation: We slide A to right by 1 unit and down by 1 unit.

方法一：逆向思维，将1的点都求出来，然后每两个做比较。相同偏移量的算到一起。

def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
    A = [(x, y) for x, row in enumerate(A) for y, d in enumerate(row) if d]
    B = [(x, y) for x, row in enumerate(B) for y, d in enumerate(row) if d]
    c = Counter((xa-xb, ya-yb) for xa, ya in A for xb, yb in B)
    return max(c.values() or [0])

方法二：数学的降维打击。卷积。其中涉及到了一些数学知识还没有完全参透。

1
2
3
4
5
6
import numpy as np
from scipy.signal import convolve2d

class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        return np.max(convolve2d(A, np.rot90(B, 2)))
1
2
3
4
5
from scipy.signal import correlate2d

class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        return correlate2d(A, B).max()

42. Trapping Rain Water

接雨水。给定一些柱状图的高度，问能接多少雨水。原题

方法一：用了逆向思维，通过总面积-损失的水-柱体面积求的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def trap(self, height: List[int]) -> int:
    if not height: return 0
    h_max, n = max(height), len(height)
    
    def get_lost(heights, target):
        cur_h = lost = 0
        for i, h in enumerate(heights):
            lost += max(h-cur_h, 0) * i   
            cur_h = max(cur_h, h)
            if h == target:
                break
        return lost
    
    lost = get_lost(height, h_max) + get_lost(height[::-1], h_max)
    return n*h_max - lost - sum(height)
方法二：遍历一次，其实思路是一样的，从两边到中间，当遇见一次下降时，计算差值面积，就是蓄水面积。left_max, right_max可以看做是两面墙。 
1
2
3
4
5
6
7
8
9
10
11
12
13
def trap(self, height: List[int]) -> int:
    left, right = 0, len(height)-1
    ans = left_max = right_max = 0
    while left < right:
        left_max = max(left_max, height[left])
        right_max = max(right_max, height[right])
        if left_max < right_max:
            ans += left_max - height[left]
            left += 1
        else:
            ans += right_max - height[right]
            right -= 1
    return ans

36. Valid Sudoku

验证一个数独的正确性，只需要考虑填入数字的格子。原题

方法一：比较直观的写法。

1
2
3
4
5
6
7
8
9
10
11
12
def isValidSudoku(self, board: List[List[str]]) -> bool:
    row = [[True]*9 for i in range(9)]        
    col = [[True]*9 for i in range(9)]
    sub = [[True]*9 for i in range(9)]
    for i in range(9):
        for j in range(9):
            if board[i][j] != '.':
                d = int(board[i][j]) - 1
                if not (row[i][d] and col[j][d] and sub[i//3*3+j//3][d]):
                    return False
                row[i][d] = col[j][d] = sub[i//3*3+j//3][d] = False
    return True
方法二：Counter, by Stefan. 记录3种元素，如果有重复的 就说明不行。这里和python2有个区别，原来是用的+，python3中字典的values()方法返回的是一个dict_values的对象。 
1
2
3
4
5
6
7
def isValidSudoku(self, board: List[List[str]]) -> bool:
    return 1 == max(collections.Counter(
        x for i, row in enumerate(board)
        for j, c in enumerate(row)
        if c != '.'
        for x in ((c, i), (j, c), (i//3, j//3, c))
    ).values() or [1])
方法三：同样来自Stefan，这个方法很有趣，将判断放到了生成器中。 
1
2
3
4
5
6
7
def isValidSudoku(self, board: List[List[str]]) -> bool:
    seen = set()
    return not any(x in seen or seen.add(x)
                   for i, row in enumerate(board)
                   for j, c in enumerate(row)
                   if c != '.'
                   for x in ((c, i), (j, c), (i//3, j//3, c)))

1054. Distant Barcodes

分散的条形码，就是将一个数组中的元素重新排序，让其没有两个一样的相邻。原题

方法一：我首次AC的方法就是用堆，取出一个或者2个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
    c = Counter(barcodes)
    heap = []
    ans = []
    for k, v in c.items():
        heapq.heappush(heap, (-v, k))
    while heap:
        most, d1 = heapq.heappop(heap)
        if ans and ans[-1]==d1:
            more, d2 = heapq.heappop(heap)
            ans.append(d2)
            if more < -1:
                heapq.heappush(heap, (more+1, d2))
            heapq.heappush(heap, (most, d1))
            continue
        ans.append(d1)
        if most < -1:
            heapq.heappush(heap, (most+1, d1))
    return ans
方法二：by Lee, 将最多的数字，按索引分割依次插入。 
1
2
3
4
5
6
7
8
9
def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
    i, n = 0, len(barcodes)
    ans = [0] * n
    for k, v in collections.Counter(barcodes).most_common():
        for _ in range(v):
            ans[i] = k
            i += 2
            if i >= n: i = 1
    return ans
方法三：by Lee，看到方法二时就想到了，这里需要注意一下，排序时要用一个元组，将一样的元素放到一起。 
1
2
3
4
5
def rearrangeBarcodes(self, a: List[int]) -> List[int]:
    count = collections.Counter(a)
    a.sort(key=lambda x: (count[x], x))
    a[1::2], a[::2] = a[:len(a)//2], a[len(a)//2:]
    return a

1588. Sum of All Odd Length Subarrays

求所有奇数长度的子数组的和。

方法一：这题给的范围比较小，竞赛时用O(n^2)暴力就解了，不过实际有O(n)的方法。通过前缀和的方式，累加，再通过减法算和。比如[1,4,2,5,3]。j-i表示的是子数组的长度。

1
2
3
4
5
6
7
8
def sumOddLengthSubarrays(self, arr: List[int]) -> int:
    n, sum_odd = len(arr), 0
    p_sum = [0] + list(itertools.accumulate(arr))
    for i, p in enumerate(p_sum):
        for j in range(i + 1, n + 1, 2):
            # print(i, j, p_sum[j], p_sum[i])
            sum_odd += p_sum[j] - p_sum[i] 
    return sum_odd
1
2
3
4
5
6
7
8
9
0 1 1 0
0 3 7 0
0 5 15 0
1 2 5 1
1 4 12 1
2 3 7 5
2 5 15 5
3 4 12 7
4 5 15 12

方法二：通过观察可以找到规律，每个数字出现的个数是有规律的。

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

5 8 9 8 5 total times each index was added.
3 4 5 4 3 total times in odd length array with (x + 1) / 2
2 4 4 4 2 total times in even length array with x / 2
方法二：在所有子数组中，不管奇偶总共有多少，比如包含2的子数组，左边有2个子数组，右边4个子数组，一共有24，也就是说

对于第i个元素，包含第i个元素的子数组=`(i+1) (n-i)奇数数组(x+1)//2`, x表示总数。 
1
2
3
4
5
def sumOddLengthSubarrays(self, arr: List[int]) -> int:
    ans, n = 0, len(arr)
    for i, a in enumerate(arr):
        ans += (((i+1)*(n-i) + 1) // 2) * a
    return ans

面试题 16.22. 兰顿蚂蚁

兰顿蚂蚁（英语：Langton’s ant）是细胞自动机的例子。它由克里斯托夫·兰顿在1986年提出，它由黑白格子和一只“蚂蚁”构成[1]，是一个二维图灵机。兰顿蚂蚁拥有非常简单的逻辑和复杂的表现。在2000年兰顿蚂蚁的图灵完备性被证明。兰顿蚂蚁的想法后来被推广，比如使用多种颜色。

若从全白的背景开始，在一开始的数百步，蚂蚁留下的路线会出现许多对称或重复的形状，然后会出现类似混沌的假随机，至约一万步后会出现以104步为周期无限重复的“高速公路”朝固定方向移动[2]。在目前试过的所有起始状态，蚂蚁的路线最终都会变成高速公路，但尚无法证明这是无论任何起始状态都会导致的必然结果[3]。

这道题非常有意思。一只蚂蚁坐在由白色和黑色方格构成的无限网格上。开始时，网格全白，蚂蚁面向右侧。每行走一步，蚂蚁执行以下操作。返回能够包含蚂蚁走过的所有方格的最小矩形。

(1) 如果在白色方格上，则翻转方格的颜色，向右(顺时针)转 90 度，并向前移动一个单位。
(2) 如果在黑色方格上，则翻转方格的颜色，向左(逆时针方向)转 90 度，并向前移动一个单位

方法一：刚看到此题时草率了，还想找到规律，后来一搜，原来在一万步之后才会出现某种规律，打扰了。此方法用了一个二维的双端队列模拟的。700ms, 40。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def printKMoves(self, K: int) -> List[str]:
    ax, ay = 0, 0  # 蚂蚁🐜
    di, dj, m, n = 0, 1, 1, 1  # 方向和矩阵高，长
    g = deque([deque([0])])  # 0 表示白色
    for k in range(K):
        if g[ax][ay]==0:
            di, dj = dj, -di  # 顺时针
        else:
            di, dj = -dj, di  # 逆时针
        g[ax][ay] ^= 1        # 翻转
        ax, ay = ax+di, ay+dj   # 移动
        if ax in (-1, m):       # 上下越界
            g.append(deque([0]*n))
            g.rotate(ax<0)       # 上越界，直接appendleft也可以，这里写到了一起
            m += 1
            ax = max(ax, 0)
        elif ay < 0:
            for row in g:
                row.appendleft(0)            
            n += 1
            ay += 1
        elif ay >= n:
            for row in g:
                row.append(0)
            n += 1
    g[ax][ay] = -1
    d = (('LR', 'UD')[di][(dj>=0)&(di>=0)])  # 阴间写法
    # d = {(0, -1): 'L', (-1, 0): 'U', (1, 0): 'D', (0, 1): 'R'}[di, dj] # 阳间写法
    ans = [''.join(('_X'+d)[c] for c in row) for row in g]
    return ans

方法二：受评论区大神启发，使用defaultdict来避免每次都移动数组。写法是不错，但是时间和空间上都比方法一差太多，时间是3，4倍，空间是10倍。所以我改了一下改成两个defaultdict，时间上虽然还是不如方法一，但是时间空间都好了一半。最后是1500ms, 240M。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def printKMoves(self, K: int) -> List[str]:
    ax, ay = 0, 0  # 蚂蚁🐜
    di, dj, m, n = 0, 1, 1, 1  # 初始方向和矩阵高，长
    g = defaultdict(lambda: defaultdict(int))
    r1 = r2 = c1 = c2 = 0
    def spread(x, y):
        nonlocal r1, r2, c1, c2
        r1, r2, c1, c2 = min(r1, x), max(r2, x), min(c1, y), max(c2, y)

    for k in range(K):
        if g[ax][ay]==0:
            di, dj = dj, -di  # 顺时针
        else:
            di, dj = -dj, di  # 逆时针
        g[ax][ay] ^= 1        # 翻转
        ax, ay = ax+di, ay+dj   # 移动
        spread(ax, ay)
    g[ax][ay] = -1
    d = (('LR', 'UD')[di][(dj>=0)&(di>=0)])  # 阴间写法
    # d = {(0, -1): 'L', (-1, 0): 'U', (1, 0): 'D', (0, 1): 'R'}[di, dj] # 阳间写法
    ans = [''.join(('_X'+d)[g[i][j]] 
           for j in range(c1, c2+1)) for i in range(r1, r2+1)]
    return ans

41. First Missing Positive

找到数组中最小的缺失的正数。数组中可能包含负数。要求在O(N)时间，常数空间实现。

方法一：难点在于复杂度的要求。这个方法没想到，但是感觉之前用过，忘记是哪道题了。就是将元素放在它对应的索引上。

1
2
3
4
5
6
7
8
9
def firstMissingPositive(self, nums: List[int]) -> int:
    for i in range(len(nums)):
        while 0 <= nums[i]-1 < len(nums) and nums[nums[i]-1] != nums[i]:
            j = nums[i] - 1
            nums[i], nums[j] = nums[j], nums[i]
    for i in range(len(nums)):
        if nums[i] != i+1:
            return i + 1
    return len(nums) + 1

面试题 17.18. 最短超串

找到包含small所有元素最短子数组的最小索引。

1
2
3
big = [7,5,9,0,2,1,3,5,7,9,1,1,5,8,8,9,7]
small = [1,5,9]
输出: [7,10]

方法一：滑动窗口。挺简单的一次就AC了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:
    ans, c, s = [], defaultdict(int), set(small)
    i, min_len = 0, float('inf')
    for end, d in enumerate(big):
        if d in s:
            c[d] += 1
        while len(c) == len(s):
            if end-i+1 < min_len:
                min_len = end - i + 1
                ans = [i, end]
            if big[i] in s:
                c[big[i]] -= 1
                if c[big[i]] == 0:
                    c.pop(big[i])
            i += 1
    return ans

289. Game of Life

生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
根据当前状态，写一个函数来计算面板上所有细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。

你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。
本题中，我们使用二维数组来表示面板。原则上，面板是无限的，但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题？

方法一：首次AC的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def gameOfLife(self, board: List[List[int]]) -> None:
    m, n = len(board), len(board[0])
    
    def count_live(i, j):
        neighbors = ((1, 0), (-1, 0), (0, 1), (0, -1), 
                     (-1, -1), (1, 1), (1, -1), (-1, 1))
        return sum(board[i+di][j+dj] for di, dj in neighbors 
                   if 0<=i+di<m and 0<=j+dj<n)
    
    g = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            c = count_live(i, j)
            g[i][j] = int(c==3 or (c==2 and board[i][j]))

    board[:] = g

方法二：如果面板是无限的，如何考虑呢？Stefan这样写，一个辅助函数来根据所有当前活着的细胞计算下一个状态的活细胞集。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def gameOfLife(self, board: List[List[int]]) -> None:
  
    def gameOfLifeInfinite(live):
        ctr = collections.Counter((I, J)
                                  for i, j in live
                                  for I in range(i-1, i+2)
                                  for J in range(j-1, j+2)
                                  if I != i or J != j)
        return {ij
                for ij in ctr
                if ctr[ij] == 3 or ctr[ij] == 2 and ij in live}
    
    live = {(i, j) for i, row in enumerate(board) for j, live in enumerate(row) if live}
    live = gameOfLifeInfinite(live)
    for i, row in enumerate(board):
        for j in range(len(row)):
            row[j] = int((i, j) in live)

方法三：此题可以使用生成器来建模，在《effictive python》中有一个非常经典的例子，《Fluent Python》中作者也提到了这个例子。我在次基础上修改了一点，主要是针对边界处理。每一个细胞都表示为一个协程，并令这些协程步调一致地向前推进。step_cell是一个协程，会生成·Transition对象用来表示细胞的状态迁移。每个细胞都可以通过运行step_cell来迁移到下一个状态。待所有细胞都迁移好之后，游戏的始终就会向前走一步。只要simulate协程在推进，这个过程就会一直持续下去。协程的优势就在于此。它令开发者所用的实现代码相互解耦。这使得程序好像能够平行地运行多个协程，也使得开发者能够在不修改协程的前提下，逐渐改进发布指令时所用的代码。不过书中说的一点没有明白”如果传入的坐标越界，那就自动折回，这使得网格看上去好像是一种无限循环的空间”，书中使用了取余的方式，但是本题中越界应该返回0。这套模板代码演示了如何用协程分离程序中的各个关注点，而关注点的分离，正是一条重要的设计原则。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
Query = namedtuple('Query', 'y x')   # 用于查询细胞的状态，这里实现很巧妙可以使协程通过此对象向外围环境查询信息
Transition = namedtuple('Transition', 'y x state')  # 表示细胞的状态迁移


class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        self.board = board
        self.TICK = object()	# 停止标识，标志着一轮模拟结束
        sim = self.simulate(len(board), len(board[0]))
        ans = self.live_a_generation(sim)
        for i in range(len(board)):
            for j in range(len(board[0])):
                board[i][j] = ans[i,j]
        
    def count_neighbors(self, y, x):		#查询了细胞周围的8个细胞状态
        n_ = yield Query(y + 1, x + 0)  # North
        ne = yield Query(y + 1, x + 1)  # Northeast
        e_ = yield Query(y + 0, x + 1)  # East
        se = yield Query(y - 1, x + 1)  # Southeast
        s_ = yield Query(y - 1, x + 0)  # South
        sw = yield Query(y - 1, x - 1)  # Southwest
        w_ = yield Query(y + 0, x - 1)  # West
        nw = yield Query(y + 1, x - 1)  # Northwest
        neighbor_states = [n_, ne, e_, se, s_, sw, w_, nw]
        count = 0
        for state in neighbor_states:
            if state == 1:
                count += 1
        return count

    def game_logic(self, state, neighbors):   # 游戏逻辑
        if state == 1:
            if neighbors < 2:
                return 0     # Die: Too few
            elif neighbors > 3:
                return 0     # Die: Too many
        else:
            if neighbors == 3:
                return 1     # Regenerate
        return state

    def step_cell(self, y, x):		
        state = yield Query(y, x)		# 查询当前细胞状态
        neighbors = yield from self.count_neighbors(y, x)  # 查询周围细胞状态，`count_neighbors`协程
        next_state = self.game_logic(state, neighbors)		# 细胞的下一次状态
        yield Transition(y, x, next_state)		# 生成迁移对象，将细胞在下一轮的状态告诉外部代码

    def simulate(self, height, width):    #  模拟协程
        while True:
            for y in range(height):
                for x in range(width):
                    yield from self.step_cell(y, x)
            yield self.TICK
        
    def live_a_generation(self, sim):			# 主函数
        M, N = len(self.board), len(self.board[0])
        progeny = Grid(M, N)
        item = next(sim)
        while item is not self.TICK:		# 对所有的细胞向前推进一步
            if isinstance(item, Query):
                if 0<=item.y<M and 0<=item.x<N:
                    state = self.board[item.y][item.x]
                else:
                    state = 0
                item = sim.send(state)
            else:
                progeny[item.y, item.x] = item.state
                item = next(sim)
        return progeny
                
                
class Grid(object):		# 用于表示细胞网格
    def __init__(self, height, width):
        self.height = height
        self.width = width
        self.rows = []
        for _ in range(self.height):
            self.rows.append([0] * self.width)

    def __str__(self):
        output = ''
        for row in self.rows:
            for cell in row:
                output += str(cell)
            output += '\n'
        return output

    def __getitem__(self, index):
        y, x = index
        if 0<=y<self.height and 0<=x<self.width:
            return self.rows[y][x]
        else:
            return 0

    def __setitem__(self, index, state):
        y, x = index
        if 0<=y<self.height and 0<=x<self.width:
            self.rows[y % self.height][x % self.width] = state

164. Maximum Gap

在线性时间空间复杂度找到数组中两个排好序后的相邻元素的最大差。

1
2
3
4
Input: [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either
             (3,6) or (6,9) has the maximum difference 3.

方法一：桶排序。 如果将这些数平分，差最小也是size，所以最大值会出现在两个相邻的桶之间，而不会在一个桶内。这里同时记录了最小值和最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
def maximumGap(self, nums: List[int]) -> int:
    N = len(nums)
    if N < 2 or min(nums)==max(nums):
        return 0
    small, big = min(nums), max(nums)
    size = (big-small) // (N-1) or 1
    buckets = [[None, None] for _ in range((big-small)//size+1)]
    for n in nums:
        b = buckets[(n-small)//size]
        b[0] = n if b[0] is None else min(b[0], n)
        b[1] = n if b[1] is None else max(b[1], n)
    buckets = [b for b in buckets if b[0] is not None]
    return max(buckets[i][0]-buckets[i-1][1] for i in range(1, len(buckets)))

1755. Closest Subsequence Sum

找到最接近目标值的子序列。

1
2
3
4
Input: nums = [5,-7,3,5], goal = 6
Output: 0
Explanation: Choose the whole array as a subsequence, with a sum of 6.
This is equal to the goal, so the absolute difference is 0.

方法一：分治+dfs。这题主要先想到分治，然后才能做，因为数组长度是40.直接做会超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def minAbsDifference(self, nums: List[int], goal: int) -> int:
    # function that generates all possible sums of sebsequences
    def dfs(i, cur, arr, sums):
        if i == len(arr):
            sums.add(cur)
            return
        dfs(i+1, cur, arr, sums)
        dfs(i+1, cur+arr[i], arr, sums)

    sums1, sums2 = set(), set()
    # generate all possible sums of the 1st and 2nd half 
    dfs(0, 0, nums[:len(nums)//2], sums1)
    dfs(0, 0, nums[len(nums)//2:], sums2)
    res = inf
    sums2 = sorted(sums2)
    for num in sums1:
        t = goal - num
        i = bisect_left(sums2, t)
        if i < len(sums2):
            res = min(res, abs(t-sums2[i]))
        if i > 0:
            res = min(res, abs(t-sums2[i-1]))
    return res

992. Subarrays with K Different Integers

k个不同数字的连续子数组的个数。

1
2
3
Input: A = [1,2,1,2,3], K = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

方法一：刚好K个等于最少k个-最少k-1个。滑动窗口。

1
2
3
4
5
6
7
8
9
10
11
12
13
def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
    def most_k(k):
        left, res, c = 0, 0, defaultdict(int)
        for right, d in enumerate(A):
            c[d] += 1
            while len(c) > k:
                c[A[left]] -= 1
                if c[A[left]] == 0:
                    del c[A[left]]
                left += 1
            res += right-left+1
        return res
    return most_k(K) - most_k(K-1)

995. Minimum Number of K Consecutive Bit Flips

每次翻转连续k个数字，能否全部翻转成1.需要多少次。

1
2
3
4
5
6
Input: A = [0,0,0,1,0,1,1,0], K = 3
Output: 3
Explanation:
Flip A[0],A[1],A[2]: A becomes [1,1,1,1,0,1,1,0]
Flip A[4],A[5],A[6]: A becomes [1,1,1,1,1,0,0,0]
Flip A[5],A[6],A[7]: A becomes [1,1,1,1,1,1,1,1]

方法一：贪心+滑动窗口。如果模拟30000的长度会超时。使用滑动窗口来做，看前k个队列中翻转的奇偶性，判断当前数是否翻转。如果翻转长度超过数组长度，则无法完成翻转。

1
2
3
4
5
6
7
8
9
10
11
def minKBitFlips(self, A: List[int], K: int) -> int:
    q, res = deque(), 0
    for i, a in enumerate(A):
        if q and q[0]+K <= i:
            q.popleft()
        flip = len(q)%2==a
        if flip:
            if i + K > len(A): return -1
            q.append(i)
            res += 1
    return res

395. Longest Substring with At Least K Repeating Characters

找到字符串中最长子串，要求每个字符频率不少于K，返回最长的子串长度。

1
2
3
输入：s = "aaabb", k = 3
输出：3
解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。

方法一：这题，滑动窗口不好滑，递归思想简单。

1
2
3
4
5
6
7
def longestSubstring(self, s: str, k: int) -> int:
    if len(s) < k:
        return 0
    for c in set(s):
        if s.count(c) < k:
            return max(self.longestSubstring(t, k) for t in s.split(c))
    return len(s)

1838. Frequency of the Most Frequent Element

有k次机会可以将数组中的元素加1，问能得到数组中最大的频数是多少。

1
2
3
4
Input: nums = [1,2,4], k = 5
Output: 3
Explanation: Increment the first element three times and the second element two times to make nums = [4,4,4].
4 has a frequency of 3.

方法一：比赛的时候，滑动窗口想了一下，没找到条件。遗憾没做出来。因为每次都是+1, 所以条件是k+sum >= size * max

1
2
3
4
5
6
7
8
9
def maxFrequency(self, nums: List[int], k: int) -> int:
    i = 0
    nums.sort()
    for j in range(len(nums)):
        k += nums[j]
        if k < (j - i + 1) * nums[j]:
            k -= nums[i]
            i += 1
    return j - i + 1

2106. Maximum Fruits Harvested After at Most K Steps

最多走k步，可以向左或向右走，最多能收集多少个草莓。

1
2
3
4
5
6
7
Input: fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4
Output: 9
Explanation: 
The optimal way is to:
- Move right to position 6 and harvest 3 fruits
- Move right to position 8 and harvest 6 fruits
You moved 3 steps and harvested 3 + 6 = 9 fruits in total.

方法一：比赛过后写出来的，比赛的方法写得过于复杂。其实简单的前缀和就好。需要注意的是往返需要2倍的步数，可以向左或向右往返。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:
    d = Counter()
    r = 1
    left = Counter()
    right = Counter()
    for i,j in fruits:  
        d[i] = j
    ans = d[startPos]

    for i in range(startPos+1,startPos+k+1):
        right[i-startPos] = right[i-1-startPos] + d[i]
        
    for i in range(startPos - 1,startPos-1-k,-1):
        left[r] = left[r-1] + d[i]
        r += 1
        
    for i in range(1,k+1):
        ans = max(ans, max(right[i] + left[k - 2*i], left[i] + right[k - 2*i]) + d[startPos])
        
    return ans

862. Shortest Subarray with Sum at Least K

给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。

1
2
输入：nums = [2,-1,2], k = 3
输出：3

方法一：前缀和很容易想到。之后需要维护一个队列，左侧删除也比较容易想到。右侧删除有点难想。

1
2
3
4
5
6
7
8
9
10
11
def shortestSubarray(self, nums: List[int], k: int) -> int:
    ans = inf
    s = list(accumulate(nums, initial=0))  # 计算前缀和
    q = deque()
    for i, cur_s in enumerate(s):
        while q and cur_s-s[q[0]]>=k:  
            ans = min(ans, i-q.popleft())
        while q and s[q[-1]]>=cur_s:  # nxt_s - cur_s的值更大，并且长度更短
            q.pop()
        q.append(i)
    return ans if ans != inf else -1

2448. Minimum Cost to Make Array Equal

给你两个下标从 0 开始的数组 nums 和 cost ，分别包含 n 个 正 整数。

你可以执行下面操作 任意 次：

将 nums 中 任意 元素增加或者减小 1 。
对第 i 个元素执行一次操作的开销是 cost[i] 。

请你返回使 nums 中所有元素 相等 的 最少 总开销。

1
2
3
4
5
6
7
8
输入：nums = [1,3,5,2], cost = [2,3,1,14]
输出：8
解释：我们可以执行以下操作使所有元素变为 2 ：
- 增加第 0 个元素 1 次，开销为 2 。
- 减小第 1 个元素 1 次，开销为 3 。
- 减小第 2 个元素 3 次，开销为 1 + 1 + 1 = 3 。
总开销为 2 + 3 + 3 = 8 。
这是最小开销。

方法一：这题竞赛没有过，题解也是看了很久，题目本身并不难。将nums和cost一起排序。首先计算所有等于nums[0]的开销，以及所有的cost。然后考虑所有的数变成nums[1]。这样要增加(nums[1]-nums[0]) * cost[0]，要减少(nums[1]-nums[0])*(sum_cost-cost[0])。之后考虑所有的数变成nums[2]，要增加(nums[2]-nums[1])*(cost[0]+cost[1])，减少(nums[2]-nums[1])*(sum_cost-cost[0]-cost[1])。总共减少(nums[i+1]-nums[i]) * (sum_cost-cost[0]*2-cost[1]*2...-cost[i]*2)

1
2
3
4
5
6
7
8
9
def minCost(self, nums: List[int], cost: List[int]) -> int:
    a = sorted(zip(nums, cost))
    ans = total = sum((x - a[0][0]) * c for x, c in a)
    sum_cost = sum(cost)
    for (x0, c), (x1, _) in pairwise(a):
        sum_cost -= c * 2
        total -= sum_cost * (x1 - x0)
        ans = min(ans, total)
    return ans

805. Split Array With Same Average

给定你一个整数数组 nums

我们要将 nums 数组中的每个元素移动到 A 数组 或者 B 数组中，使得 A 数组和 B 数组不为空，并且 average(A) == average(B) 。

如果可以完成则返回true ， 否则返回 false 。

1
2
3
输入: nums = [1,2,3,4,5,6,7,8]
输出: true
解释: 我们可以将数组分割为 [1,4,5,8] 和 [2,3,6,7], 他们的平均值都是4.5。

方法一：看了题解才明白，首先要明白转化问题，目标是找到一个子数组，平均数为总数组的平均数。题中数组长度为30，如果遍历将会为2**30，超时，所以可以将问题折半，变为两个数组。分为三种情况：子数组在数组左侧，子数组在数组右侧，子数组左右都有。由于平均数浮点有精度问题，所以我们将所有数乘以N，然后减去sum(nums),这样问题变为，找到一个子数组和为0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def splitArraySameAverage(self, nums: List[int]) -> bool:
    N = len(nums)
    s = sum(nums)
    mid = sum(nums) / N
    arr = [num*N-s for num in nums]
    left, right = arr[:N//2], arr[N//2:]
    t = set()
    for i in range(1, N//2+1):
        for inner in combinations(left, i):
            ss = sum(inner)
            # print(inner, ss)
            if ss == 0:
                return True
            else:
                t.add(ss)
    # print(t)
    for i in range(1, N-len(left)):
        for inner in combinations(right, i):
            ss = sum(inner)
            if ss == 0:
                return True
            elif -ss in t:
                return True
    return False