LeetCode 个人分类
2018-05-17
数组 11. Container With Most Water 15. 3Sum 16. 3Sum Closest 26. Remove Duplicates from Sorted Array 27. Remove Element 31. Next Permutation 42. Trapping Rain Water 48. Rotate Image 54. Spiral Matrix 59. Spiral Matrix II 60. Permutation Sequence 73. Set Matrix Zeroes 75. Sort Colors 80. Remove Duplicates from Sorted Array II 88. Merge Sorted Array 118. Pascal’s Triangle 119. Pascal’s Triangle II …
Best Time to Buy and Sell Stock III
2018-05-04
股票买入卖出的最佳时间问题： https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/ Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again). Example 1: Input: [3,3,5,0,0,3,1,4] Output: 6 Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3. Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3. Example 2: Input: [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again. Example 3: Input: [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e. max profit = 0. 意即给定一个数组，数组下标表示时间，元素值表示股票价格，买入、卖出最多两次，且买入前必须先卖出，求最大利润。 …
牛顿法实现开平方 sqrt
2018-04-30
在精度要求较低的情况下，可以用二分查找实现开平方，例如 Sqrt(x) - LeetCode 就只需返回 int，即精确到个位。 在求更高精度开平方时，可以利用牛顿法。 …
批量构建二叉查找树时的一个常见错误
2018-04-03
给定一个正整数 n，生成结点值为 1 ~ n 的所有二叉查找树： https://leetcode.com/problems/unique-binary-search-trees-ii/ Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n. For example, Given n = 3, your program should return all 5 unique BST’s shown below. 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 这个问题可以用递归来求解，对于一个值，先分别生成它的左右子树的集合，然后把这些子树组合即可。 算法明明已经 AC 了，然而我在本地测试运行时却出现了 Exception: EXC_BAD_ACCESS (code=EXC_I386_GPFLT) 错误，这个错误是在访问已经 free 掉的内存时产生的。 经过一番 debug，终于发现了问题所在，同时发现网上很多方法也有这个 bug。 …
二叉树非递归遍历算法的快速实现
2018-03-25
二叉树的递归遍历简洁明了，而非递归遍历则相对复杂，三种递归思路有很大区别，还容易忘。如果不用线索二叉树的话，一般要用栈来实现，即便都是用栈实现，实现思路也有差别，这给我们理解和记忆带来困扰。 本文介绍利用栈来实现的二叉树非递归算法，主要目的是快速实现，而不是详细解释。 …
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)))$。 …
LeetCode 题解
2017-07-24