哈希表系列
azl397985856 opened this issue · 1 comments
azl397985856 commented
- 一个不行就两个
[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
- 同余定理
[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
- 计数 + 计频率
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
- 二维平面
- 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]
- 其他题目推荐
- 720
- 953
- 面试题 01.04. 回文排列
- 500. 键盘行
- 36. 有效的数独
- 37. 解数独 与 36 类似,还需要点回溯的**
- 【每日一题】- 2020-04-27 - 多人运动
- 811.子域名访问计数
stale commented
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.