LeetCode笔记：Biweekly Contest 50 比赛记录
LeetCode笔记：Biweekly Contest 50 比赛记录
0. 赛后总结
久违地打了一次双周赛，然后就被虐成了渣渣……
好吧，其实排名也还好，主要前三题比较简单，花了12分钟多点就搞定了，但是最后一题太难了，有点思路，但是到最后都没能真正搞出来，然后就很伤……
不过所幸似乎最后一题太难了以至于做出的人实在是不怎么多，所以整体排名就没怎么受到影响，算是比较lucky吧……
算了，排名都是虚的，好好锻炼代码能力才是实的……
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题的解题思路还是非常直接的，由于只能做加法操作，因此每个数的可取范围就被限制了，那么每一个数可取的范围就是其本身和上一个值加一两个数之间的最大值。
因此，我们就可以快速地算出每一个数所需要经过的操作数。
2. 代码实现
给出python代码实现如下：
class Solution:
def minOperations(self, nums: List[int]) -> int:
pre = 0
res = 0
for n in nums:
if n <= pre:
res += pre+1-n
pre += 1
else:
pre = n
return res提交代码评测得到：耗时120ms，占用内存15.1MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题由于限制了点的数目和query的数目都不会超过500，因此，二层循环的时间复杂度还是能够在允许范围内的。
故，我们可以直接采用暴力地二重循环的方式直接对问题进行求解。
2. 代码实现
给出python代码实线如下：
class Solution:
def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:
def in_circle(p, q):
x1, y1 = p
x2, y2, r = q
return r**2 >= (x2-x1)**2 + (y2-y1)**2
res = []
for q in queries:
cnt = 0
for p in points:
if in_circle(p, q):
cnt += 1
res.append(cnt)
return res提交代码评测得到：耗时2776ms，占用内存14.5MB。
意外的有点耗时间，不过whatever了，如果有读者有更好的解题思路欢迎在下方评论区指点一二。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
考察要处理后结果中第i个回答，其结果可以用下述公式进行表达：
res[i] = nums[0] ^ …… ^ nums[n-1-i] ^ k
因此，我们只需要事先求解好所有nums[0] ^ …… ^ nums[i]的值，就可以在 O ( N ) O(N) O(N)的算法复杂度内直接获得k的异或对象。
然后问题就划归为对于一个已知的数a，如果给出另一个数b使得a^b最大，其中 b < 2 k b < 2^k b<2k，显然他们可以获得的最大的数为:
((a >> k) << k) | 0b11...1
那么，我们很直观地就能够看出，b的取值应对为a的末k位数字进行位反操作后得到的结果。
由此，我们即刻对其编程进行实现，其对应的算法复杂度为 O ( N ) O(N) O(N)。
2. 代码实现
给出python代码实现如下：
class Solution:
def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:
arr = deepcopy(nums)
n = len(nums)
for i in range(1, n):
arr[i] = arr[i-1] ^ arr[i]
def fn(x, k):
return (x ^ (k-1)) % k
res = [fn(x, 2**maximumBit) for x in arr]
return res[::-1]提交代码评测得到：耗时1908ms，占用内存32.6MB。
当前最优的算法实现耗时948ms，但是看了一下算法思路是一致的，也是挺奇怪的，这里就不多做展开了，有兴趣的读者可以自行研究一下。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
好吧，折腾了一周之后我放弃了，实在没想出来好的解决方法，我个人的思路是使用迭代的方法进行求解，不过迭代公式里面存在一定的问题，导致结果有误。
然后看了一下leetcode官网上给出的解答，瞬间就给跪了……
官方解答利用了费马小定理然后还有乘法逆元，简直了，一度想起高中被数学竞赛中数论支配的恐惧……
唉，回头再说吧，这里就先不做解答了，仅仅给出官方的解法链接如下，如果有读者感兴趣的话可以自行去看一下：