Floyd 判圈算法
2017-12-01
判断一个单链表中是否存在环，并找出环的入口： https://leetcode.com/problems/linked-list-cycle-ii/ Given a linked list, return the node where the cycle begins. If there is no cycle, return null. Note: Do not modify the linked list. Follow up: Can you solve it without using extra space? 不知道 LeetCode 难度评级的标准是什么，有的 hard 题看完题目就有思路，像这种 medium 题我琢磨半天也想不出空间复杂度为 $O(1)$ 的解法。后来了解到这一题已经有著名的解法了，即 Floyd 判圈算法，没错，就是求最短路径的弗洛伊德算法的那个 Floyd。 …
Single Number II
2017-11-27
LeetCode 的一道题，在一个 int 数组中，其余数值均出现了 3 次，只有一个数值出现了 1 次，求这个数： https://leetcode.com/problems/single-number-ii/description/ Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? 要求时间复杂度为 $O(n)$，并挑战读者是否能在空间复杂度 $O(1)$ 的条件下解决。 …
Gas Station
2017-10-14
加油站问题，LeetCode 链接： https://leetcode.com/problems/gas-station/description/ There are N gas stations along a circular route, where the amount of gas at station i is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations. Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1. Note: The solution is guaranteed to be unique. 这道题难度为 Medium，但如果对每个加油站进行模拟，则时间复杂度为 $O(n^2)$，OJ 判定超时，而 $O(n)$ 的方法并不容易。 Discuss 区有人给出了 $O(n)$ 的方法： https://leetcode.com/problems/gas-station/discuss/42568/Share-some-of-my-ideas. 但其中用到的结论并没有证明，而且描述不清晰。下面我会说明这两个结论的正确性。 …
求两个有序数组的中位数 Median of Two Sorted Arrays
2017-07-24
这是 LeetCode 上的一道题，求两个有序数组的中位数： https://leetcode.com/problems/median-of-two-sorted-arrays/description/ Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. Follow up: The overall run time complexity should be O(log (m+n)). Example 1: Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2. Example 2: Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5. Example 3: Input: nums1 = [0,0], nums2 = [0,0] Output: 0.00000 Example 4: Input: nums1 = [], nums2 = [1] Output: 1.00000 Example 5: Input: nums1 = [2], nums2 = [] Output: 2.00000 Constraints: nums1.length == m nums2.length == n 0 <= m <= 1000 0 <= n <= 1000 1 <= m + n <= 2000 -106 <= nums1[i], nums2[i] <= 106 确定一下输入应满足的条件：两个数组的长度可以有一个为 $0$（此时中位数就是另一个数组的中位数），但不能同时为 $0$。 很容易想到时间复杂度为 $O(m+n)$ 的方法，但是 follow-up 要求复杂度为 $O(\log(m+n))$。从复杂度看应该用分治法。事实上，复杂度可以减少到 $O(\log(\min(m, n)))$。 …