[LeetCode周赛复盘] 第 96 场双周赛20230121

• • 一、本周周赛总结
  • 二、 [Easy] 6300. 最小公共值
  • • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 三、[Medium] 6275. 使数组中所有元素相等的最小操作数 II
  • • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 四、[Medium] 6302. 最大子序列的分数
  • • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 五、[Hard] 6301. 判断一个点是否可以到达
  • • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 六、参考链接

一、本周周赛总结

• 没想到我能在除夕写算法。
• T1 哈希集合模拟。
• T2 计数。
• T3 贪心，排序+堆。
• T4 脑筋急转弯猜结论。
  

二、 [Easy] 6300. 最小公共值

链接: 6300. 最小公共值

1. 题目描述

2. 思路分析

• 看了下数据范围，决定无视‘已有序’这个条件，直接set求交集。反正复杂度不变。
• 双指针可以利用有序。

3. 代码实现

class Solution:def getCommon(self, nums1: List[int], nums2: List[int]) -> int:ans = set(nums1)&set(nums2)        return min(ans,default=-1)

三、[Medium] 6275. 使数组中所有元素相等的最小操作数 II

链接: 6275. 使数组中所有元素相等的最小操作数 II

1. 题目描述

2. 思路分析

这题由于k可以是0，前排wa声一片。

• 我也wa了，可以说是和前排大佬最近的一次。
• 注意，i,j都是操作nums1，因此每次操作nums1的数值总和不变。
• 同时,每个数位置不变，每次变k，因此nums2[i]-nums1[i]必须是k的倍数。
• 那么我们只需要统计增加的次数和减少的次数是否相同即可。

3. 代码实现

class Solution:def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:if k == 0:return 0 if nums1 == nums2 else -1            n = len(nums1)ans = 0a = b = 0for x,y in zip(nums1,nums2):d = y - x if d%k != 0:return -1if d < 0:a += -d//kif d > 0:b += d//kif a != b:return -1return a

四、[Medium] 6302. 最大子序列的分数

链接: 6302. 最大子序列的分数

1. 题目描述

2. 思路分析

• 贪心。
• 题目要求最大，且全是正数。首先考虑让a1,a2中参与运算的数都尽可能的大。
• 发现a2是取的子序列中的最小值，那么显然最大的k-1个值是取不到了。
• 那我们就考虑一下取第k大的，这时显然下标是取a2最大的k个数，这时的答案是可以计算的。
• 再考虑a2还能取哪些值，发现可以向更小的递推，而同时维护最大的k个a1即可。
• 那么按照a2降序排序，然后最小堆维护a1的最大k个数，同时维护堆的和。

3. 代码实现

class Solution:def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:     z = sorted(zip(nums1,nums2),key=lambda x:x[1],reverse=True)h = [x for x,y in z[:k]]heapify(h)s = sum(h)ans = s * z[k-1][1]for x,y in z[k:]:s += xs -= heappushpop(h,x)ans = max(ans,s*y)return ans

五、[Hard] 6301. 判断一个点是否可以到达

链接: 6301. 判断一个点是否可以到达

1. 题目描述

2. 思路分析

• 猜结论，最大公约数是2的幂。

3. 代码实现

class Solution:def isReachable(self, x: int, y: int) -> bool:return gcd(x,y).bit_count() == 1   

六、参考链接