LeetCode算法题整理（贪心篇）Greedy

984. String Without AAA or BBB

生成字符串没有‘aaa’和’bbb’。原题

Input: A = 1, B = 2
Output: "abb"
Explanation: "abb", "bab" and "bba" are all correct answers.

def strWithout3a3b(self, A, B):
    ans = ''
    while A or B:
        if len(ans) >= 2 and ans[-1]==ans[-2]:
            writeA = ans[-1]=='b'
        else:
            writeA = A>=B
        
        if writeA:
            A -= 1
            ans += 'a'
        else:
            B -= 1
            ans += 'b'
    return ans

455. Assign Cookies

发小饼干，s为若干个饼干的大小，g为每个人需要的大小，没人发的饼干不能比要求的size小，问最多可以满足几个人。原题

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

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. 
You have 3 cookies and their sizes are big enough to gratify all of the children, 
You need to output 2.

def findContentChildren(self, g: List[int], s: List[int]) -> int:
    g.sort()
    s.sort()
    i = j = 0
    while i < len(g) and j < len(s):
        i += s[j] >= g[i]
        j += 1
    return i

860. Lemonade Change

柠檬找零，每人买一个柠檬，（价值5）可能付5, 10, 20面值的钞票，问零钱是否能找开。原题

Input: [5,5,5,10,20]
Output: true
Explanation: 
From the first 3 customers, we collect three $5 bills in order.
From the fourth customer, we collect a $10 bill and give back a $5.
From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.

方法一：defaultdict。

def lemonadeChange(self, bills: 'List[int]') -> 'bool':
    c = collections.defaultdict(int)
    for bill in bills:
        if bill == 10:
            c[5] -= 1
        elif bill == 20:
            if c[10] >= 1:
                c[10] -= 1
                c[5] -= 1
            else:
                c[5] -= 3
        if c[5] < 0:
            return False
        c[bill] += 1
    return True

944. Delete Columns to Make Sorted

找出并行项中未排序的个数。原题

方法一：sorted要比any快，感觉是Cpython的优化导致，理论上来说应该是any快。

def minDeletionSize(self, A: 'List[str]') -> 'int':
    ans = 0
    for col in zip(*A):
        # if any(col[i]>col[i+1] for i in range(len(col)-1)):
        if sorted(col) != list(col):
            ans += 1
    return ans

55. Jump Game

跳跃游戏，数组中每个元素表示下一步的距离，问是否能跳到最后索引位置。原题

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

方法一：贪心。

def canJump(self, nums: List[int]) -> bool:
    last_pos = len(nums) - 1
    for i in range(len(nums)-1, -1, -1):
        if i + nums[i] >= last_pos:
            last_pos = i
    return last_pos == 0

1005. Maximize Sum Of Array After K Negations

K次取负后的数组最大和。原题

Input: A = [3,-1,0,2], K = 3
Output: 6
Explanation: Choose indices (1, 2, 2) and A becomes [3,1,0,2].

方法一：竞赛的时候，写得比较麻烦，分了两个数组，还考虑了0，后来看lee神的整理一下。注意最后一步要用一下min，否则获取不了最小值。

def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
    A.sort()
    i = 0
    while i<len(A) and i<K and A[i]<0:
        A[i] = -A[i]
        i += 1
    return sum(A) - (K-i)%2*min(A)*2

1029. Two City Scheduling

两个城市调度。每个坐标表示，去A和B的花费，使花费最小。原题

Input: [[10,20],[30,200],[400,50],[30,20]]
Output: 110
Explanation: 
The first person goes to city A for a cost of 10.
The second person goes to city A for a cost of 30.
The third person goes to city B for a cost of 50.
The fourth person goes to city B for a cost of 20.

The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.

方法一：假设左边的人留在A，右边的人留在B，如果不是最优解，那么右边的人r需要移到左边，左边的人l需要移到右边，相当于从l[0]+r[1]变为了l[1]+r[0]，即l[1]-l[0]+r[0]-r[1]<0时需要交换两个城市，推导可得出，l[0]-l[1] > r[0]-r[1]，则得出排序规则。

def twoCitySchedCost(self, costs: List[List[int]]) -> int:
    costs.sort(key=lambda x: x[0]-x[1]) 
    return sum(i[0] for i in costs[:len(costs)//2]) + sum(j[1] for j in costs[len(costs)//2:])

1042. Flower Planting With No Adjacent

联通图染色问题，paths表示相邻的花园，相邻的花园中不能种同一种花，一种有四种花。原题

方法一：

def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]:
    res = [0] * N
    g = [[] for _ in range(N)]
    for x, y in paths:
        g[x-1].append(y-1)
        g[y-1].append(x-1)
        
    for i in range(N):
        res[i] = ({1, 2, 3, 4}-{res[j] for j in g[i]}).pop()
    return res

1046. Last Stone Weight

最后一块石头的质量。每次从石头堆中拿出两块最重的pk，剩下为二者之差。原题

方法一：暴力排序。

def lastStoneWeight(self, stones: List[int]) -> int:
    stones = sorted(stones)
    while len(stones) > 1:
        a, b = stones.pop(), stones.pop()
        if a != b:
            stones.append(a - b)
            stones.sort()
    return stones[0] if stones else 0

方法二：使用堆。

def lastStoneWeight(self, stones: List[int]) -> int:
    import heapq as hq
    from operator import neg
    stones = list(map(neg, stones))
    hq.heapify(stones)
    while len(stones) > 1:
        a = -hq.heappop(stones)
        b = -hq.heappop(stones)
        if a != b:
            hq.heappush(stones, b - a)
    return -hq.heappop(stones) if stones else 0

1090. Largest Values From Labels

给一个集合，每个元素有一个值values[i]与标签labels[i]。这里要选择一个子集，使得子集的元素个数不超过num_wanted，而且相同标签的元素个数不超过use_limit。求子集的最大和。原题

Input: values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted = 3, use_limit = 1
Output: 9
Explanation: The subset chosen is the first, third, and fifth item.

方法一：此题大部分时间花在理解题意，英文原文非常容易误解。

def largestValsFromLabels(self, values: List[int], labels: List[int], num_wanted: int, use_limit: int) -> int:
    ans = 0
    c = collections.defaultdict(int)
    for v, b in sorted(zip(values, labels), reverse=True):
        if num_wanted == 0:
            break
        if c[b] < use_limit:
            c[b] += 1
            ans += v
            num_wanted -= 1
    return ans

1094. Car Pooling

一辆车接旅客，根据旅客的人数，上下车位置，判断是否可以载完所有的旅客。原题

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false

方法一：将旅客上下车地点排序。

def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
    for i, v in sorted(x for n, s, e in trips for x in ((s, n), (e, -n))):
        capacity -= v
        if capacity < 0:
            return False
    return True

1403. Minimum Subsequence in Non-Increasing Order

最小的宽度的和大于剩余数的子序列。原题

Input: nums = [4,3,10,9,8]
Output: [10,9] 
Explanation: The subsequences [10,9] and [10,8] are minimal such that the sum of their elements is strictly greater than the sum of elements not included, however, the subsequence [10,9] has the maximum total sum of its elements.

方法一：排序。

def minSubsequence(self, nums: List[int]) -> List[int]:
    nums.sort(reverse=True)
    total = sum(nums)
    cur = 0
    for i, d in enumerate(nums):
        cur += d
        if cur * 2 > total:
            return nums[:i+1]
    return nums

1400. Construct K Palindrome Strings

是否能用给定的字符串够成k个回文串。原题

Input: s = "annabelle", k = 2
Output: true
Explanation: You can construct two palindromes using all characters in s.
Some possible constructions "anna" + "elble", "anbna" + "elle", "anellena" + "b"

方法一：能否构成回文串，要看奇数个字符是否小于等于k。

def canConstruct(self, s: str, k: int) -> bool:
    from collections import Counter
    odd_c = sum(cnt&1==1 for cnt in Counter(s).values())
    return odd_c <= k <= len(s)

45. Jump Game II

跳跃游戏。每个位置写了最远距离。原题

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
    Jump 1 step from index 0 to 1, then 3 steps to the last index.

方法一：使用了与1024题一样的方法。

def jump(self, nums: List[int]) -> int:
    n = len(nums)
    end, end2, cnt = -1, 0, 0
    for i, s in enumerate(nums):
        if end2 >= n-1:
            break
        elif end < i <= end2:
            cnt += 1
            end = end2
        end2 = max(end2, i+s)
    return cnt

方法二：使用两个指针，表示了一个范围，每次增加一步时，在这个范围中找到下一次最右的距离，为了不让范围重叠, 让left=right+1，直到最右点到达末尾。

def jump(self, nums: List[int]) -> int:
    if len(nums) <= 1: return 0
    l, r = 0, nums[0]
    step = 1
    while r < len(nums)-1:
        step += 1
        nxt = max(i+nums[i] for i in range(l, r+1))
        l, r = r+1, nxt
    return step

1296. Divide Array in Sets of K Consecutive Numbers

数组能否分成连续的k个元素的子数组。原题

Input: nums = [1,2,3,3,4,4,5,6], k = 4
Output: true
Explanation: Array can be divided into [1,2,3,4] and [3,4,5,6].

方法一：首次ac的方法。每次取最小的key比较耗时。

def isPossibleDivide(self, nums: List[int], k: int) -> bool:
    n = len(nums)
    if n % k != 0:
        return False
    c = collections.Counter(nums)
    for i in range(n//k):
        s = min(c.keys())
        for j in range(k):
            if s+j not in c:
                return False
            c[s+j] -= 1
            if c[s+j] == 0:
                del c[s+j]
    return True

方法二：排序，每次从中取最小，如果其数量不为1，那么作为它的等差数列一组，另外的k-1个数也得大于等于这个数量。

def isPossibleDivide(self, nums: List[int], k: int) -> bool:
    c = collections.Counter(nums)
    for i in sorted(c):
        if c[i] > 0:
            for j in range(1, k):
                c[i+j] -= c[i]
                if c[i+j] < 0:
                    return False
    return True

1282. Group the People Given the Group Size They Belong To

将元素分组到指定的size中。原题

Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]
Explanation: 
Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].

方法一：比赛时用的sort，其实有O(n)的方法。

def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
    gs = [(i, s) for i, s in enumerate(groupSizes)]
    ans = []
    last = None
    for i, s in sorted(gs, key=lambda x: x[1]):
        if not last or len(ans[-1]) == last:
            ans.append([i])
        else:
            ans[-1].append(i)
        last = s
    return ans

方法二：hash.

def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
    count = collections.defaultdict(list)
    for i, g in enumerate(groupSizes):
        count[g].append(i)
    return [l[i:i+s] for s, l in count.items() for i in range(0, len(l), s)]

1253. Reconstruct a 2-Row Binary Matrix

两个二进制数组，给出每个累加1的和，和列的和，重建这个二进制数组，答案不唯一。原题

Input: upper = 2, lower = 1, colsum = [1,1,1]
Output: [[1,1,0],[0,0,1]]
Explanation: [[1,0,1],[0,1,0]], and [[0,1,1],[1,0,0]] are also correct answers.

方法一：竞赛时的方法写的太java。因为在于贪心的条件选择先塞满第一个数。这样会徒增一些没用的判断。

def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:
    n = len(colsum)
    c1, c2 = colsum.count(1), colsum.count(2)
    if upper+lower-c2*2 != c1 or min(upper, lower)<c2:
        return []
    a, b, r = [], [], 0
    for c in colsum:
        if c == 2:
            i = j = 1
        elif c == 1:
            if upper-c2-r > 0:
                i = 1
                j = 0
                r += 1
            else:
                i = 0
                j = 1
        else:
            i = j = 0
        a.append(i)
        b.append(j)
    return [a, b]

方法二：可以用大小判断选择放哪个数中。

def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:
    n = len(colsum)
    a1, a2 = [0] * n, [0] * n
    for i, s in enumerate(colsum):
        if s == 1:
            if upper > lower:
                a1[i] = 1
                upper -= 1
            else:
                a2[i] = 1
                lower -= 1
        elif s == 2:
            a1[i] = a2[i] = 1
            upper -= 1
            lower -= 1
    return (a1, a2) if lower==upper==0 else []

1247. Minimum Swaps to Make Strings Equal

两个包含x和y的字符串，互换任意两个字符，最小需要多少次才能相等。原题

Input: s1 = "xx", s2 = "yy"
Output: 1
Explanation: 
Swap s1[0] and s2[1], s1 = "yx", s2 = "yx".

Input: s1 = "xy", s2 = "yx"
Output: 2
Explanation: 
Swap s1[0] and s2[0], s1 = "yy", s2 = "xx".
Swap s1[0] and s2[1], s1 = "xy", s2 = "xy".
Note that you can't swap s1[0] and s1[1] to make s1 equal to "yx", cause we can only swap chars in different strings.

方法一：尽量多的匹配,’xx’和’yy’这样只需要一步。ac倒是ac了，写法上看着有点烂。

def minimumSwap(self, s1: str, s2: str) -> int:
    c_x, c_y = 0, 0
    ans = 0
    for a, b in zip(s1, s2):
        if a != b:
            c_x += (a=='x')
            c_y += (a=='y')
        if max(c_x, c_y)==2:
            if c_x > c_y:
                c_x -= 2
            else:
                c_y -= 2
            ans += 1
    if c_x + c_y == 1:
        return -1
    ans += (c_x==1 and c_y==1) * 2
    return ans

方法二：优化一下。

def minimumSwap(self, s1: str, s2: str) -> int:
    x1 = y1 = 0
    for a, b in zip(s1, s2):
        if a != b:
            if a == 'x':
                x1 += 1
            else:
                y1 += 1
    if (x1+y1) & 1 == 1:
        return -1
    return x1//2 + y1//2 + 2*(x1&1)

406. Queue Reconstruction by Height

根据没跟人的高度和前面比他高的k个人，重建队列。原题

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

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

方法一：看了答案，理解起来也不是很难，根据高度来排序，每次选出一个人插入到队列中，因为队列里的人都是比他高的。

def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
    people.sort(key=lambda x: (-x[0], x[1]))
    queue = []
    for p in people:
        queue.insert(p[1], p)
    return queue

1488. Avoid Flood in The City

rains表示哪个湖会下雨，0的时候表示可以选择一个湖抽干水，如果有湖水在抽干前又下雨了，那么就会发洪水，返回-1，然后需要返回一个数组，表示每天应该抽干哪个湖的水，答案不唯一。原题

Input: rains = [1,2,0,0,2,1]
Output: [-1,-1,2,1,-1,-1]
Explanation: After the first day full lakes are [1]
After the second day full lakes are [1,2]
After the third day, we dry lake 2. Full lakes are [1]
After the fourth day, we dry lake 1. There is no full lakes.
After the fifth day, full lakes are [2].
After the sixth day, full lakes are [1,2].
It is easy that this scenario is flood-free. [-1,-1,1,2,-1,-1] is another acceptable scenario.

方法一：竞赛的时候没有做出来，在多次wa后TLE了，使用的方式是二分查找修改要抽哪天的水。没有想到用堆。而且整体的思路有一种滞后性，就是当遇见第二次下雨的时候再去找0的那天抽干哪个湖的水。这个方法遍历了两次数组，第一次将每个湖下雨的天数记录下来。然后可以抽水的时候用一个堆去计算最近的哪个湖会再次下雨，这样优先抽干这个湖的水。to_empty中记录索引。

def avoidFlood(self, rains: List[int]) -> List[int]:
    n = len(rains)
    dic = collections.defaultdict(list)
    ans = [-1] * n
    full = set()
    to_empty = []
    for i, rain in enumerate(rains):
        dic[rain].append(i)
        
    for i, rain in enumerate(rains):
        if rain:
            if rain in full:
                return []
            else:
                full.add(rain)
                dic[rain].pop(0)
                if dic[rain]:
                    heapq.heappush(to_empty, dic[rain][0])
        else:
            if to_empty:
                j = heapq.heappop(to_empty)
                ans[i] = rains[j]
                full.remove(rains[j])
            else:
                ans[i] = 1
    return ans

1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits

一个数字最多交换K次相邻的字符，使其表示的数字最小，可以0开头。原题

Input: num = "4321", k = 4
Output: "1342"
Explanation: The steps to obtain the minimum integer from 4321 with 4 adjacent swaps are shown.

方法一：据说是字节的面试题。contest时卡在了第三题，此题没有时间看。这个方法是超时的。

def minInteger(self, num: str, k: int) -> str:
    num = [*map(int, num)]
    if k >= (len(num) ** 2) // 2:
        return ''.join(map(str, sorted(num)))
    
    res = []
    q = [(v, i) for i, v in enumerate(num)]
    while k and q:
        idx, (v, i) = min(enumerate(q[:k + 1]), key=lambda p:p[1])
        k -= idx
        del q[idx]
        res += v,
        
    res += [v for v, _ in q]
    return ''.join(map(str, res))

方法二：使用一个FenWick数即二叉索引数记录位移。总体的思路是一样的，每次在可以k的范围内找到一个最小的数移到最左边，这样数字会变为最小，开始的时候记录每个数的原始索引，使用FenWick记录位移索引，如在一个i的位置找到一个最小数移到最左边，那么其原始序列右侧的数下次需要位移为原始做阴-1，因为最左位已经被占用了。

class FenWick(object):
    
    def __init__(self, n):
        self.nums = [0] * (1+ n)
        
    def update(self, i, delta):
        while i < len(self.nums):
            self.nums[i] += delta
            i += i & -i
            
    def query(self, i):
        ans = 0
        while i > 0:
            ans += self.nums[i]
            i -= i & -i
        return ans
    
class Solution:
    def minInteger(self, num: str, k: int) -> str:
        n = len(num)
        pos = [[] for _ in range(10)]
        for i in range(n-1, -1, -1):
            pos[ord(num[i])-ord('0')].append(i)
        
        def find_min():
            for d in range(10):
                if not pos[d]: continue
                i = pos[d][-1]
                cost = i - tree.query(i)
                if cost <= k: return d, cost
            return None, None
        
        tree = FenWick(n)
        res = []
        removed = [False] * n
        
        while k:
            d, cost = find_min()
            if d is None: break  
            k -= cost
            res.append(d)
            i = pos[d].pop()
            tree.update(i+1, 1)
            removed[i] = True
            
        lhs = ''.join(map(str, res))
        rhs = ''.join(num[i] for i in range(n) if not removed[i])
        return lhs + rhs

763. Partition Labels

将字符串S尽可能分成多的部分，不同部分不能有相同的字符。原题

Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.

方法一：一开始想的方法。每次遇到之前的元素就用栈的方式来合并。

def partitionLabels(self, S: str) -> List[int]:
    n = len(S)
    last = {}
    ans = []
    for i, c in enumerate(S):
        last[c] = i
        
    hi = -1
    while hi != n-1:
        lo = start = hi + 1
        hi = last[S[lo]]
        while lo < hi:
            lo += 1
            hi = max(hi, last[S[lo]])
        ans.append(hi-start+1)
    return ans

方法二：这个判断条件没有想到，其实只要和最后索引相同，就可以添加一段了。

def partitionLabels(self, S: str) -> List[int]:
    last = {c: i for i, c in enumerate(S)}
    ans = []
    lo = hi = 0
    
    for i, c in enumerate(S):
        hi = max(hi, last[c])
        if i == hi:
            ans.append(hi-lo+1)
            lo = i + 1
    return ans

方法三：stefan有比较直观的方法。时间复杂度略高

def partitionLabels(self, S: str) -> List[int]:
    ans = []
    while S:
        i = 1
        while set(S[:i]) & set(S[i:]):
            i += 1
        ans.append(i)
        S = S[i:]
    return ans

621. Task Scheduler

每两个相同任务之间需要有n个时间，不足则需要闲置，问最少的任务调度完成时间是多少。原题

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: 
A -> B -> idle -> A -> B -> idle -> A -> B
There is at least 2 units of time between any two same tasks.

方法一：使用堆。

def leastInterval(self, tasks: List[str], n: int) -> int:
    c = Counter(tasks).most_common()
    ans = 0
    c = [(-b, a) for a, b in c]
    heapq.heapify(c)
    while c:
        tmp = [heapq.heappop(c)]
        k = n
        while k and c:
            tmp.append(heapq.heappop(c))
            k -= 1
        for t, l in tmp:
            if -t > 1:
                heapq.heappush(c, (t+1, l))
        if c:
            ans += k
    return ans + len(tasks)

方法二：构造一个M*(n+1)的矩阵（最后一行可能不满），将最多的任务排在每一列中。Mct表示最多的任务有多少个。那么总时间为

(M-1)(n+1)+Mct。

如果还有任务没有放置，该怎么办？这时只要增加宽度，对于CPU来说，相当于没有空闲时间，一直在满负载运行。

def leastInterval(self, tasks: List[str], N: int) -> int:
    task_counts = list(collections.Counter(tasks).values())
    M = max(task_counts)
    Mct = task_counts.count(M)
    return max(len(tasks), (M - 1) * (N + 1) + Mct)

1536. Minimum Swaps to Arrange a Binary Grid

二维矩阵，每次换相邻的2行，最小步数使左上右下的对象线上方全是0.原题

方法一：贪心。曾经做过一道类似的题，是每次变换十字形，然后最后变成全是0，那道题用了转换的方式，将数组转换成了一个二维数字。受到了那题的影响，比赛时想的是BFS的方法，所以最后超时了。为什么贪心的方法可行，因为每行所需的结尾0的个数是越来越少的，所以每次将所满足的行移到最上，下面的行需要的个数不会超过此行。

def minSwaps(self, grid: List[List[int]]) -> int:
    n = len(grid)
    ans = 0
    tail_zero = [len(list(itertools.takewhile(lambda x: x==0, row[::-1]))) 
                 for row in grid]
    for i in range(n):
        for j in range(i, n):
            tail_zero[i], tail_zero[j] = tail_zero[j], tail_zero[i]
            if tail_zero[i] >= n-i-1:
                ans += j - i
                break
        else:
            return -1
            
    return ans

435. Non-overlapping Intervals

删除最少的段，使剩余的不重复。原题

Input: [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.

方法一：排序。一开始没有加key，为什么是这样的条件呢，因为需要每次选取最小的end，才能保证容纳更多的段。

def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
    intervals.sort(key=lambda x: x[1])
    end, ans = float('-inf'), 0
    for s, e in intervals:
        if s < end:
            ans += 1
        else:
            end = e
    return ans

134. Gas Station

说有这么一个加油站，每个加油站能加gas[i]的油量，走到下一个站需要花费cost[i]的油量，这些加油站围绕成一个圈，只有从一个站走才能顺时针走完一圈，问这个站的索引是多少，如果没有，返回-1。原题

Input: 
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]

Output: 3

Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

方法一：首次ac的方法。找到油量消耗最多的点，然后让其最后经过那里。

def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
    diff = [a-b for a, b in zip(gas, cost)]
    acc = list(itertools.accumulate(diff))
    if sum(diff) < 0: return -1
    ans = acc.index(min(acc)) + 1 
    return ans if ans < len(gas) else 0

方法二：这个方法遍历一次，one-pass，想想原理其实一样。

def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
    gas_left = gas_needed = start = 0
    for i, (g, c) in enumerate(zip(gas, cost)):
        gas_left += g - c
        if gas_left < 0:
            gas_needed -= gas_left
            start = i + 1
            gas_left = 0
    return start if gas_left >= gas_needed else -1

1558. Minimum Numbers of Function Calls to Make Target Array

最小步骤能将全是0的数组变为目标数组。每步可以选择一个元素+1，或者所有元素*2。原题

Input: nums = [1,5]
Output: 5
Explanation: Increment by 1 (second element): [0, 0] to get [0, 1] (1 operation).
Double all the elements: [0, 1] -> [0, 2] -> [0, 4] (2 operations).
Increment by 1 (both elements)  [0, 4] -> [1, 4] -> [1, 5] (2 operations).
Total of operations: 1 + 2 + 2 = 5.

方法一：比赛时想到了这个方法，从后往前算，然后尽量/2，但是感觉会超时，所以没有提交。

def minOperations(self, nums: List[int]) -> int:
    d = nums.index(max(nums))
    
    ans = 0
    while True:
        for i in range(len(nums)):
            if nums[i]& 1 == 1:
                nums[i] -= 1
                ans += 1
        if nums[d] == 0: break
        nums = [n//2 for n in nums]
        ans += 1
        # print(nums, ans)
        
    return ans

方法二：这个方法差一点想出来，没想到用二进制时可以看到规律，/2的操作可以被共享，这点我也想到了，其实是最大数的二进制长度-1，而-1的操作就是每个数字有多少个1，这点没有想到。

def minOperations(self, A: List[int]) -> int:
    return sum(bin(a).count('1') for a in A) + len(format(max(A), 'b')) - 1

1568. Minimum Number of Days to Disconnect Island

把刚好存在一个岛屿变成2个或没有，最少需要几步。每步可以沉没一个格子。原题

Input: grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]
Output: 2
Explanation: We need at least 2 days to get a disconnected grid.
Change land grid[1][1] and grid[0][2] to water and get 2 disconnected island.

方法一：这题需要想明白一件事，对于任意的岛屿，我找一个角沉没它旁边两个，就能将其变成一个单独的岛屿。那么也就是说 最多需要2步就行。

def minDays(self, grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    
    def count(g):
        def sink(i, j):
            if 0<=i<m and 0<=j<n and g[i][j]:
                g[i][j] = 0
                list(map(sink, (i, i, i+1, i-1), (j+1, j-1, j, j)))        
                return 1
            return 0
        return sum(sink(i, j) for i in range(m) for j in range(n))
    
    cnt_g = count(copy.deepcopy(grid))
    if cnt_g == 0 or cnt_g > 1: return 0
    for i in range(m):
        for j in range(n):
            tmp_g = copy.deepcopy(grid)
            tmp_g[i][j] = 0
            if count(tmp_g)!=1:
                return 1
    return 2

方法二：不用深拷贝，用集合判断点是否重复。

def minDays(self, grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])

    seen = set()
    
    def count(g):
        def sink(i, j):
            if 0<=i<m and 0<=j<n and (i, j) not in seen and g[i][j]:
                seen.add((i, j))
                list(map(sink, (i, i, i+1, i-1), (j+1, j-1, j, j)))        
                return 1
            return 0
        return sum(sink(i, j) for i in range(m) for j in range(n))
    
    cnt_g = count(grid)
    seen.clear()
    if cnt_g == 0 or cnt_g > 1: return 0
    for i in range(m):
        for j in range(n):
            if grid[i][j]:
                grid[i][j] = 0
                if count(grid)!=1:
                    return 1
                grid[i][j] = 1
                seen.clear()
    return 2

1567. Maximum Length of Subarray With Positive Product

最长的子数组累乘为正数。原题

Input: nums = [1,-2,-3,4]
Output: 4
Explanation: The array nums already has a positive product of 24.
Input: nums = [0,1,-2,-3,-4]
Output: 3

方法一：比赛时的方法。这题作为竞赛第二题有点稍难，但还是完成了。

def getMaxLen(self, nums: List[int]) -> int:
    # [1, 0, -2, 4, 3, 1]
    start = ans = 0
    flag = 1
    q = collections.deque()
    for end in range(len(nums)):
        if nums[end] == 0:
            start = end+1
            if flag:
                ans = max(ans, end-start)
            else:
                ans = max(ans, end-q[0]-1)
            q.clear()
            flag = 1
            continue
        elif nums[end] > 0:
            pass
        else:
            q.append(end)
            flag ^= 1
            
        if flag:
            ans = max(ans, end-start+1)
        else:
            ans = max(ans, end-q[0])
    return ans

方法二：0这个元素不是很好判断，所以先将数组以0分割。

def getMaxLen(self, nums: List[int]) -> int:
    trip_zeros = []
    for num in nums:
        if num:
            if trip_zeros: trip_zeros[-1].append(num)
            else: trip_zeros.append([num])
        else:
            trip_zeros.append([])
    
    def count(arr):
        start = ans = 0
        left_neg = None
        pos = 1
        for end in range(len(arr)):
            if arr[end] < 0:
                if left_neg is None:
                    left_neg = end
                pos ^= 1
            if pos:
                ans = max(ans, end-start+1)
            else:
                ans = max(ans, end-left_neg)
        return ans
    
    return max(map(count, trip_zeros))

方法三：dp方法。这个方法有用，有一道dp的类似题，152号题。

def getMaxLen(self, nums: List[int]) -> int:
    n = len(nums)
    pos, neg = [0] * n, [0] * n
    if nums[0] > 0: pos[0] = 1
    if nums[0] < 0: neg[0] = 1
    ans = pos[0]
    for i in range(1, n):
        if nums[i] > 0:
            pos[i] = 1 + pos[i - 1]
            neg[i] = (1 + neg[i - 1]) * (neg[i - 1] != 0)
        elif nums[i] < 0:
            pos[i] = (1 + neg[i - 1]) * (neg[i - 1] != 0)
            neg[i] = 1 + pos[i - 1]
        ans = max(ans, pos[i])
    return ans

881. Boats to Save People

最少需要多少小船救人。小船限重为limit，最多能装俩人。根据人的重量，最少需要多少小船。原题

Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)

方法一：抱着超时的心态提交，居然ac了。但是太慢了。

def numRescueBoats(self, people: List[int], limit: int) -> int:
    c = Counter(people)
    ans = 0
    for i in range(1, limit+1):
        while c[i]>0:
            c[i] -= 1
            ans += 1
            p = limit - i
            for j in range(p, i-1, -1):
                if c[j]:
                    c[j] -= 1
                    break
    return ans

方法二：要从肥的人考虑，这样简单一些。

def numRescueBoats(self, people: List[int], limit: int) -> int:
    q = collections.deque(sorted(people, reverse=True))
    ans = 0
    while q:
        fat = q.popleft()
        ans += 1
        if q and q[-1] + fat <= limit:
            q.pop()
    return ans

方法三：用指针。

def numRescueBoats(self, p: List[int], limit: int) -> int:
    p.sort()
    ans = 0
    i, j = 0, len(p)-1
    while i <= j:
        fat = p[j]
        j -= 1
        ans += 1
        if fat+p[i] <= limit:
            i += 1
    return ans

方法四：Lee的方法，用i表示Ans。

def numRescueBoats(self, p: List[int], limit: int) -> int:
    p.sort(reverse=True)
    i, j = 0, len(p)-1
    while i <= j:
        if p[j]+p[i] <= limit:
            j -= 1
        i += 1
    return i

1405. Longest Happy String

最长的欢乐字符串，有’abc’3个字符组成，并且不存在’aaa’这种三连的情况。给定每个字符的个数，问最长可以生成多长的这样的字符串。原题

Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.

方法一：用最大堆实现，注意这里选择第二多元素时要添加一个字符，因为有时候第二个字符可能不够分割。

def longestDiverseString(self, a: int, b: int, c: int) -> str:
    ans = ''
    lt = [(-a, 'a'), (-b, 'b'), (-c, 'c')]
    heapq.heapify(lt)
    while lt:
        max_d, char = heapq.heappop(lt)
        if ans[-2:]==char*2:
            if not lt:
                break
            snd_d, char2 = heapq.heappop(lt)
            ans += char2*min(-snd_d, 1)
            snd_d += 1
            if snd_d < 0:
                heapq.heappush(lt, (snd_d, char2))
        else:
            ans += char*min(-max_d, 2)
            max_d += 2
        if max_d < 0:
            heapq.heappush(lt, (max_d, char))

    return ans

870. Advantage Shuffle

将A重新排序，使得对应位置>B的数尽可能地多。原题

Input: A = [2,7,11,15], B = [1,10,4,11]
Output: [2,11,7,15]

方法一：很直观的贪心算法。将AB排序。每次拿出最大的和B最大的比，如果比不过，就拿最小的顶上。类似于田忌赛马。

def advantageCount(self, A: List[int], B: List[int]) -> List[int]:
    q = collections.deque(sorted(A))
    ans = [0] * len(A)
    B = reversed(sorted((b, i) for i, b in enumerate(B)))
    for b, i in B:
        if q[-1] <= b:
            ans[i] = q.popleft()
        else:
            ans[i] = q.pop()
    return ans

方法二：这个方法很新颖，把能赢的位置放到take中。然后A会剩下一部分，这部分顺序已经无所谓了，所以当take不到时，就从A随便返回一个就行了

def advantageCount(self, A: List[int], B: List[int]) -> List[int]:
    A.sort()
    take = collections.defaultdict(list)
    for b in sorted(B, reverse=True):
        if b < A[-1]: take[b].append(A.pop())
    return [(take[b] or A).pop() for b in B]

861. Score After Flipping Matrix

一个二维矩阵，可以按行，列翻转，问最大每行和是多少。原题

Input: [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
Output: 39
Explanation:
Toggled to [[1,1,1,1],[1,0,0,1],[1,1,1,1]].
0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

方法一：贪心，首先保证行首位是1，然后列翻转时保证多余一半1.

def matrixScore(self, A: 'List[List[int]]') -> 'int':
    m, n = len(A), len(A[0])
    for i in range(m):
        if A[i][0] == 0:
            A[i] = [A[i][j]^1 for j in range(n)]
    ans = 0
    for i, cols in enumerate(list(zip(*A))[::-1]):
        ans += 2**i * max(sum(cols), m-sum(cols))
    return ans

方法二：Lee215的方法。首先保证行首是1，但是并没有实际翻过来，后序通过跟行首比较，判断翻过后的值。

def matrixScore(self, A: List[List[int]]) -> int:
    M, N = len(A), len(A[0])
    ans = (1 << N-1) * M
    for j in range(1, N):
        cur = sum(A[i][j]==A[i][0] for i in range(M))
        ans += max(cur, M-cur) * (1 << N-1-j)
    return ans

452. Minimum Number of Arrows to Burst Balloons

有很多个气球绑在了水平线上，给了这些气球的start, end表示和水平线相交的点。问最少需要多少个飞镖才能将所有气球扎坏。

Input:
[[10,16], [2,8], [1,6], [7,12]]

Output:
2

Explanation:
One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).

方法一：贪心法，尽量扎多点。

def findMinArrowShots(self, points: List[List[int]]) -> int:
    ans = 0
    points.sort(key=lambda x: x[1], reverse=True)
    while points:
        ans += 1
        s, e = points.pop()
        while points and points[-1][0]<=e:
            points.pop()
    return ans

方法二：for循环也可以。

def findMinArrowShots(self, points: List[List[int]]) -> int:
    ans, e = 0, float('-inf')
    for start, end in sorted(points, key=itemgetter(1)):
        if start > e:
            ans += 1
            e = end
    return ans

1589. Maximum Sum Obtained of Any Permutation

说要查询某一段，进行n次查询，问将数组如何排列能使线段的总和最大。

方法一：这题竞赛时没做出来，心态崩了。不知道怎么构造一个对线段的计数，用Counter超时了。剩下的一小时就是拼命地构造一个不重复的线段tuple，最后也没完成。正确的思路是这样的，在线段的起点+1，结束点后一位-1，这样在累加的时候就会把这段1都算出来。

def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
    n = len(nums)
    imos = [0] * (n + 1)
    for l, r in requests:
        imos[l] += 1
        imos[r + 1] -= 1
    for i in range(n):
        imos[i+1] += imos[i]
    del imos[-1]
    ans = 0
    for i, v in zip(sorted(nums), sorted(imos)):
        ans += i * v
        ans %= 10 ** 9 + 7
    return ans

1599. Maximum Profit of Operating a Centennial Wheel

这题看起来很复杂，作为竞赛第二题还算可以。有这样一个摩天轮，一次只能上4个人，转一次要花费runningCost，门票boardingCost。给定一个游客时间人数队列，问最大利润时在第几轮（摩天轮转了多少圈）。

方法一：竞赛时的答案擦边过的。

def minOperationsMaxProfit(self, cust: List[int], bc: int, rc: int) -> int:
    cust.reverse()
    wait, profit, t, max_p, ans = 0, 0, 0, float('-inf'), 0
    while cust or wait:
        if cust:
            wait += cust.pop()
        if wait >= 4:
            profit += 4 * bc
        else:
            profit += wait * bc
        wait = max(0, wait-4)
        profit -= rc
        t += 1
        if profit > max_p:
            ans = t
            max_p = profit
    return ans if max_p>0 else -1

方法二：实际上最后需要一个取余操作就行，不用再模拟了。

def minOperationsMaxProfit(self, cust: List[int], bc: int, rc: int) -> int:
    ans = -1
    most = profit = wait = 0
    for i, c in enumerate(cust, 1):
        wait += c
        wait -= (cur := min(4, wait))
        profit += bc*cur - rc
        if profit > most:
            ans, most = i, profit
    q, r = divmod(wait, 4)
    if 4*bc - rc > 0: ans += q
    if r*bc - rc > 0: ans += 1
    return ans

1605. Find Valid Matrix Given Row and Column Sums

给定一个二维数组行的和与列的和，求这个二维数组，答案不唯一。

方法一：这道题比赛用回溯法写的，超时了一次，然后改为倒序勉强过了。其实可以用贪心，每次都尽量将最大的数填进去，但是并不知道怎么证明。Lee也没有给出很好的证明方式。

def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:
    M, N = len(rowSum), len(colSum)
    g = [[0]*N for _ in range(M)]
    for i in range(M):
        for j in range(N):
            g[i][j] = min(rowSum[i], colSum[j])
            rowSum[i] -= g[i][j]
            colSum[j] -= g[i][j]
    return g

1616. Split Two Strings to Make Palindrome

从某个索引出切断两个字符串，相互拼接是否能组成回文串。

Input: a = "ulacfd", b = "jizalu"
Output: true
Explaination: Split them at index 3:
aprefix = "ula", asuffix = "cfd"
bprefix = "jiz", bsuffix = "alu"
Then, aprefix + bsuffix = "ula" + "alu" = "ulaalu", which is a palindrome.

方法一：竞赛时最后一分钟做了出来，顶着压力AC了。不过之前超时了两次，妄想用暴力法过，没有得逞。整理一下代码。以每个字符串中心找最大的回文串，然后比较相互的头尾相交。

def checkPalindromeFormation(self, a: str, b: str) -> bool:
    
    def max_palindrome_by_center(s):
        n = len(s)
        l, r = (n-1)//2, n//2
        while l >= 0 and s[l]==s[r]:
            l -= 1
            r += 1
        return l, r
    
    i, j = max_palindrome_by_center(a)
    ans = [b[:i+1] + a[j:], a[:i+1] + b[j:]]
    i, j = max_palindrome_by_center(b)
    ans.extend([a[:i+1] + b[j:], b[:i+1] + a[j:]])
    return any(s==s[::-1] for s in ans)

方法二：Lee的方法。从头尾找相同，判断中间是否回文。

def checkPalindromeFormation(self, a: str, b: str) -> bool:
    i, j = 0, len(a)-1
    while i<j and a[i]==b[j]:
        i += 1
        j -= 1
    s1, s2 = a[i:j+1], b[i:j+1]
    
    i, j = 0, len(a)-1
    while i<j and b[i]==a[j]:
        i += 1
        j -= 1
    s3, s4 = a[i:j+1], b[i:j+1]
    return any(s==s[::-1] for s in (s1, s2, s3, s4))

可以封装一下。这个方法确实比我的简单一点。

def checkPalindromeFormation(self, a: str, b: str) -> bool:
    
    def get_middle(a, b):
        i, j = 0, len(a)-1
        while i<j and a[i]==b[j]:
            i += 1
            j -= 1
        return a[i:j+1], b[i:j+1]
    
    return any(s==s[::-1] for s in get_middle(a, b)+get_middle(b, a))

948. Bag of Tokens

你的初始能量为 P，初始分数为 0，只有一包令牌。令牌的值为 token[i]，每个令牌最多只能使用一次，可能的两种使用方法如下：如果你至少有 token[i] 点能量，可以将令牌置为正面朝上，失去 token[i] 点能量，并得到 1 分。如果我们至少有 1 分，可以将令牌置为反面朝上，获得 token[i] 点能量，并失去 1 分。在使用任意数量的令牌后，返回我们可以得到的最大分数。

Input: tokens = [100,200,300,400], P = 200
Output: 2
Explanation: Play the tokens in this order to get a score of 2:
1. Play the 0th token (100) face up, your power becomes 100 and score becomes 1.
2. Play the 3rd token (400) face down, your power becomes 500 and score becomes 0.
3. Play the 1st token (200) face up, your power becomes 300 and score becomes 1.
4. Play the 2nd token (300) face up, your power becomes 0 and score becomes 2.

方法一：双指针。很容易想到是贪心，因为分数都是一样的，以最少的能量换最多的分。10分钟AC。

def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
    ans, cur_score, p = 0, 0, P
    tokens.sort()
    lo, hi = 0, len(tokens)-1
    while lo <= hi:
        if tokens[lo] <= p:
            p -= tokens[lo]
            lo += 1
            cur_score += 1
            ans = max(ans, cur_score)
        elif cur_score > 0:
            p += tokens[hi]
            hi -= 1
            cur_score -= 1
        else:
            break
    return ans

方法二：Lee的写法，deque，将判断放到while 中了。

def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
    ans, cur_score = 0, 0
    q = deque(sorted(tokens))
    while q and (q[0]<=P or cur_score):
        if q[0] <= P:
            cur_score += 1
            P -= q.popleft()
        else:
            cur_score -= 1
            P += q.pop()
        ans = max(ans, cur_score)
    return ans

135. Candy

N个学生站成一排，每个人有个比率，要求每人至少发一块糖，比率如果比挨着的两位同学大，那么糖要比他们多。问最少需要多少个糖。

方法一：左右遍历两次。从左向右遍历之后，保证每人比左侧大的条件，再从右向左遍历，保证每人比左侧大的条件。注意13452的情况，反向遍历时要去最大值。因为左侧遍历完事12341。

def candy(self, ratings: List[int]) -> int:
    N = len(ratings)
    if N <= 1:
        return N
    candies = [1] * N
    for i in range(1, N):
        if ratings[i] > ratings[i-1]:
            candies[i] = candies[i-1] + 1
    
    for i in range(N-1, 0, -1):
        if ratings[i] < ratings[i-1]:
            candies[i-1] = max(candies[i-1], candies[i]+1)
            
    return sum(candies)

646. Maximum Length of Pair Chain

能组成的最长的链。和300题一样。

Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]

方法一：dp, O(n^2)的暴力方法。

def findLongestChain(self, pairs: List[List[int]]) -> int:
    n = len(pairs)
    dp = [1] * (n+1)
    pairs.sort()
    for i in range(1, n):
        for j in range(i):
            if pairs[i][0] > pairs[j][1]:
                dp[i] = max(dp[i], dp[j]+1)
    return pairs and max(dp) or 0

方法二：此题优化的解法不能像300一样用二分，因为有两个维度的信息需要考虑，最优的解法是贪心。

def findLongestChain(self, pairs: List[List[int]]) -> int:
    ans, last = 0, float('-inf')
    for start, end in sorted(pairs, key=itemgetter(1)):
        if last < start:
            ans += 1
            last = end
    return ans

1647. Minimum Deletions to Make Character Frequencies Unique

最少需要删除多少次字母使得每个字母的频率都不一样。

Input: s = "aaabbbcc"
Output: 2
Explanation: You can delete two 'b's resulting in the good string "aaabcc".
Another way it to delete one 'b' and one 'c' resulting in the good string "aaabbc".

方法一：比赛时写得比较直观的方法。

def minDeletions(self, s: str) -> int:
    c = Counter(s)
    cnt = Counter(c.values())
    ans = 0
    for k in sorted(cnt.keys()):
        while cnt[k] > 1:
            for j in range(k)[::-1]:
                if j == 0:
                    cnt[k] -= 1
                    ans += k
                elif cnt[j] == 0:
                    cnt[k] -= 1
                    cnt[j] = 1
                    ans += k-j
                    break
    return ans

方法二：可以用一个集合来做去重的工作。

def minDeletions(self, s: str) -> int:
    ans, seen = 0, set()
    for cnt in sorted(Counter(s).values(), reverse=True):
        while cnt in seen:
            cnt -= 1
            ans += 1
        if cnt: 
            seen.add(cnt)
    return ans

1648. Sell Diminishing-Valued Colored Balls

有这么几种颜色的球，每种球有一些个数。当取出一个球的时候，分数为剩下同种颜色的球，问一共需要取orders个球，问最大的分是多少？

Input: inventory = [2,5], orders = 4
Output: 14
Explanation: Sell the 1st color 1 time (2) and the 2nd color 3 times (5 + 4 + 3).
The maximum total value is 2 + 5 + 4 + 3 = 14.

方法一：很容易看出是一道贪心的题，比赛时超时了一次，因为想用堆来模拟。后来想到了用数学的方式。就是尽量将所有的剩下球平均，因为越少拿球分就越少。这里用了一个动态的求平均的方式。不是最优解，700+ms，beats 30%，还有很大的优化空间。

def maxProfit(self, inventory: List[int], orders: int) -> int:
    ans, mod = 0, 10**9+7
    total = sum(inventory) 
    inventory.sort()
    remain = total - orders
    N = len(inventory)
    for i, d in enumerate(inventory):
        each = remain // (N-i)
        if d > each:
            ans += (each+1+d) * (d-each) // 2
        remain -= min(each, d)
    return ans % mod

1653. Minimum Deletions to Make String Balanced

最少的步数可以让字符串中没有b在a前的情况。

Input: s = "aababbab"
Output: 2
Explanation: You can either:
Delete the characters at 0-indexed positions 2 and 6 ("aababbab" -> "aaabbb"), or
Delete the characters at 0-indexed positions 3 and 6 ("aababbab" -> "aabbbb").

方法一：比赛时想着和秋叶收藏集一题很像，就用了dp，也能过，不过不是最优。

def minimumDeletions(self, s: str) -> int:
    a, b, ab = int(s[0]!='a'), int(s[0]!='b'), float('inf')
    for i in range(1, len(s)):
        cur = int(s[i]!='a')
        a, b, ab = a+cur, b+(cur^1), min(a, ab)+(cur^1)
    return min(a, b, ab)

方法二：贪心。分为两种情况，一种将后面的a全部删掉；一种将前面的b全部删掉。

def minimumDeletions(self, s: str) -> int:
    cur = res = s.count('a')
    for c in s:
        if c == 'a':
            cur -= 1
        else:
            cur += 1
        res = min(res, cur)
    return res

1663. Smallest String With A Given Numeric Value

每个字母对应一个值，给定一个长度为n的条件，求这个条件字符总和为k的最小字典序的字符串。

Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.

方法一：这题我想错了一个点，z对应的是26而不是25。导致用了1个小时才提交上。周赛第一题用了44秒的好成绩都浪费掉了。

def getSmallestString(self, n: int, k: int) -> str:
    ans = ''
    for i in range(n):
        if n*26 == k:
            ans += n * 'z'
            break
        elif k-1 <= (n-1)*26:
            ans += 'a'
            n -= 1
            k -= 1
        else:
            m = k - (n-1)*26
            ans += chr(ord('a') + m -1)
            n -= 1
            k -= m
    return ans

方法二：这个思路我想到了，但是没想好代码，本质上这个字符串就是aaxzzz。所以用数学的思路可以直接求出。

def getSmallestString(self, n: int, k: int) -> str:
    num2 = (k-n) // 25     
    num1 = n - num2 - 1
    num = k - (num1 + num2 * 26)
    return 'a' * num1 + chr(num+ord('a')-1) + 'z' * num2

1664. Ways to Make a Fair Array

删除一个数使得数组奇数位偶数位和相等，一共有多少种删除的方法。

Input: nums = [2,1,6,4]
Output: 1
Explanation:
Remove index 0: [1,6,4] -> Even sum: 1 + 4 = 5. Odd sum: 6. Not fair.
Remove index 1: [2,6,4] -> Even sum: 2 + 4 = 6. Odd sum: 6. Fair.
Remove index 2: [2,1,4] -> Even sum: 2 + 4 = 6. Odd sum: 1. Not fair.
Remove index 3: [2,1,6] -> Even sum: 2 + 6 = 8. Odd sum: 1. Not fair.
There is 1 index that you can remove to make nums fair.

方法一：前缀和，竞赛时想到了，但是没做出来，因为看错了题，忽略了删除一次这个条件。这里是Lee的写法，维持一个当前的奇偶和与右侧的奇偶和，当删除某个数后，后面的奇偶位互换。

def waysToMakeFair(self, nums: List[int]) -> int:
    res = 0
    acc, total = [0, 0], [sum(nums[::2]), sum(nums[1::2])]
    for i, num in enumerate(nums):
        total[i%2] -= num
        res += acc[0]+total[1]==acc[1]+total[0]
        acc[i%2] += num
    return res

767. Reorganize String

重排字符串使其没有相邻的两个字符使相同的。

Input: S = "aab"
Output: "aba"

方法一：使用堆实现的。每次从堆中取一个或两个。

def reorganizeString(self, S: str) -> str:
    heap = [(-cnt, c) for c, cnt in Counter(S).items()]
    heapq.heapify(heap)
    res = []
    while heap:
        cnt_1, c1 = heapq.heappop(heap)
        if res and res[-1]==c1:
            if not heap:
                return ''
            cnt_2, c2 = heapq.heappop(heap)
            res.append(c2)
            cnt_2 += 1
            heapq.heappush(heap, (cnt_1, c1))
            if cnt_2:
                heapq.heappush(heap, (cnt_2, c2))
        else:
            res.append(c1)
            cnt_1 += 1
            if cnt_1:
                heapq.heappush(heap, (cnt_1, c1))
    return ''.join(res)

方法二：by @Stefan。为何内层也要sorted一下，是因为[a, b, b, a]会保留原来的相对顺序。

def reorganizeString(self, S: str) -> str:
    a = sorted(sorted(S), key=S.count)
    h = len(a) // 2
    a[1::2], a[::2] = a[:h], a[h:]
    return ''.join(a) * (a[-1:] != a[-2:-1])

659. Split Array into Consecutive Subsequences

将一个升序的数组，拆分重连续的子数组段，长度不能小于3.

Input: [1,2,3,3,4,4,5,5]
Output: True
Explanation:
You can split them into two consecutive subsequences : 
1, 2, 3, 4, 5
3, 4, 5

方法一：By@lee215。挺难想的方法，left表示每个数剩了多少个。end表示以这个数结尾的有几个。当我没法将当前的数追加到前一段的结尾时，也没法找到后两个连续的数时，就不能拆分成功。

def isPossible(self, A: List[int]) -> bool:
    left = collections.Counter(A)
    end = collections.Counter()
    for i in A:
        if not left[i]: continue
        left[i] -= 1
        if end[i - 1] > 0:
            end[i - 1] -= 1
            end[i] += 1
        elif left[i + 1] and left[i + 2]:
            left[i + 1] -= 1
            left[i + 2] -= 1
            end[i + 2] += 1
        else:
            return False
        print(left, end)
    return True

1702. Maximum Binary String After Change

对于一个二进制的字符串，你可以将00变成10, 也可以将10变成01，问可以变成的表示最大的十进制的数对应的字符串是多少。

Input: binary = "000110"
Output: "111011"
Explanation: A valid transformation sequence can be:
"000110" -> "000101" 
"000101" -> "100101" 
"100101" -> "110101" 
"110101" -> "110011" 
"110011" -> "111011"

方法一：竞赛时想出来了，无非是找到规律就行，代码写的过于冗长。思路是开头的1不用管，将后面所有的0冒泡到最高位，0000可以变成1110，最后以一些1结尾。这里是Lee的优雅写法

def maximumBinaryString(self, binary: str) -> str:
    if '0' not in s: return s
    k, n = s.count('1', s.find('0')), len(s)
    return '1' * (n - k - 1) + '0' + '1' * k

1727. Largest Submatrix With Rearrangements

重新排列二维矩阵，可以得到的最大的都是1的矩阵面积是多少。

Input: matrix = [[0,0,1],[1,1,1],[1,0,1]]
Output: 4
Explanation: You can rearrange the columns as shown above.
The largest submatrix of 1s, in bold, has an area of 4.

方法一：比赛时没有做出来，想到了贪心和排序，但是没想到列的怎么保持一致的顺序。此题和84，85很像，印象不深，所以没有关联上。从列上从上至下做一个累加，所以累加的数都到了一行，这样再排序每行都是独立的。

def largestSubmatrix(self, matrix: List[List[int]]) -> int:
    M, N = len(matrix), len(matrix[0])
    res = 0
    for i in range(M):
        for j in range(N):
            matrix[i][j] += matrix[i-1][j] * matrix[i][j] * (i>=1)
        arr = sorted(matrix[i], reverse = True)
        for j in range(N):
            res = max(res, (j+1) * arr[j])
    return res

1737. Change Minimum Characters to Satisfy One of Three Conditions

给定两个字符串a和b，都是由小写字母组成。然后每次允许将任意字符串的一个字符改成任意一个字符最后满足下列三种条件之一：问最小操作步数是多少。1. a的所有字符严格小于b；2：b的所有字符严格小于a；3：a，b都是一种相同的字符。

Input: a = "aba", b = "caa"
Output: 2
Explanation: Consider the best way to make each condition true:
1) Change b to "ccc" in 2 operations, then every letter in a is less than every letter in b.
2) Change a to "bbb" and b to "aaa" in 3 operations, then every letter in b is less than every letter in a.
3) Change a to "aaa" and b to "aaa" in 2 operations, then a and b consist of one distinct letter.
The best way was done in 2 operations (either condition 1 or condition 3).
Input: a = "dabadd", b = "cda"
Output: 3
Explanation: The best way is to make condition 1 true by changing b to "eee".

方法一：竞赛时没有做出来，就差一点。第三种条件很容易想到。前两种不好想，需要用到前缀和+错位。这点我想到了，没想到是以分割字符来暴力枚举。将a,b字符串转成字母计数的数组，以a~y中的字母d来分割，a串全部小于等于d，b串全部大于d。

def minCharacters(self, a: str, b: str) -> int:
    c_a, c_b = Counter(a), Counter(b)
    res = len(a) + len(b) - max((c_a + c_b).values())
    lst_a = []
    lst_b = []
    for d in string.ascii_lowercase:
        lst_a.append(c_a[d])
        lst_b.append(c_b[d])

    r_pre_sum_a = list(accumulate(lst_a[::-1]))[::-1]
    pre_sum_b = list(accumulate(lst_b))
    for i in range(1, 26):
        res = min(res, r_pre_sum_a[i]+pre_sum_b[i-1])

    r_pre_sum_b = list(accumulate(lst_b[::-1]))[::-1]
    pre_sum_a = list(accumulate(lst_a))
    for i in range(1, 26):
        res = min(res, r_pre_sum_b[i]+pre_sum_a[i-1])
    return res

方法二：可以用总和减去前缀和来求得后缀和。Lee的方法。

def minCharacters(self, a: str, b: str) -> int:
    m, n = len(a), len(b)
    c1 = Counter(ord(c) - 97 for c in a)
    c2 = Counter(ord(c) - 97 for c in b)
    res = m + n - max((c1+c2).values())
    for i in range(25):
        c1[i+1] += c1[i]
        c2[i+1] += c2[i]
        res = min(res, m - c1[i] + c2[i]) # condition 1
        res = min(res, n - c2[i] + c1[i]) # condition 2
    return res

1665. Minimum Initial Energy to Finish Tasks

最少需要多少能量完成所有的任务。每个任务有一个最低能量和消耗的能量。

Input: tasks = [[1,2],[2,4],[4,8]]
Output: 8
Explanation:
Starting with 8 energy, we finish the tasks in the following order:
    - 3rd task. Now energy = 8 - 4 = 4.
    - 2nd task. Now energy = 4 - 2 = 2.
    - 1st task. Now energy = 2 - 1 = 1.
Notice that even though we have leftover energy, starting with 7 energy does not work because we cannot do the 3rd task.

方法一：很容易想到贪心，要排序，但是根据什么排序很重要。因为 minimum 表示的是”开始做这个任务的时候，拥有的最小能量值是多少“；actual 则是”做这个任务所消耗的能量值“。所以，minimum - actual 的结果，就是”完成这个任务以后，剩余的能量值的最小值“。为了完成所有的任务，我们显然希望剩余的能量值越多越好。所以，我们应该先完成“使得剩余的能量值多的任务”，即 minimum - actual 大的任务；这样有更多的能量，去完成别的任务。

def minimumEffort(self, tasks: List[List[int]]) -> int:
    res = 0
    for a, m in sorted(tasks, key=lambda x: x[1]-x[0]):
        res += a
        res = max(res, m)
    return res

1754. Largest Merge Of Two Strings

合并两个字符串，字典序最大。每次从两个单词开头拿字符。

Input: word1 = "cabaa", word2 = "bcaaa"
Output: "cbcabaaaaa"
Explanation: One way to get the lexicographically largest merge is:
- Take from word1: merge = "c", word1 = "abaa", word2 = "bcaaa"
- Take from word2: merge = "cb", word1 = "abaa", word2 = "caaa"
- Take from word2: merge = "cbc", word1 = "abaa", word2 = "aaa"
- Take from word1: merge = "cbca", word1 = "baa", word2 = "aaa"
- Take from word1: merge = "cbcab", word1 = "aa", word2 = "aaa"
- Append the remaining 5 a's from word1 and word2 at the end of merge.

方法一：模拟。

def largestMerge(self, word1: str, word2: str) -> str:

    def is_larger(a, b):
        for c1, c2 in zip_longest(reversed(a), reversed(b), fillvalue='-'):
            if c1 > c2:
                return True
            elif c1 < c2:
                return False
        return True

    s1, s2 = list(word1)[::-1], list(word2)[::-1]
    res = []
    while s1 or s2:
        if is_larger(s1, s2):
            res.append(s1.pop())
        else:
            res.append(s2.pop())
    return ''.join(res)

方法二：递归。

def largestMerge(self, s1: str, s2: str) -> str:
    if s1 >= s2 > '':
        return s1[0] + self.largestMerge(s1[1:], s2)
    if s2 >= s1 > '':
        return s2[0] + self.largestMerge(s1, s2[1:])
    return s1 + s2

1591. Strange Printer II

二维矩阵中，每次能打一个递增的数字，但是必须打出矩形，后打的字可以覆盖之前的，问一个结果是否能被打印出来。

Input: targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]
Output: true

方法一：此题需要逆向思维，将数字还原为0。需要注意一点，不能排序从大到小因为，可能有[4,3,3,4]的情况。所以判断条件是，当所有的颜色都不能透过矩形变小时，返回False。遍历过程中可以置为0，因为当大数可打印时，其可以替换为任何比它小的数字，相当于万能，所以在检测到矩形时，就将其置为0.

def isPrintable(self, g: List[List[int]]) -> bool:
    colors = set()
    M, N = len(g), len(g[0])
    pos = [[M, N, 0, 0] for _ in range(61)] 
    for i, row in enumerate(g):
        for j, d in enumerate(row):
            colors.add(d)
            pos[d][0] = min(pos[d][0], i)
            pos[d][1] = min(pos[d][1], j)
            pos[d][2] = max(pos[d][2], i)
            pos[d][3] = max(pos[d][3], j)

    def check(d):
        for i in range(pos[d][0], pos[d][2]+1):
            for j in range(pos[d][1], pos[d][3]+1):
                if g[i][j]>0 and g[i][j]!=d:
                    return False
        for i in range(pos[d][0], pos[d][2]+1):
            for j in range(pos[d][1], pos[d][3]+1):
                g[i][j] = 0
        return True

    while colors:
        colors2 = set()
        for d in colors:
            if not check(d):
                colors2.add(d)
        if len(colors) == len(colors2):
            return False
        colors = colors2
    return True

1793. Maximum Score of a Good Subarray

从数组k的位置向两侧延伸，子数组分数（最小值*长度）最大为多少

Input: nums = [1,4,3,7,4,5], k = 3
Output: 15
Explanation: The optimal subarray is (1, 5) with a score of min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15.

方法一：这周周赛简单，作为第四题过于简单。我这里想了最后才用了二分法做出来。

def maximumScore(self, nums: List[int], k: int) -> int:
    right = list(accumulate(nums[k:], min))
    left = list(accumulate(nums[:k][::-1], min))[::-1]
    min_nums = left + right
    res = 0
    for num in sorted(set(min_nums)):
        i = bisect_left(left, num)
        j = bisect_left(right[::-1], num)
        j = len(right)-j+k
        if i <= k and j>k:
            res = max(res, num*(j-i))
    return res

方法二：贪心，双指针。就尽量让最小值减少得慢。

def maximumScore(self, nums: List[int], k: int) -> int:
    res = mini = nums[k]
    i, j, n = k, k, len(nums)
    while i>0 or j<n-1:
        if (nums[i-1] if i else 0) >= (nums[j+1] if j<n-1 else 0):
            i -= 1
        else:
            j += 1
        mini = min(mini, nums[i], nums[j])
        res = max(res, mini*(j-i+1))
    return res

1806. Minimum Number of Operations to Reinitialize a Permutation

操作多少次，数组能变回原样

• If i % 2 == 0, then arr[i] = perm[i / 2].
• If i % 2 == 1, then arr[i] = perm[n / 2 + (i - 1) / 2].

Input: n = 4
Output: 2
Explanation: prem = [0,1,2,3] initially.
After the 1st operation, prem = [0,2,1,3]
After the 2nd operation, prem = [0,1,2,3]
So it takes only 2 operations.

方法一：比较简单，写法上有点 丑陋。

def reinitializePermutation(self, n: int) -> int:
    first = False
    i = 1
    i *= 2
    if i > n-1:
        i -= n-1
    res = 1
    while i != 1:
        i *= 2
        if i > n-1:
            i -= n-1
        res += 1
    return res

方法二：Lee215的方法。

def reinitializePermutation(self, n: int) -> int:
    res, i = 0, 1
    while res==0 or i > 1:
        i = i * 2 % (n-1)
        res += 1
    return res