Closed
Description
- 一个不行就两个
[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.子域名访问计数