Leetcode 【287、1035】

题目描述：【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]