[英雄星球七月集训LeetCode解题日报] 第7日 哈希表

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
class Solution:
    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:
        h = set()
        g = set()
        if x == 1:
            h.add(1)
        else:
            for i in range(bound+1):
                if x**i > bound:
                    break            
                h.add(x**i)
        if y == 1:
            g.add(1)
        else:
            for i in range(bound+1):
                if y**i > bound:
                    break            
                g.add(y**i)
        
        ans = set()
        for i,j in product(h,g):
            if i +j <= bound:
                ans.add(i+j)
        return list(ans)

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def hasGroupsSizeX(self, deck: List[int]) -> bool:
        cnt = Counter(deck)
        vs = sorted(list(cnt.values()))
        g = vs[0]
        for i in range(1,len(vs)):
            g = gcd(g,vs[i])
            if g == 1:
                return False
        return g>1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        m = [0] * k 
        for a in arr:
            m[a%k] += 1
        if m[0] & 1:
            return False
        for i in range(1,k):
            if k - i  == i:
                if m[i] & 1:
                    return False 
            else:
                if m[i] != m[k-i]:
                    return False
        return True

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def findLongestSubarray(self, array: List[str]) -> List[str]:   
        if len(array) <= 1:
            return []     
        t =  [1 if a.isdigit() else -1 for a in array]  # 预处理t,题目转化为求t中和为0的最长子段。
        # print(t)
        presum = list(accumulate(t))
        # print(presum)
        d = {0:-1}
        k = 0
        ans = 0
        for i,s in enumerate(presum):
            if s in d:
                pre = d[s]
                if i - pre > k:
                    k = i - pre 
                    ans = pre 
            else:
                d[s] = i 
        # print(ans,k)
        return array[ans+1:ans+1+k] if k else []