LeetCode笔记：Weekly Contest 223 比赛记录
LeetCode笔记：Weekly Contest 223 比赛记录
codename_cys
发布于 2021-03-27 22:31:02
发布于 2021-03-27 22:31:02
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这道题其实就是考了一下异或的特征，无非就是a^a == 0，所以我们不断地求异或就能够反推出原先的全部元素。
2. 代码实现
给出python代码实现如下：
class Solution:
def decode(self, encoded: List[int], first: int) -> List[int]:
n = len(encoded)
res = [first for _ in range(n+1)]
for i in range(n):
res[i+1] = first ^ encoded[i]
first = res[i+1]
return res整体的算法复杂度为O(N)，提交代码评测得到：耗时64ms，占用内存16MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题的思路就更加简单了，把链表中的两个节点进行定位之后然后交换一下他们的值就行了。
2. 代码实现
给出python代码实现如下：
class Solution:
def swapNodes(self, head: ListNode, k: int) -> ListNode:
def count_len(head):
l = 0
while head:
l += 1
head = head.next
return l
n = count_len(head)
i, j = k, n-k+1
if i == j:
return head
p = head
for k in range(1, n+1):
if k == i:
nodei = p
if k == j:
nodej = p
if k > max(i, j):
break
p = p.next
nodei.val, nodej.val = nodej.val, nodei.val
return head可以看到，整体的算法复杂度同样为O(N)，提交代码评测得到：耗时1144ms，占用内存48.9MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题的考察点应该是有两部分，分别为：
- 当一些元素是相互连接的情况时，我们总能够通过有限次操作将他们的顺序任意重排；
- 如何快速得到元素间的相互连接关系。
其中，前者可以通过数学归纳法进行证明，后者则可以通过DSU结构进行实现。
有关DSU相关的内容可以参考我之前的博客：Python笔记：并查集（DSU）结构简介。
2. 代码实现
给出python代码实现如下：
class DSU:
def __init__(self, n):
self.dsu = [i for i in range(n)]
def find(self, x):
if x != self.dsu[x]:
self.dsu[x] = self.find(self.dsu[x])
return self.dsu[x]
def union(self, x, y):
x = self.find(x)
y = self.find(y)
if x != y:
self.dsu[x] = y
return
class Solution:
def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:
n = len(source)
dsu = DSU(n)
for x, y in allowedSwaps:
dsu.union(x, y)
groups = defaultdict(list)
for i in range(n):
groups[dsu.find(i)].append(i)
res = 0
for group in groups.values():
counter = defaultdict(int)
for idx in group:
counter[source[idx]] += 1
counter[target[idx]] -= 1
res += sum(x for x in counter.values() if x > 0)
return res提交代码评测得到：耗时476ms，占用内存49.5MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题最直接的思路就是采用迭代算法，然后我们可以使用缓存的方式构建一个伪动态规划算法来优化实行效率。
我们给出迭代的思路如下：
- 每一次操作，都找到当前的第一个元素，将其和后面的某一个元素进行合并，然后迭代进行下一次操作；
- 如果某一次操作之后元素总数目刚好为工人数目，则返回当前堆中的最大值作为这一策略下的结果，然后求取最小值即可。
2. 代码实现
我们给出python代码实现如下：
class Solution:
def minimumTimeRequired(self, jobs: List[int], k: int) -> int:
n = len(jobs)
if k == n:
return max(jobs)
elif k == 1:
return sum(jobs)
jobs = sorted(jobs)
if k == n-1:
return max(jobs[-1], jobs[0] + jobs[1])
@lru_cache(None)
def dp(work):
if len(work) == k:
return max(work)
m = len(work)
res = math.inf
work = list(work)
for i in range(1, m):
work[i] += work[0]
res = min(dp(tuple(work[1:])), res)
work[i] -= work[0]
return res
return dp(tuple(jobs))评测得到结果如下：耗时2060ms，占用内存83.5MB。属于当前最优解法。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-01-11 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录