题目描述：【Two Pointers】287. Find the Duplicate Number
解题思路：
这道题由于 Note 中有很多限制，想到的一些方法（如排序后再找、开辟 O(n) 空间计数、双循环）都不满足题意。由于只有一个数字出现了 2 次或 2 次以上，因此想到可不可以像 Leetcode 142. Linked List Cycle II 那样，使用快慢指针的方法去解决（因为只有一个重复数字出现，因此可以理解成有环）？
答案为 Yes。
我们已经知道，判断一个链表是否有环可以像 Leetcode 【Two Pointers】141. Linked List Cycle 那样，使用快慢指针。慢指针一次走一步，快指针一次走两步，两指针相遇就证明有环。
但是在 142 中，我们要确定环的入口在哪里，怎么做呢？还是先像 141 那样，找到第一次快慢指针相遇的地方。然后，将慢指针重新指向头结点，快指针依然指向相遇的那个节点。两个指针以每次一步的速度来遍历，直到他们再次相遇。此时，他们相遇的节点即是链表环的入口（这个问题的证明留到我做 142 题时再写）。
那么回到 287 这道题。我们只需要构造出类似于 142 题的“链表”，然后使用上述方法就可以找到重复的那个数字（即环的入口）。
题目大致意思是有 n+1 空间的整形数组，里面存的是 1∼n，而且这个数组里面有且仅存在一种重复的数字（重复但不限于重复一次），这里因为题目的特殊性，我们可以拿数组的索引号和数组里面存放的数字做文章。 因为数组中的数字是不大于 n 的，所以也就意味着不大于索引号（0∼n），所以在每次读取一个数组中的数字内容时，我们可以将这个数字作为新的索引，相当于现在我们可以构造出一个有向循环图，包含n+1 个节点和 n+1 条边，所以必定有环。
举个例子，nums = [3,1,3,4,2]，下标从 0 开始。首先第一个数字 3 指向下标 3 的数字 4，数字 4 指向下标 4 的数字 2，数字 2 指向下标 2 的数字 3，数字 1 指向下标 1 的数字 1。那么就会得到如下的有向循环图：
从这里看出来 3，4，2形成了一个环，而环的入口点是 3，这个问题就转换成了 Leetcode 142 的问题了。
当然这里还有一个问题，看上图中，1 是单独出来的，那么当我们初始化的时候，如果刚好碰到像 1 这种单独成环的怎么办？其实我们从数组第 1 个点进去即可，即下标为 0 的数字。因为题目说了数组中数字的范围是 1-n 的，所以 0 点处的值是不可能单独成环的，放心的从第一个数字开始找环即可。
Python3 实现：
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
slow = nums[nums[0]] # 慢指针走一步
fast = nums[nums[nums[0]]] # 快指针走两步
while slow != fast: # 找到第一次相遇的地方
slow = nums[slow]
fast = nums[nums[fast]]
slow = nums[0] # 慢指针指向链表入口
while slow != fast: # 快慢指针走都走一步，就能在环的入口处相遇
slow = nums[slow]
fast = nums[fast]
return slow
print(Solution().findDuplicate([2,3,1,5,3,6,4]) # 3 （画的链表为 2->1->3->5->6->4>3）
题目描述：【DP】1035. Uncrossed Lines
解题思路：
刚开始想了一下，发现应该用动态规划求解。在构造矩阵、填写最优子结构的结果的过程中，发现怎么和最长公共子序列的转移方程一模一样。再去理解一下题目，好吧，就是求最长公共子序列。代码 AC，结束。
最长公共子序列的参考博客：常考的经典算法--最长公共子序列（LCS）与最长公共子串(DP)。
Python3 实现：
class Solution:
def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
dp = [[0] * (len(B)+1) for _ in range(len(A)+1)]
for i in range(1, len(A)+1):
for j in range(1, len(B)+1):
if A[i-1] == B[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[-1][-1]
