LeetCode算法题整理（哈希篇）hashtable

1. Two Sum

给定一个数组，找出数组两个元素相加为目标值，假定只有唯一解。原题

1
2
3

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

def two_sum(nums, target):
    buff_dict = {}
    for i, num in enumerate(nums):
        if num not in buff_dict:
            buff_dict[target-num] = i
        else:
            return [buff_dict[num], i]

15. 3Sum

找出3个数相加为0的所有组合。

方法一：固定一个数，再通过双指针找另外两个。

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
        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

18. 4Sum

找出4个数和为target的组合。

方法一：还是根据3sum的方法进行修改。

def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
    def three_sum(ary, target):
        res, N = [], len(ary)
        for i in range(N-2):
            a = ary[i]
            if i!=0 and a==ary[i-1]:
                continue
            lo, hi = i+1, N-1
            while lo < hi:
                total = ary[lo] + ary[hi]
                if total < target-a:
                    lo += 1
                elif total > target-a:
                    hi -= 1
                else:
                    while lo<hi and ary[lo]==ary[lo+1]:
                        lo += 1
                    while lo<hi and ary[hi]==ary[hi-1]:
                        hi -= 1
                    res.append([a, ary[lo], ary[hi]])
                    lo += 1
                    hi -= 1
        return res
    
    nums.sort()
    ans = []
    for i, d in enumerate(nums[:-3]):
        if i == 0 or nums[i] != nums[i-1]:
            three_res = three_sum(nums[i+1:], target-d)
            for res in three_res:
                ans.append([d] + res)
    return ans

454. 4Sum II

在四个数组中每个各选出一个，使得它们所有的和为0。

Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:
2

Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

方法一：和18题不同，这里不需要想3Sum之后怎么怎么样，因为3Sum的方法需要排序，而这里没法处理两个数组排序，双指针也比较麻烦了。换一个思路，拆成2个2Sum的子问题。

def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
    ab = defaultdict(int)
    res = 0
    for a in A:
        for b in B:
            ab[-a-b] += 1

    for c in C:
        for d in D:
            res += ab[c+d]
    return res

方法二：和Stenfan学习。

1
2
3

def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
    ab = Counter(-a-b for a in A for b in B)
    return sum(ab[c+d] for c in C for d in D)

720. Longest Word in Dictionary

字典中的最长单词，找出一个列表中的一个单词，该单词的子单词也必须在字典中。相同长度的单词，返回字典序最前的一个。原题

Input: 
words = ["w","wo","wor","worl", "world"]
Output: "world"
Explanation: 
The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

方法一：Brute Force.

def longestWord(self, words):
    res = ''
    wordset = set(words)
    for word in words:
        if len(word)>len(res) or len(word)==len(res) and word<res:
            if all(word[:k] in wordset for k in range(1, len(word))):
                res = word         
    return res

方法二：trie. 暂且留坑。

748. Shortest Completing Word

最短的完整匹配单词。包含`licensePlate`中的所有字母，大小写不敏感。假设答案一定存在。原题

Input: licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]
Output: "steps"
Explanation: The smallest length word that contains the letters "S", "P", "S", and "T".
Note that the answer is not "step", because the letter "s" must occur in the word twice.
Also note that we ignored case for the purposes of comparing whether a letter exists in the word.

方法一：先排序。

def shortestCompletingWord(self, licensePlate: 'str', words: 'List[str]') -> 'str':
    lp = ''.join(x for x in licensePlate.lower() if x.isalpha())
    c1 = collections.Counter(lp)
    words.sort(key=len)
    words = map(str.lower, words)
    for word in words:
        diff = c1 - collections.Counter(word)
        if not diff:
            return word

方法二：more elegant.

def shortestCompletingWord(self, licensePlate: 'str', words: 'List[str]') -> 'str':
    lp = ''.join(x for x in licensePlate.lower() if x.isalpha())
    c1 = collections.Counter(lp)
    words = map(str.lower, words)
    return min((word for word in words 
                if not c1-collections.Counter(word)), key=len)

方法三：most efficient. 认为方法二是在计算-的操作时，涉及一些无关的key导致效率过低。

def shortestCompletingWord(self, licensePlate: 'str', words: 'List[str]') -> 'str':
    ans = ''
    lp = ''.join(x for x in licensePlate.lower() if x.isalpha())
    for w in words:
        temp = list(w.lower())
        for l in lp:
            if l in temp:
                temp.remove(l)
            else:
                break
        else:
            if len(w)<len(ans) or ans=='':
                ans = w
    return ans

811. Subdomain Visit Count

子域名访问量。给定一个三级或二级域名列表，统计所有三级、二级和顶级域名的访问量。原题

Example 1:
Input: 
["9001 discuss.leetcode.com"]
Output: 
["9001 discuss.leetcode.com", "9001 leetcode.com", "9001 com"]
Explanation: 
We only have one website domain: "discuss.leetcode.com". As discussed above, the subdomain "leetcode.com" and "com" will also be visited. So they will all be visited 9001 times.

方法一：Solution中用了Counter，个人认为defaultdict.

def subdomainVisits(self, cpdomains: 'List[str]') -> 'List[str]':
    ans = collections.defaultdict(int)
    for domain in cpdomains:
        count, d = domain.split()
        count = int(count)
        frags = d.split('.')
        for i in range(len(frags)):
            ans['.'.join(frags[i:])] += count
    return ['{} {}'.format(c, d) for d, c in ans.items()]

884. Uncommon Words from Two Sentences

求两句话中的单词，在本句中出现一次，并不在另一句中的单词。也就是在两句中出现一次。原题

1 2	Input: A = "this apple is sweet", B = "this apple is sour" Output: ["sweet","sour"]

方法一：Counter

def uncommonFromSentences(self, A: 'str', B: 'str') -> 'List[str]':
    from collections import Counter
    count = Counter((A + ' ' + B).split())
    return [word for word, c in count.items() if c == 1]

1010. Pairs of Songs With Total Durations Divisible by 60

和能被60整除的为一对，求有多少对。原题

Input: [30,20,150,100,40]
Output: 3
Explanation: Three pairs have a total duration divisible by 60:
(time[0] = 30, time[2] = 150): total duration 180
(time[1] = 20, time[3] = 100): total duration 120
(time[1] = 20, time[4] = 40): total duration 60

def numPairsDivisibleBy60(self, time: List[int]) -> int:
    c = collections.defaultdict(int)
    ans = 0
    for t in time:
        # ans += c[(60-t%60)%60]
        ans += c[-t % 60]
        c[t%60] += 1
    return ans

1138. Alphabet Board Path

小写字母排列的键盘，要打出目标字母需要移动的操作。原题

1 2	Input: target = "leet" Output: "DDR!UURRR!!DDD!"

方法一：此题需要注意z，然后按照一个优先的顺序移动即可。另外使用字典可以快速定位坐标，而不用每个字符做比较

def alphabetBoardPath(self, target: str) -> str:
    import string
    m = {c: (i//5, i%5) for i, c in enumerate(string.ascii_lowercase)}
    ans = ''
    x0 = y0 = 0
    for c in target:
        x, y = m[c]
        if y < y0: ans += 'L' * (y0-y)
        if x < x0: ans += 'U' * (x0-x)
        if y > y0: ans += 'R' * (y-y0)
        if x > x0: ans += 'D' * (x-x0)
        x0, y0 = x, y
        ans += '!'
    return ans

1072. Flip Columns For Maximum Number of Equal Rows

二维数组，翻转某几列可以最多使多少行内的元素都相同。原题

Input: [[0,1],[1,1]]
Output: 1
Explanation: After flipping no values, 1 row has all values equal.

Input: [[0,0,0],[0,0,1],[1,1,0]]
Output: 2
Explanation: After flipping values in the first two columns, the last two rows have equal values.

方法一：核心思想在于找到每行的模式，具有相同模式的行，最终可变成同样的数值。

def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
    c = collections.Counter()
    for row in matrix:
        c[tuple([x for x in row])] += 1
        c[tuple([1-x for x in row])] += 1
    return max(c.values())

方法二：使用异或。方法一中其实有多余的部分，模式与反模式都求了出来，其实没有必要。

1 2	def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int: return max(collections.Counter(tuple(r ^ row[0] for r in row) for row in matrix).values())

1160. Find Words That Can Be Formed by Characters

找出能被目标字符串组成的子串长度和。原题

1
2
3

def countCharacters(self, words: List[str], chars: str) -> int:
    ma = collections.Counter(chars)
    return sum(len(w) for w in words if not collections.Counter(w)-ma)

525. Contiguous Array

找出二进制数组中拥有相等个数0和1的最长子串的长度。原题

1
2
3

Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

方法一：此题解法类似于买卖股票，维护一个count如果是0减一，如果是1加一，那么当count值相等的时候，说明这个子串中有相等1和0。使用一个字典来记录每次count的最小索引。需要注意的是索引从1开始。

def findMaxLength(self, nums: List[int]) -> int:
    count = ans = 0
    table = {0: 0}
    for i, num in enumerate(nums, 1):
        if num == 0:
            count -= 1
        else:
            count += 1
        if count in table:
            ans = max(ans, i-table[count])
        else:
            table[count] = i
            
    return ans

560. Subarray Sum Equals K

子数组和为k的个数。原题

1 2	Input:nums = [1,1,1], k = 2 Output: 2

方法一：累加一开始想到了，补0也想到了，没想到用哈希，而是用循环去迭代，这样时间超时了。

def subarraySum(self, nums: List[int], k: int) -> int:
    total = ans = 0
    d = collections.defaultdict(int)
    d[0] = 1
    for x in nums:
        total += x
        ans += d[total-k]
        d[total] += 1
    return ans

1074. Number of Submatrices That Sum to Target

和为目标值的子矩阵个数。

1
2
3

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
Explanation: The four 1x1 submatrices that only contain 0.

方法一：560的升级版。需要先求出每行的前缀和。然后选定两个列（可以相同），以这两个列为宽度，高度逐渐递增，寻找这个宽度的子矩阵的和。

def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
    M, N = len(matrix), len(matrix[0])
    for i, row in enumerate(matrix):
        matrix[i][:] = accumulate(row)
    res = 0
    for i in range(N):
        for j in range(i, N):
            cur, d = 0, defaultdict(int)
            d[0] = 1
            for k in range(M):
                cur += matrix[k][j] - (matrix[k][i-1] if i>0 else 0)
                res += d[cur-target]
                d[cur] += 1
    return res

1311. Get Watched Videos by Your Friends

找到你的level级别的朋友看的电影，按照频率字母排序。原题

Input: watchedVideos = [["A","B"],["C"],["B","C"],["D"]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 1
Output: ["B","C"] 
Explanation: 
You have id = 0 (green color in the figure) and your friends are (yellow color in the figure):
Person with id = 1 -> watchedVideos = ["C"] 
Person with id = 2 -> watchedVideos = ["B","C"] 
The frequencies of watchedVideos by your friends are: 
B -> 1 
C -> 2

def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
    bfs, seen = {id}, {id}
    for _ in range(level):
        bfs = {j for i in bfs for j in friends[i] if j not in seen}
        seen |= bfs
    videos=collections.Counter([v for idx in bfs for v in watchedVideos[idx]])
    return sorted(videos, key=lambda x: (videos[x], x))

388. Longest Absolute File Path

最长的绝对路径。原题

方法一：自己用栈实现的。

def lengthLongestPath(self, input: str) -> int:
    stack = []
    path = input.split('\n')
    ans = ['']
    for p in path:
        t = p.count('\t')
        p = p[t:]
        while t < len(stack):
            stack.pop()
        stack.append(p)
        if '.' in p:
            ans.append('/'.join(stack))
    return len(max(ans, key=len))

方法二：用字典记录深度。

def lengthLongestPath(self, input: str) -> int:
    ans = 0
    path_len = {0: 0}
    for line in input.splitlines():
        name = line.lstrip('\t')
        depth = len(line) - len(name)
        if '.' in name:
            ans = max(ans, path_len[depth] + len(name))
        else:
            path_len[depth+1] = path_len[depth] + len(name) + 1
    return ans

1224. Maximum Equal Frequency

给定一个数组，返回这个数组最长的前缀，前缀中刚好有删除一个元素使其它元素的频率相等。原题

1
2
3

Input: nums = [2,2,1,1,5,3,3,5]
Output: 7
Explanation: For the subarray [2,2,1,1,5,3,3] of length 7, if we remove nums[4]=5, we will get [2,2,1,1,3,3], so that each number will appear exactly twice.

方法一：Lee215的答案，一共分为两种情况，一种情况是将当前元素删除，那么前面的元素具有相同的频率。如果不删除当前的元素，那么这个元素出现了c次，我们用freq来记录出现i次的有多少个数。那么删除的元素只能是出现c+1次或者1次，并且这个数只有一个。

def maxEqualFreq(self, A: List[int]) -> int:
    count = collections.defaultdict(int)
    freq = [0] * (len(A)+1)
    res = 0
    for n, a in enumerate(A, 1):
        freq[count[a]+1] += 1
        freq[count[a]] -= 1
        c = count[a] = count[a] + 1
        if freq[c]*c==n and n < len(A):
            res = n + 1
        d = n - freq[c]*c
        if d in (c+1, 1) and freq[d]==1:
            res = n
    return res

957. Prison Cells After N Days

有8个监狱，如果两边的监狱是相同的，那么次日这个监狱会有人，否则为空。求N天之后的监狱原题

Input: cells = [0,1,0,1,1,0,0,1], N = 7
Output: [0,0,1,1,0,0,0,0]
Explanation: 
The following table summarizes the state of the prison on each day:
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

方法一：看了提示用hash但是还是没想到，总共有8个监狱，首位肯定是0，那么还有6个，6个监狱一共有多少种情况呢，2**6，也就是说最多这些天形成一种循环。

def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]:
    seen = {str(cells): N}
    while N:
        seen[str(cells)] = N
        N -= 1
        cells = [0] + [cells[i - 1] ^ cells[i + 1] ^ 1 for i in range(1, 7)] + [0]
        if str(cells) in seen:
            N %= seen[str(cells)] - N
    return cells

方法二：Lee发现了规律，有三个情况一种是1，7，14的时候循环。那么，每14次进行一次循环。但是不能直接进行取余，因为当过了一天，才会进入14天循环中的一天，所以如果当N能被14整除时，并且首位不为0，那么实际上他需要进行变换，而不是直接返回。

def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]:
    N -= max(N - 1, 0) // 14 * 14
    for i in range(N):
        cells = [0] + [cells[i - 1] ^ cells[i + 1] ^ 1 for i in range(1, 7)] + [0]
    return cells

1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

和为目标值的子数组最多有多少个，子数组不能重复。原题

1
2
3

Input: nums = [1,1,1,1,1], target = 2
Output: 2
Explanation: There are 2 non-overlapping subarrays [1,1,1,1,1] with sum equals to target(2).

方法一：题目分类为dp。但我感觉更适合哈希，比赛的时候想到了一下TwoSum的思路，但是重置seen为空那步没想到。

def maxNonOverlapping(self, nums: List[int], target: int) -> int:
    acc = [0] + list(itertools.accumulate(nums))
    n = len(nums)
    ans = 0
    seen = set()
    for pre_sum in acc:
        if pre_sum - target in seen:
            ans += 1
            seen = set()
        seen.add(pre_sum)
    return ans

1577. Number of Ways Where Square of Number Is Equal to Product of Two Numbers

找到一个数组中两个元素乘积等于另一个数组的平方，求总共的个数。原题

Input: nums1 = [7,7,8,3], nums2 = [1,2,9,7]
Output: 2
Explanation: There are 2 valid triplets.
Type 1: (3,0,2).  nums1[3]^2 = nums2[0] * nums2[2].
Type 2: (3,0,1).  nums2[3]^2 = nums1[0] * nums1[1].

方法一：比赛时想复杂了，但还是做出来了。比赛时想的是Counter原数组，根据平方找值。实际上通过combine方法可以反过来算简单。

def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
    c1 = Counter(n**2 for n in nums1)
    c2 = Counter(n**2 for n in nums2)
    ans = 0
    for x, y in itertools.combinations(nums1, 2):
        ans += c2[x*y]
    for x, y in itertools.combinations(nums2, 2):
        ans += c1[x*y]
    return ans

916. Word Subsets

给两个单词列表，返回A中满足这样条件的单词：B中的所有单词都是此单词的子集。原题

1 2	Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["e","oo"] Output: ["facebook","google"]

方法一：Counter 比较简单。效率不咋高。

def wordSubsets(self, A: List[str], B: List[str]) -> List[str]:
    c_a = [Counter(w) for w in A]
    c_b = reduce(operator.or_, [Counter(w) for w in B])
    return [word for i, word in enumerate(A) if not c_b-c_a[i]]

方法二：一的基础上改进。& 比较貌似快一丢丢？

1
2
3

def wordSubsets(self, A: List[str], B: List[str]) -> List[str]:
    c_b = reduce(operator.or_, (Counter(w) for w in B))
    return [a for a in A if c_b & Counter(a) == c_b]

方法三：直接查字符会比较快。快了一倍左右

def wordSubsets(self, A: List[str], B: List[str]) -> List[str]:
    subset = {}
    for b in B:
        for char in b:
            subset[char] = max(subset.get(char, 0), b.count(char))
    return [a for a in A if all(a.count(c) >= subset[c] for c in subset.keys())]

974. Subarray Sums Divisible by K

连续的子数组的和能被K整除的个数。原题

Input: A = [4,5,0,-2,-3,1], K = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by K = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

方法一：这道题没有在规定时间内完成，此答案参考了排名第一的大佬，然后使用defaultdict进行了改进。

这里有一个详细的解答。不过那里给出的答案没有这个简单，不过思路大体相同。

假设通过sum(i, j)表示切片[i: j]的总和，如果sum(i, j)能被K整除，则说明sum(0, j) - sum(0, i)也能被K整除，即对sum(0, j) % K == sum(0, i) % K。下面的解法使用一个字典记录了余数的个数。当余数第二次出现的时候，开始计数，但0的时候除外，因为整除了就产生结果了。

然后再看累加的方法以下文第3行log为例，mod又为4，这时它和之前余数为4的的数组都可以产生一个结果即[4, 5, 0] - [4] = [5, 0] 和[4 , 5, 0] - [4, 5] = [0]所以要累加原来的和。

def subarraysDivByK(self, A, K):
    from collections import defaultdict
    m = defaultdict(int)
    m[0] = 1
    total, ans = 0, 0
    for i, num in enumerate(A):
        total += num
        sum_p = total % K
        ans += m[sum_p]
        m[sum_p] += 1
        print('sum subarray {} total is {},  mod is {},  ans is {},  {}'.format(
            A[:i+1], total, sum_p, ans, m
        ))
    return ans

sum subarray [4] total is 4,  mod is 4,  ans is 0,  defaultdict(<class 'int'>, {0: 1, 4: 1})
sum subarray [4, 5] total is 9,  mod is 4,  ans is 1,  defaultdict(<class 'int'>, {0: 1, 4: 2})
sum subarray [4, 5, 0] total is 9,  mod is 4,  ans is 3,  defaultdict(<class 'int'>, {0: 1, 4: 3})
sum subarray [4, 5, 0, -2] total is 7,  mod is 2,  ans is 3,  defaultdict(<class 'int'>, {0: 1, 4: 3, 2: 1})
sum subarray [4, 5, 0, -2, -3] total is 4,  mod is 4,  ans is 6,  defaultdict(<class 'int'>, {0: 1, 4: 4, 2: 1})
sum subarray [4, 5, 0, -2, -3, 1] total is 5,  mod is 0,  ans is 7,  defaultdict(<class 'int'>, {0: 2, 4: 4, 2: 1})

1590. Make Sum Divisible by P

删除最小的连续子数组，使得整个数组和能被P整除。

方法一：此题作为竞赛第三题，比二题简单，但是竞赛的时候没有做。首先可以用总和%p看余几，然后就是找到最小的子数组能让余数等于这个，就把这个删除，这一点很好想。剩下的和974一样。

def minSubarray(self, nums: List[int], p: int) -> int:
    m = sum(nums) % p
    dp = {0: -1}
    mod = 0
    ans = len(nums)
    for i, a in enumerate(nums):
        mod = (mod+a) % p
        dp[mod] = i
        want = (mod-m) % p
        if want in dp:
            ans = min(ans, i-dp[want])
    return ans if ans < len(nums) else -1

692. Top K Frequent Words

最高频的K个单词，相同频率，优先返回字符顺序优先。

Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
Output: ["i", "love"]
Explanation: "i" and "love" are the two most frequent words.
    Note that "i" comes before "love" due to a lower alphabetical order.

方法一：记录写法，nsmallest 也能接受key函数。

1
2
3

def topKFrequent(self, words: List[str], k: int) -> List[str]:  
    c = Counter(words)
    return [w for w in heapq.nsmallest(k, c.keys(), key=lambda x: (-c[x], x))]

1399. Count Largest Group

以数字和为分组，求最大组的个数。原题

Input: n = 13
Output: 4
Explanation: There are 9 groups in total, they are grouped according sum of its digits of numbers from 1 to 13:
[1,10], [2,11], [3,12], [4,13], [5], [6], [7], [8], [9]. There are 4 groups with largest size

方法一：Counter

def countLargestGroup(self, n: int) -> int:
    from collections import Counter
    c = Counter()
    for i in range(1, n+1):
        c[sum(int(d) for d in str(i))] += 1
    ans = 0
    largest_size = 0
    for s, cnt in c.most_common():
        if largest_size!=0 and cnt!=largest_size:
            return ans
        else:
            largest_size = cnt
            ans += 1
    return ans

方法二：标准库。statistics.multimode返回一个可迭代对象中出现次数最多的元素。

1
2
3

def countLargestGroup(self, n: int) -> int:
    import statistics
    return len(statistics.multimode(sum(map(int, str(d))) for d in range(1, n+1)))

1394. Find Lucky Integer in an Array

找到数组中数字和出现次数一致的最大的数。原题

1
2
3

Input: arr = [2,2,3,4]
Output: 2
Explanation: The only lucky number in the array is 2 because frequency[2] == 2.

def findLucky(self, arr: List[int]) -> int:
    from collections import Counter
    c = Counter(arr)
    for d, f in c.most_common():
        if d == f:
            return d
        return -1

1128. Number of Equivalent Domino Pairs

相等的多米诺骨牌对数。原题

方法一：把牌翻转成一样的，然后组合。

1
2
3

def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
    dominoes = collections.Counter(tuple(sorted(d)) for d in dominoes)
    return sum(v*(v-1)//2 for v in dominoes.values())

1002. Find Common Characters

在给定的单词列表中找到公共字符。原题

1 2	Input: ["bella","label","roller"] Output: ["e","l","l"]

1 2	def commonChars(self, A: List[str]) -> List[str]: return list(reduce(and_, map(Counter, A)).elements())

697. Degree of an Array

degree这里表示数组最常见的元素的频率，然后在连续的子数组中寻找同样的degree，求最小子数组的长度。原题

Input: [1, 2, 2, 3, 1]
Output: 2
Explanation: 
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest length is 2. So return 2.

方法一：使用Counter 和index. 600ms有点慢。

def findShortestSubArray(self, nums):
    from collections import Counter
    c = Counter(nums)
    degree = None
    res = n = len(nums)
    for num, count in c.most_common():
        if degree and count != degree:
            break
        min_len = n - nums[::-1].index(num) - 1 - nums.index(num) + 1
        # print(min_len, num)
        res = min(res, min_len)
        degree = count
    return res

方法二：使用dict记录索引。

def findShortestSubArray(self, nums):
    c = collections.defaultdict(int)
    left, right = {}, {}
    for i, num in enumerate(nums):
        if num not in left:
            left[num] = i
        right[num] = i
        c[num] += 1
    res = len(nums)
    degree = max(c.values())
    for num, count in c.items():
        if count == degree:
            res = min(res, right[num]-left[num]+1)
    return res

方法三：使用Counter + dict.

def findShortestSubArray(self, nums: 'List[int]') -> 'int':
    c = collections.Counter(nums)
    left, right = {}, {}
    for i, num in enumerate(nums):
        if num not in left:
            left[num] = i
        right[num] = i
    degree, res = 0, len(nums)
    for num, count in c.most_common():
        if degree and count != degree:
            break
        res = min(res, right[num]-left[num]+1)
        degree = count
    return res

187. Repeated DNA Sequences

找出出现两次以上的DNA连续序列，序列长度为10。

1 2	Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" Output: ["AAAAACCCCC","CCCCCAAAAA"]

方法一：此题简单方法用滑动窗口加counter就行了。

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        c = Counter(s[i:i+10] for i in range(len(s)-9))
        return [k for k, cnt in c.items() if cnt > 1]

方法二：此题有个位运算的标签，所以试了一下，将DNA序列编码为二进制的形式。

def findRepeatedDnaSequences(self, s: str) -> List[str]:
    d = dict(zip('ACGT', range(4)))
    dd = {v: k for k, v in d.items()}
    dna = reduce(lambda x, y: x<<2 | d[y], s[:10], 0)
    cnt = Counter([dna])

    for i, c in enumerate(islice(s, 10, None)):
        dna <<= 2
        dna &= (1<<20)-1    # 取出多余的高位
        dna |= d[c]
        cnt[dna] += 1

    def decode(n):
        s = ''
        for _ in range(10):
            s += dd[n % 4]
            n >>= 2
        return s[::-1]

    return [decode(n) for n, c in cnt.items() if c > 1]

1658. Minimum Operations to Reduce X to Zero

给定一个数组和一个目标数x，每次可以将x-数组两边的某个数，最少需要多少步可以将x变为0。

Input: nums = [1,1,4,2,3], x = 5
Output: 2
Explanation: The optimal solution is to remove the last two elements to reduce x to zero.
Input: nums = [3,2,20,1,1,3], x = 10
Output: 5
Explanation: The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.

方法一：变长滑动窗口。比赛时没有做出来，想成BFS了，结果超时。这题和1423很像，那题是定长的滑动窗口，此题可以转化为，找到一个最长的窗口使得窗口值的和等于总和-x。1200ms.

def minOperations(self, nums: List[int], x: int) -> int:
    target = sum(nums) - x
    lo, N = 0, len(nums)
    cur_sum, res = 0, -1
    for hi, num in enumerate(nums):
        cur_sum += num
        while lo+1<N and cur_sum>target:
            cur_sum -= nums[lo]
            lo += 1
        if cur_sum == target:
            res = max(res, hi-lo+1)
    return res if res<0 else N-res

方法二：前缀和+字典，这个写法比较优雅，但是比较难想。i表示从右边减去的数字，mp[x]表示从左边减去的数字。

def minOperations(self, nums: List[int], x: int) -> int:
    mp = {0: 0}
    prefix = 0
    for i, num in enumerate(nums, 1): 
        prefix += num
        mp[prefix] = i 
    
    ans = mp.get(x, inf)
    for i, num in enumerate(reversed(nums), 1): 
        x -= num
        if x in mp and mp[x] + i <= len(nums): 
            ans = min(ans, i + mp[x])
    return ans if ans < inf else -1

1711. Count Good Meals

给你一个整数数组 deliciousness ，其中 deliciousness[i] 是第 i 道餐品的美味程度，返回你可以用数组中的餐品做出的不同大餐的数量。结果需要对 109 + 7 取余。

Input: deliciousness = [1,3,5,7,9]
Output: 4
Explanation: The good meals are (1,3), (1,7), (3,5) and, (7,9).
Their respective sums are 4, 8, 8, and 16, all of which are powers of 2.

方法一：哈希。比赛时相出了两数之和的思想，但是想放到Counter中遍历，这样写非常麻烦，直接遍历原数组就好。1400ms

def countPairs(self, dis: List[int]) -> int:
    two_powers = {2**i for i in range(22)}
    res = 0
    s = Counter()
    for d in dis:
        for c in two_powers:
            if c - d in s:
                res += s[c - d]
        s[d] += 1
    return res % (10**9 + 7)

方法二：使用Counter遍历，1176ms。

def countPairs(self, dis: List[int]) -> int:
    two_powers = {2**i for i in range(22)}
    res = 0
    s = Counter()
    for d, cnt in Counter(dis).items():
        for c in two_powers:
            if c - d == d:
                res += comb(cnt, 2)
            else:
                res += s[c - d] * cnt
        s[d] = cnt
    return res % (10**9 + 7)

2122. Recover the Original Array

恢复原始的数组，给你一个合并后的数组，由原数组每个元素-k和+k形成两个数组后合并。

Input: nums = [2,10,6,4,8,12]
Output: [3,7,11]
Explanation:
If arr = [3,7,11] and k = 1, we get lower = [2,6,10] and higher = [4,8,12].
Combining lower and higher gives us [2,6,10,4,8,12], which is a permutation of nums.
Another valid possibility is that arr = [5,7,9] and k = 3. In that case, lower = [2,4,6] and higher = [8,10,12].

方法一：竞赛时险过，有两个地方想复杂了，其实没必要用堆，本来复制数组就用了O(N)的复杂度。思路是先找2k，然后判断这个是否可行。找的过程也是需要O(N)。

def recoverArray(self, nums: List[int]) -> List[int]:

    def check(d):
        c, res = Counter(nums), []
        for num in nums:
            if c[num] == 0:
                continue
            elif c[num+d] == 0:
                return False, []
            c[num] -= 1
            c[num+d] -= 1
            res.append(num+d//2)
        return True, res

    N = len(nums)
    nums.sort()
    for i in range(1, N):
        k = nums[i]-nums[0]  # 对比最小元素
        if k!=0 and k&1==0:
            valid, res = check(k)
            if valid: return res

2488. Count Subarrays With Median K

统计子数组中位数为k的个数。

给你一个长度为 n 的数组 nums ，该数组由从 1 到 n 的不同整数组成。另给你一个正整数 k 。

统计并返回 num 中的 中位数 等于 k 的非空子数组的数目

1
2
3

输入：nums = [3,2,1,4,5], k = 4
输出：3
解释：中位数等于 4 的子数组有：[4]、[4,5] 和 [1,4,5] 。

方法一：比赛时没有时间做，瞄了一眼以为用堆，结果不是。首先很重要得一个条件是，所有的数不同，那么能使中位数为K，一定会包含k，所以可以围绕k向两侧拓展。

对于一个合理的子数组，一定保证小于k的和大于k的相等（奇数），小于k的+1等于大于k的（偶数）。

用 l1, s1 表示k左侧比k大，比k小的个数。l2,s2表示k右侧比k大，比k小的个数。

得出l1+l2=s1+s2或者l1+l2=s1+s2+1，推论出l1-s1=s2-l2和l1-s1=s2-l2+1。这样可以维护一个map来计数。注意，需要考虑没有左或者右的情况。

def countSubarrays(self, nums: List[int], k: int) -> int:
    index = nums.index(k)

    cnt = defaultdict(int)
    res = l1 = s1 = 0
    for i in reversed(range(index)):  #注意这里要倒序
        if nums[i] < k:
            s1 += 1
        else:
            l1 += 1
        cnt[l1-s1] += 1
        if l1==s1 or l1==s1+1:
            res += 1
    l2 = s2 = 0
    for i in range(index+1, len(nums)):
        if nums[i] < k:
            s2 += 1
        else:
            l2 += 1
        res += cnt[s2-l2] + cnt[s2-l2+1]
        if l2==s2 or l2==s2+1:
            res += 1
    return res + 1