LeetCode笔记：Weekly Contest 235 比赛记录
LeetCode笔记：Weekly Contest 235 比赛记录
- LeetCode笔记：Weekly Contest 235
- 0. 赛后总结
- 1. 题目一
- 1. 解题思路
- 2. 代码实现
- 2. 题目二
- 1. 解题思路
- 2. 代码实现
- 3. 题目三
- 1. 解题思路
- 2. 代码实现
- 4. 题目四
- 1. 解题思路
- 2. 代码实现
0. 赛后总结
果然还是翘掉了周日的比赛，虽然其实当时酒已经醒的差不多了，至少头不晕了，但是怎么说的，还是懒，就赖过去了……
慢慢补做比赛吧……
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题依然没啥好多说的，只要将句子分词之后然后保留前k个词，然后恢复成句子就行了……
2. 代码实现
给出python代码实现如下：
class Solution:
def truncateSentence(self, s: str, k: int) -> str:
s = s.split()[:k]
return " ".join(s)提交代码评测得到：耗时24ms，占用内存14.1MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题难度感觉还是在读题目上，把题目看懂了，基本题目也就搞定了。
说白了就是根据log先对每一个用户id统计他们所有操作发生的时间，然后记录下他们的uam次数，然后在用一个list记录下来即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def findingUsersActiveMinutes(self, logs: List[List[int]], k: int) -> List[int]:
uam = defaultdict(set)
for u, t in logs:
uam[u].add(t)
uam = {u: len(v) for u, v in uam.items()}
res = [0 for _ in range(k)]
for cnt in uam.values():
res[cnt-1] += 1
return res提交代码评测得到：耗时1016ms，占用内存24.4MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题的思路也挺直接的，就是想办法进行替换就是了，不过比较坑爹的是只能从原数组中的数字内寻求替换，因此就搜索范围只能在原数组中找寻和目标数字（nums2中的对应数字）最为接近的数。
如果直接搜索的话显然容易超时，因此，我们采用二分搜索的方式进行搜索，整体的时间复杂度就在O(NlogN)范围。
当然，这里我并没有做剪枝，如果先根据绝对值之差做一个排序，然后再进行一定的剪枝的话应该可以进一步优化执行效率，有兴趣的读者可以后续自行尝试一下。
2. 代码实现
给出python代码实现如下：
class Solution:
def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:
MOD = 10**9+7
s = sum(abs(x-y) for x, y in zip(nums1, nums2))
arr = sorted(nums1)
n = len(nums1)
res = s
for x, y in zip(nums1, nums2):
idx = bisect.bisect_left(arr, y)
if idx < n:
res = min(res, s-abs(x-y)+abs(arr[idx]-y))
if idx - 1 >= 0:
res = min(res, s-abs(x-y)+abs(arr[idx-1]-y))
return res % MOD提交代码评测得到：耗时1572ms，占用内存32.2MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题坦率地说就是没啥思路，后来是看了答案之后搞明白的，然后感觉真的是三观尽毁……
因为怎么想都觉得他的解法的算法复杂度高的离谱好不好……
他的思路异常简单，就是由于每一个数都不会大于 2×105，那么我就考察其中的每一个数 k，如果这个数的倍数中存在多个数在给定的数组当中，那么他们的最大公因数必然是 k的倍数，然后我们考察所有这样的数，如果到了某一次他们的最大公因数退化到了 k，那么就存在某一个子数组使其的最大公因数为 k，答案即可加一。遍历 2×105中的所有数，即可得到我们的答案。
怎么想都觉得这玩意的时间复杂度简直爆炸，但是没想到居然能过，没天理啊……
2. 代码实现
给出python代码实现如下：
class Solution:
def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:
_max = 2*10**5
nums = set(nums)
res = 0
for i in range(1, _max+1):
g = 0
for j in range(i, _max+1, i):
if j in nums:
g = math.gcd(g, j)
if g == i:
res += 1
break
return res提交代码评测得到：耗时4500ms，占用内存35MB。
当前最优的代码实现耗时3176ms，但是看了一下思路是基本一致的，三观尽毁……