通配符匹配 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 这个问题可以用递归来求解，对于一个值，先分别生成它的左右子树的集合，然后把这些子树组合即可。 …
二叉树非递归遍历算法的快速实现
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。 …