最近由于某些原因，又把做题、写博客的习惯捡起来。这一周主要做了LeetCode的每日一题和周赛，比较有意思的是预测赢家和保证图可完全遍历。
1.预测赢家
题目描述：对于分值数组scores，其中各分值均为正数。A、B两人游戏，依次从数组的首尾取值，直至取空，最终获得分值高者获胜。那么给定scores，判断率先开始的A是否可以获得游戏胜利。
思路：看到题目，第一反应A应当是占一些优势的。分析可知:
当分值数组长度为偶数时，双方各拿一半，A总有机会拿到分值更高的那一半，即数组长度为偶数时，A必胜；
而数组长度为奇数时则不然，考虑[1, 100, 2]，A将不得不将分值最高的100留给B，而这也说明了上述结论的正确性，因为A可以将此情况丢给B。此情况下需要更深入的分析，一种想法是利用dfs，探索所有可能的情况，而此种做法的时间复杂度将是2^n，显然是不行的；求最优解时可以利用动态规划，令dp[i][j]表示在scores[i:j+1]之间取值时两人的最大分差。可以找到状态转移公式：dp[i][j] = max(nums[i]-dp[i+1][j], nums[j]-dp[i][j-1])。动态规划的时间复杂度为n^2。
代码:
class Solution:
def PredictTheWinner(self, nums: List[int]) -> bool:
# 若为偶数，则1必胜
if len(nums) % 2 == 0:
return True
l = len(nums)
dp = [[0] * l for _ in range(l)]
for i in range(l):
dp[i][i] = nums[i]
for i in range(l-1, -1, -1):
for j in range(i+1, l):
dp[i][j] = max(nums[i]-dp[i+1][j], nums[j]-dp[i][j-1])
return dp[0][l-1] >= 0
2.保证图可完全遍历
这题整的挺复杂，其实就是由图的最小生成树拓展。算法的核心在于判断两个顶点是否连通，常用的做法是利用并查集来做。
代码：
# root[i]表示顶点 i 的根，初始化为自身
root = list(range(n+1))
# 寻找顶点i的根，并在过程中更新
def find(i):
if i != root[i]:
root[i] = find(root[i])
return root[i]
# 判断某条边是否需要
def union(x, y):
x, y = find(x), find(y)
return x != y