总结
这里是式酱(∠・ω< )⌒☆
大家新年快乐呀！今天运气好趁着没人参赛上了一波分，T2比较坑，T4则是结论题，需要猜一下结论。
6300. 最小公共值
普遍做法:用集合直接暴力搜即可。因为题目保证非递减，也可以用常规做法双指针解决。
class Solution:
def getCommon(self, nums1: List[int], nums2: List[int]) -> int:
s2 = set(nums2)
for i in nums1:
if i in s2:
return i
return -16275. 使数组中所有元素相等的最小操作数 II
粗心WA了一发，漏了k == 0的情况要单独抓出来讨论。
一步一步思考：
首先加减的过程中总和是不变的，要保证sum(nums1) == sum(nums2)，才有可能完成转换。
其次对于每个nums1的值一次只能加k或者减k，如果nums1[i] - nums2[i]不能整除k，那么也不可能完成转换。
因为正负相抵消，统计每个nums1[i] - nums2[i]中正数部分整除k的总和即可
class Solution:
def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:
n = len(nums1)
# 挺坑的，k == 0的情况只有0和-1这两种答案 特判一下
if k == 0:
for i in range(n):
if nums1[i] != nums2[i]:
return -1
return 0
# 加减的过程中总和不变，如果总和不一样，肯定无法转换
if sum(nums1) != sum(nums2):
return -1
res = 0
for i in range(n):
sub = nums1[i] - nums2[i]
# 差值无法除尽k 无法完成转换操作
if sub % k != 0:
return -1
# 因为sub的总和为0，对称的，我们计算次数只计算大于0的部分即可
if sub > 0:
res += sub // k
return res6302. 最大子序列的分数
套路题：贪心+堆
思考流程如下：
1.因为题目求的是子序列，所以与前后顺序无关，保证可以进行排序，不过排序过程中坐标需要一一对应。
2.因为题目涉及两个操作，一个是求子序列和，另一个是求子序列最小值，思考能不能固定其中一个呢？以固定最小值为例。
示例 nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
对nums2进行逆序排序，得到 nums1 = [2,3,1,3], nums2 = [4,3,2,1],对于每个nums2中的值，其左边的数都大于等于当前这个数值，所以最小值直接取当前这个数值即可，其前面的数对可以任意取，而对于nums1就是转化为一道求长度为k的子序列的最大值的题目，用堆实现即可。
class Solution:
def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
import heapq
a = sorted(zip(nums1,nums2),key = lambda x:-x[1])
q = []
total = 0
res = 0
for x,y in a:
# 若要选y为最小值，这个和必须包含当前的x，先出堆
if len(q) == k:
total -= heapq.heappop(q)
total += x
heapq.heappush(q,x)
if len(q) == k:
res = max(res, y * total)
return res一样套路的题目
1383. 最大的团队表现值
857. 雇佣 K 名工人的最低成本
6301. 判断一个点是否可以到达
看到前两个操作直接想到gcd，可以将[x,y]转化为[gcd(x,y),gcd(x,y)],而后面两个操作则可以把2幂的gcd转化为1，结合一下得出结论。
class Solution:
def isReachable(self, targetX: int, targetY: int) -> bool:
return gcd(targetX,targetY) in [1 << x for x in range(32)]写在最后
评论 (23)
