将正整数表示为若干平方数之和 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 *. …
数组中首个缺失的正整数 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))$。 …
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 链表 2. Add Two Numbers 19. Remove Nth Node From End of List 21. Merge Two Sorted Lists 24. Swap Nodes in Pairs 25. Reverse Nodes in k-Group 61. Rotate List 82. Remove Duplicates from Sorted List II 83. Remove Duplicates from Sorted List 86. Partition List 92. Reverse Linked List II 138. Copy List with Random Pointer 141. Linked List Cycle 142. Linked List Cycle II 143. Reorder List …
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). …
牛顿法实现开平方 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 这个问题可以用递归来求解，对于一个值，先分别生成它的左右子树的集合，然后把这些子树组合即可。 …