哈希表系列

[azl397985856]

1. 一个不行就两个

[1090] 受标签影响的最大值

class Solution:
    def largestValsFromLabels(self, values: List[int], labels: List[int], num_wanted: int, use_limit: int) -> int:
        zipped = sorted(zip(values, labels), reverse=True)
        used_label = collections.defaultdict(int)
        ans = 0
        total_picked = 0
        for value, label in zipped:
            if total_picked == num_wanted:
                return ans
            if used_label[label] < use_limit:
                used_label[label] += 1
                total_picked += 1
                ans += value
        return ans

[1577] 数的平方等于两数乘积的方法数

class Solution:
    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
        products1 = collections.defaultdict(int)
        products2 = collections.defaultdict(int)
        ans = 0
        for i in range(len(nums1)):
            for j in range(i + 1, len(nums1)):
                products1[nums1[i] * nums1[j]] += 1
        for i in range(len(nums2)):
            for j in range(i + 1, len(nums2)):
                products2[nums2[i] * nums2[j]] += 1
        for a in nums1:
            if a ** 2 in products2:
                ans += products2[a ** 2]
        for a in nums2:
            if a ** 2 in products1:
                ans += products1[a ** 2]

        return ans

2. 同余定理

[1590] 使数组和能被 P 整除

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        total = sum(nums)
        remainder = total % p
        if remainder == 0:
            return 0
        ans = len(nums)
        pre = [0]
        remainders = {0: -1}
        for i, a in enumerate(nums):
            pre.append(pre[-1] + a)
            pre_remainder = pre[-1] % p
            r = (pre_remainder - remainder) % p
            if r in remainders:
                ans = min(ans, i - remainders[r])
            remainders[pre_remainder] = i
        return ans if ans < len(nums) else -1

3. 计数 + 计频率

		counts, freq = collections.Counter(), collections.Counter()
        for i, num in enumerate(nums):
            counts[num] += 1
            if counts[num] != 1:
                freq[counts[num] - 1] -= 1
            freq[counts[num]] += 1

[1224] 最大相等频率

class Solution:
    def maxEqualFreq(self, nums):
        counts, freq = collections.Counter(), collections.Counter()
        ans = 0
        for i, num in enumerate(nums):
            counts[num] += 1
            freq[counts[num]] += 1
            if counts[num] > 1:
                freq[counts[num] - 1] -= 1
                if freq[counts[num] - 1] == 0:
                    freq.pop(counts[num] - 1)
            if len(freq) == 1:
                h, w = list(freq.items())[0]
                if h == 1 or w == 1:
                    ans = i + 1
            elif len(freq) == 2:
                (h1, w1), (h2, w2) = list(freq.items())[0], list(freq.items())[1]
                if h1 > h2:
                    h1, h2 = h2, h1
                    w1, w2 = w2, w1
                if w1 == 1 and h1 == 1 or (h2 == h1 + 1 and w2 == 1):
                    ans = i + 1
        return ans

4. 二维平面

• 939.最小面积矩形
• 面试题 16.14. 最佳直线

# y1 = kx1 + b 
# y2 = kx2 + b
# (y1 + y2  - k(x1 + x2)) / 2
class Solution:
    def bestLine(self, points: List[List[int]]) -> List[int]:
        n = len(points)
        dic = collections.defaultdict(set)
        for i in range(n):
            for j in range(i + 1, n):
                dy = points[j][1] - points[i][1]
                dx = points[j][0] - points[i][0]
                if dx == 0:
                    k = 'oo'
                    b = points[j][1]
                else:
                    # 此处 k = str(dy) + '/' + str(dx) 会有问题， 除非你自己手动化简。 生产环境建议采用这种方式，注意化简即可
                    k = dy/dx
                    b = points[j][1] + points[i][1] - (dy / dx) * (points[j][0] + points[i][0])
                dic[(k, b)].add(i)
                dic[(k, b)].add(j)
        return sorted(list(sorted(dic.values(), key=lambda a:-len(a))[0]))[:2]

                

5. 其他题目推荐

• 720
• 953
• 面试题 01.04. 回文排列
• 500. 键盘行
• 36. 有效的数独
• 37. 解数独 与 36 类似，还需要点回溯的思想
• 【每日一题】- 2020-04-27 - 多人运动
• 811.子域名访问计数

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.