将正整数表示为若干平方数之和 Perfect Squares
2019-05-08
https://leetcode.com/problems/perfect-squares/ Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n. Example 1: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4. Example 2: Input: n = 13 Output: 2 Explanation: 13 = 4 + 9. 动态规划 $$ f(i) = \min\{f(i - s)\} + 1, 其中 s 为平方数且 1 \le s \le i$$ …
幂运算 pow(x, n) 的一个迭代实现
2018-08-24
求一个浮点数的整数次幂： https://leetcode.com/problems/powx-n/ Implement pow(x, n), which calculates x raised to the power n (i.e. xn). Example 1: Input: x = 2.00000, n = 10 Output: 1024.00000 Example 2: Input: x = 2.10000, n = 3 Output: 9.26100 Example 3: Input: x = 2.00000, n = -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25 Constraints: -100.0 < x < 100.0 -231 <= n <= 231-1 -104 <= xn <= 104 基本就是分治思想，用递归就能很方便地实现，也可以把递归改写成迭代，但我在 Discuss 区看见了一个精奇的迭代思路1。 …
通配符匹配 Wildcard Matching
2018-06-12
通配符匹配问题： https://leetcode.com/problems/wildcard-matching/ Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘?’ and ‘*’. ‘?’ Matches any single character. ‘*’ Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial). Note: s could be empty and contains only lowercase letters a-z. p could be empty and contains only lowercase letters a-z, and characters like ? or *. 待匹配字串 s 中只有字母，模式串中 p 只含有字母和 ?、*，? 匹配任意单个字符，* 匹配任意多个字符（包括空字串），判断字串是否完全匹配。 使用递归算法会超时。 …
数组中首个缺失的正整数 First Missing Positive
2018-06-08
找出数组中首个缺失的正整数： https://leetcode.com/problems/first-missing-positive/ Given an unsorted integer array, find the smallest missing positive integer. Example 1: Input: [1,2,0] Output: 3 Example 2: Input: [3,4,-1,1] Output: 2 Example 3: Input: [7,8,9,11,12] Output: 1 Note: Your algorithm should run in O(n) time and uses constant extra space. 看起来很简单，首先想到排序的方法，时间复杂度为 $O(n\log(n))$。 也可以用最小堆/优先队列，在平均情况下也只要 $O(n)$，最坏情况下为 $O(n\log(n))$，空间复杂度为 $O(n)$。 以上两种方法均能 AC。然而题目要求时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。 …
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。 …