/leetcode

sync from leetcode

Primary LanguageJava

Summary

I have solved 174 problems：Easy(37)、Medium(105)、Hard(32)。

leetcode_generate.py脚本改自 https://github.com/bonfy/leetcode/blob/master/leetcode_generate.py

# Title Source Code Difficulty Last submission date Last submission url
1 two-sum Java Easy 2018-02-10 18:10:20 https://leetcode.com/submissions/detail/140256555/
2 add-two-numbers Java Medium 2019-01-11 17:44:01 https://leetcode.com/submissions/detail/200522321/
3 longest-substring-without-repeating-characters Java Medium 2018-02-21 18:24:58 https://leetcode.com/submissions/detail/141744296/
4 median-of-two-sorted-arrays Java Hard 2018-02-16 18:25:29 https://leetcode.com/submissions/detail/141081067/
5 longest-palindromic-substring Java Medium 2018-02-16 23:00:12 https://leetcode.com/submissions/detail/141091696/
6 zigzag-conversion Java Medium 2018-02-14 23:33:10 https://leetcode.com/submissions/detail/140871013/
7 reverse-integer Java Easy 2018-02-17 23:41:19 https://leetcode.com/submissions/detail/141194748/
8 string-to-integer-atoi Java Medium 2018-02-18 23:16:36 https://leetcode.com/submissions/detail/141326255/
9 palindrome-number Java Easy 2018-02-18 00:00:44 https://leetcode.com/submissions/detail/141195967/
10 regular-expression-matching Java Hard 2018-02-20 13:29:27 https://leetcode.com/submissions/detail/141572575/
11 container-with-most-water Java Medium 2018-02-20 15:09:08 https://leetcode.com/submissions/detail/141586207/
14 longest-common-prefix Java Easy 2018-02-21 15:37:19 https://leetcode.com/submissions/detail/141731052/
15 3sum Java Medium 2018-02-11 21:00:34 https://leetcode.com/submissions/detail/140417724/
16 3sum-closest Java Medium 2018-02-11 23:46:04 https://leetcode.com/submissions/detail/140428336/
17 letter-combinations-of-a-phone-number Java Medium 2018-02-21 21:57:16 https://leetcode.com/submissions/detail/141753043/
18 4sum Java Medium 2018-02-12 00:18:36 https://leetcode.com/submissions/detail/140430757/
19 remove-nth-node-from-end-of-list Java Medium 2018-02-21 22:29:18 https://leetcode.com/submissions/detail/141754974/
20 valid-parentheses Java Easy 2018-02-21 22:56:30 https://leetcode.com/submissions/detail/141756770/
21 merge-two-sorted-lists Java Easy 2018-02-21 20:18:13 https://leetcode.com/submissions/detail/141748396/
22 generate-parentheses Java Medium 2018-02-22 18:23:12 https://leetcode.com/submissions/detail/141887702/
23 merge-k-sorted-lists Java Hard 2018-02-22 18:46:21 https://leetcode.com/submissions/detail/141888811/
24 swap-nodes-in-pairs Java Medium 2018-02-22 20:31:18 https://leetcode.com/submissions/detail/141893223/
25 reverse-nodes-in-k-group Java Hard 2018-02-22 21:16:08 https://leetcode.com/submissions/detail/141895518/
26 remove-duplicates-from-sorted-array Java Easy 2018-02-22 21:31:01 https://leetcode.com/submissions/detail/141896420/
27 remove-element Java Easy 2018-02-22 21:39:30 https://leetcode.com/submissions/detail/141896969/
28 implement-strstr Java Easy 2018-02-22 22:32:31 https://leetcode.com/submissions/detail/141900320/
30 substring-with-concatenation-of-all-words Java Hard 2018-02-27 14:32:28 https://leetcode.com/submissions/detail/142590854/
31 next-permutation Java Medium 2018-02-23 12:52:35 https://leetcode.com/submissions/detail/141993157/
32 longest-valid-parentheses Java Hard 2018-02-24 13:52:11 https://leetcode.com/submissions/detail/142123797/
33 search-in-rotated-sorted-array Java Medium 2018-02-24 20:47:12 https://leetcode.com/submissions/detail/142156727/
34 find-first-and-last-position-of-element-in-sorted-array Java Medium 2018-02-24 21:52:23 https://leetcode.com/submissions/detail/142159882/
35 search-insert-position Java Easy 2018-02-24 22:07:06 https://leetcode.com/submissions/detail/142160707/
36 valid-sudoku Java Medium 2018-02-25 23:09:14 https://leetcode.com/submissions/detail/142316125/
37 sudoku-solver Java Hard 2018-02-25 23:43:48 https://leetcode.com/submissions/detail/142318388/
39 combination-sum Java Medium 2018-02-26 11:51:08 https://leetcode.com/submissions/detail/142409572/
40 combination-sum-ii Java Medium 2018-02-26 13:03:43 https://leetcode.com/submissions/detail/142420608/
41 first-missing-positive Java Hard 2018-02-26 13:23:42 https://leetcode.com/submissions/detail/142423486/
42 trapping-rain-water Java Hard 2018-02-20 16:32:08 https://leetcode.com/submissions/detail/141595380/
43 multiply-strings Java Medium 2018-02-13 00:49:14 https://leetcode.com/submissions/detail/140594777/
44 wildcard-matching Java Hard 2018-02-21 14:06:23 https://leetcode.com/submissions/detail/141718079/
45 jump-game-ii Java Hard 2018-02-26 17:22:20 https://leetcode.com/submissions/detail/142456566/
46 permutations Java Medium 2018-02-23 13:09:33 https://leetcode.com/submissions/detail/141995569/
47 permutations-ii Java Medium 2018-02-23 13:52:09 https://leetcode.com/submissions/detail/142001817/
48 rotate-image Java Medium 2018-02-26 18:24:02 https://leetcode.com/submissions/detail/142461599/
49 group-anagrams Java Medium 2018-02-26 19:31:42 https://leetcode.com/submissions/detail/142465441/
50 powx-n Java Medium 2018-02-26 20:57:01 https://leetcode.com/submissions/detail/142470818/
51 n-queens Java Hard 2018-02-26 22:12:41 https://leetcode.com/submissions/detail/142476557/
52 n-queens-ii Java Hard 2018-02-26 22:23:16 https://leetcode.com/submissions/detail/142477343/
53 maximum-subarray Java Easy 2018-02-26 22:33:07 https://leetcode.com/submissions/detail/142478127/
54 spiral-matrix Java Medium 2017-06-13 20:30:48 https://leetcode.com/submissions/detail/105911684/
55 jump-game Java Medium 2018-02-26 22:46:04 https://leetcode.com/submissions/detail/142479136/
56 merge-intervals Java Medium 2018-02-26 23:08:46 https://leetcode.com/submissions/detail/142481008/
57 insert-interval Java Medium 2018-02-26 23:27:24 https://leetcode.com/submissions/detail/142482489/
58 length-of-last-word Java Easy 2018-02-26 23:32:54 https://leetcode.com/submissions/detail/142482962/
59 spiral-matrix-ii Java Medium 2018-02-26 23:50:25 https://leetcode.com/submissions/detail/142484416/
61 rotate-list Java Medium 2018-02-27 18:49:57 https://leetcode.com/submissions/detail/142621214/
62 unique-paths Java Medium 2018-02-27 19:29:35 https://leetcode.com/submissions/detail/142623298/
63 unique-paths-ii Java Medium 2018-02-27 19:44:17 https://leetcode.com/submissions/detail/142624252/
64 minimum-path-sum Java Medium 2018-02-27 20:44:20 https://leetcode.com/submissions/detail/142628419/
67 add-binary Java Easy 2018-02-12 13:17:11 https://leetcode.com/submissions/detail/140537669/
69 sqrtx Java Easy 2018-02-27 23:23:26 https://leetcode.com/submissions/detail/142641624/
70 climbing-stairs Java Easy 2018-02-27 23:30:47 https://leetcode.com/submissions/detail/142642251/
71 simplify-path Java Medium 2018-02-28 00:22:32 https://leetcode.com/submissions/detail/142646998/
72 edit-distance Java Hard 2018-02-28 00:56:49 https://leetcode.com/submissions/detail/142650250/
73 set-matrix-zeroes Java Medium 2018-03-11 19:58:24 https://leetcode.com/submissions/detail/144545185/
74 search-a-2d-matrix Java Medium 2018-03-11 21:02:12 https://leetcode.com/submissions/detail/144550427/
75 sort-colors Java Medium 2018-03-11 21:16:52 https://leetcode.com/submissions/detail/144551696/
76 minimum-window-substring Java Hard 2018-02-28 13:46:58 https://leetcode.com/submissions/detail/142746140/
77 combinations Java Medium 2018-02-26 12:20:33 https://leetcode.com/submissions/detail/142413966/
79 word-search Java Medium 2018-03-12 23:31:30 https://leetcode.com/submissions/detail/144745335/
80 remove-duplicates-from-sorted-array-ii Java Medium 2018-03-16 16:51:24 https://leetcode.com/submissions/detail/145405434/
81 search-in-rotated-sorted-array-ii Java Medium 2018-02-24 21:06:35 https://leetcode.com/submissions/detail/142157545/
82 remove-duplicates-from-sorted-list-ii Java Medium 2018-03-16 17:04:12 https://leetcode.com/submissions/detail/145406815/
84 largest-rectangle-in-histogram Java Hard 2017-05-26 21:18:08 https://leetcode.com/submissions/detail/104078173/
85 maximal-rectangle Java Hard 2017-05-26 21:20:24 https://leetcode.com/submissions/detail/104078284/
86 partition-list Java Medium 2018-03-16 17:22:36 https://leetcode.com/submissions/detail/145408552/
88 merge-sorted-array Java Easy 2018-02-21 20:26:10 https://leetcode.com/submissions/detail/141748700/
91 decode-ways Java Medium 2018-03-01 00:37:32 https://leetcode.com/submissions/detail/142813256/
92 reverse-linked-list-ii Java Medium 2018-02-19 00:35:29 https://leetcode.com/submissions/detail/141331166/
94 binary-tree-inorder-traversal Java Medium 2018-03-08 21:08:17 https://leetcode.com/submissions/detail/144088587/
95 unique-binary-search-trees-ii Java Medium 2018-03-01 01:37:38 https://leetcode.com/submissions/detail/142817860/
96 unique-binary-search-trees Java Medium 2018-03-01 02:14:09 https://leetcode.com/submissions/detail/142820780/
97 interleaving-string Java Hard 2018-03-01 20:07:25 https://leetcode.com/submissions/detail/142947676/
98 validate-binary-search-tree Java Medium 2019-04-15 16:32:28 https://leetcode.com/submissions/detail/222569579/
100 same-tree Java Easy 2018-05-02 16:46:56 https://leetcode.com/submissions/detail/152475735/
101 symmetric-tree Java Easy 2018-03-18 01:10:34 https://leetcode.com/submissions/detail/145579300/
102 binary-tree-level-order-traversal Java Medium 2018-05-02 18:03:14 https://leetcode.com/submissions/detail/152481386/
103 binary-tree-zigzag-level-order-traversal Java Medium 2018-05-02 17:41:15 https://leetcode.com/submissions/detail/152480055/
104 maximum-depth-of-binary-tree Java Easy 2018-05-02 18:20:26 https://leetcode.com/submissions/detail/152482232/
105 construct-binary-tree-from-preorder-and-inorder-traversal Java Medium 2018-03-09 19:23:16 https://leetcode.com/submissions/detail/144241601/
106 construct-binary-tree-from-inorder-and-postorder-traversal Java Medium 2018-03-09 19:10:40 https://leetcode.com/submissions/detail/144240866/
107 binary-tree-level-order-traversal-ii Java Medium 2018-05-02 18:53:01 https://leetcode.com/submissions/detail/152483674/
110 balanced-binary-tree Java Easy 2018-03-18 16:16:51 https://leetcode.com/submissions/detail/145703003/
111 minimum-depth-of-binary-tree Java Easy 2019-04-26 13:31:53 https://leetcode.com/submissions/detail/225029896/
112 path-sum Java Easy 2018-05-02 19:00:42 https://leetcode.com/submissions/detail/152484081/
113 path-sum-ii Java Medium 2018-05-06 19:50:28 https://leetcode.com/submissions/detail/153028293/
114 flatten-binary-tree-to-linked-list Java Medium 2018-01-28 01:17:51 https://leetcode.com/submissions/detail/138127587/
115 distinct-subsequences Java Hard 2018-03-01 21:11:13 https://leetcode.com/submissions/detail/142952536/
116 populating-next-right-pointers-in-each-node Java Medium 2018-05-06 20:47:19 https://leetcode.com/submissions/detail/153031879/
117 populating-next-right-pointers-in-each-node-ii Java Medium 2018-05-06 21:34:03 https://leetcode.com/submissions/detail/153035124/
120 triangle Java Medium 2018-03-02 16:13:47 https://leetcode.com/submissions/detail/143081489/
121 best-time-to-buy-and-sell-stock Java Easy 2018-03-02 03:16:25 https://leetcode.com/submissions/detail/142983794/
122 best-time-to-buy-and-sell-stock-ii Java Easy 2018-03-02 03:41:21 https://leetcode.com/submissions/detail/142986466/
123 best-time-to-buy-and-sell-stock-iii Java Hard 2018-03-02 04:22:32 https://leetcode.com/submissions/detail/142990620/
124 binary-tree-maximum-path-sum Java Hard 2018-05-10 00:05:09 https://leetcode.com/submissions/detail/153500021/
128 longest-consecutive-sequence Java Hard 2019-01-13 18:00:35 https://leetcode.com/submissions/detail/200922373/
129 sum-root-to-leaf-numbers Java Medium 2018-05-10 14:31:49 https://leetcode.com/submissions/detail/153596769/
130 surrounded-regions Java Medium 2019-01-11 21:35:53 https://leetcode.com/submissions/detail/200539347/
131 palindrome-partitioning Java Medium 2018-03-02 21:02:04 https://leetcode.com/submissions/detail/143100316/
132 palindrome-partitioning-ii Java Hard 2018-03-02 22:56:42 https://leetcode.com/submissions/detail/143107667/
139 word-break Java Medium 2018-03-02 23:26:11 https://leetcode.com/submissions/detail/143109830/
140 word-break-ii Java Hard 2018-03-04 00:41:03 https://leetcode.com/submissions/detail/143243070/
142 linked-list-cycle-ii Java Medium 2019-01-13 20:10:59 https://leetcode.com/submissions/detail/200932462/
144 binary-tree-preorder-traversal Java Medium 2018-03-08 21:13:15 https://leetcode.com/submissions/detail/144089104/
145 binary-tree-postorder-traversal Java Medium 2018-03-08 21:20:26 https://leetcode.com/submissions/detail/144089853/
146 lru-cache Java Medium 2018-03-20 18:48:14 https://leetcode.com/submissions/detail/146064526/
147 insertion-sort-list Java Medium 2018-03-13 00:53:05 https://leetcode.com/submissions/detail/144753529/
152 maximum-product-subarray Java Medium 2018-03-02 16:50:29 https://leetcode.com/submissions/detail/143085677/
153 find-minimum-in-rotated-sorted-array Java Medium 2018-02-24 16:55:17 https://leetcode.com/submissions/detail/142143759/
154 find-minimum-in-rotated-sorted-array-ii Java Hard 2018-02-24 20:07:03 https://leetcode.com/submissions/detail/142154970/
155 min-stack Java Easy 2018-02-28 15:01:23 https://leetcode.com/submissions/detail/142759537/
167 two-sum-ii-input-array-is-sorted Java Easy 2018-02-10 18:52:24 https://leetcode.com/submissions/detail/140258540/
173 binary-search-tree-iterator Java Medium 2018-05-02 16:42:14 https://leetcode.com/submissions/detail/152475310/
174 dungeon-game Java Hard 2018-02-27 22:49:16 https://leetcode.com/submissions/detail/142638726/
188 best-time-to-buy-and-sell-stock-iv Java Hard 2018-03-02 15:38:16 https://leetcode.com/submissions/detail/143076695/
198 house-robber Java Medium 2018-03-04 23:48:59 https://leetcode.com/submissions/detail/143405166/
199 binary-tree-right-side-view Java Medium 2018-05-10 14:52:19 https://leetcode.com/submissions/detail/153599592/
200 number-of-islands Java Medium 2018-03-25 21:10:14 https://leetcode.com/submissions/detail/146871687/
206 reverse-linked-list Java Easy 2018-02-18 23:46:34 https://leetcode.com/submissions/detail/141328078/
213 house-robber-ii Java Medium 2018-03-05 00:32:03 https://leetcode.com/submissions/detail/143408812/
214 shortest-palindrome Java Hard 2018-02-17 23:09:52 https://leetcode.com/submissions/detail/141193041/
215 kth-largest-element-in-an-array Java Medium 2019-07-13 16:28:02 https://leetcode.com/submissions/detail/242950891/
222 count-complete-tree-nodes Java Medium 2018-03-12 23:50:18 https://leetcode.com/submissions/detail/144747413/
226 invert-binary-tree Java Easy 2018-03-18 01:01:01 https://leetcode.com/submissions/detail/145578358/
230 kth-smallest-element-in-a-bst Java Medium 2018-03-18 15:17:06 https://leetcode.com/submissions/detail/145696051/
234 palindrome-linked-list Java Easy 2018-02-18 23:42:21 https://leetcode.com/submissions/detail/141327809/
235 lowest-common-ancestor-of-a-binary-search-tree Java Easy 2018-03-08 16:20:59 https://leetcode.com/submissions/detail/144062614/
236 lowest-common-ancestor-of-a-binary-tree Java Medium 2020-07-29 19:37:13 https://leetcode.com/submissions/detail/373159729/
239 sliding-window-maximum Java Hard 2018-02-28 14:40:30 https://leetcode.com/submissions/detail/142755722/
240 search-a-2d-matrix-ii Java Medium 2018-03-11 21:07:59 https://leetcode.com/submissions/detail/144550939/
257 binary-tree-paths Java Easy 2018-05-10 15:59:54 https://leetcode.com/submissions/detail/153607469/
263 ugly-number Java Easy 2018-04-04 17:54:19 https://leetcode.com/submissions/detail/148464199/
264 ugly-number-ii Java Medium 2018-04-05 00:03:37 https://leetcode.com/submissions/detail/148490711/
268 missing-number Java Easy 2018-02-26 13:56:08 https://leetcode.com/submissions/detail/142428274/
279 perfect-squares Java Medium 2018-04-10 19:45:52 https://leetcode.com/submissions/detail/149378260/
287 find-the-duplicate-number Java Medium 2018-02-26 18:40:41 https://leetcode.com/submissions/detail/142462594/
300 longest-increasing-subsequence Java Medium 2018-02-28 15:47:51 https://leetcode.com/submissions/detail/142767120/
303 range-sum-query-immutable Java Easy 2018-05-30 18:36:57 https://leetcode.com/submissions/detail/156549550/
304 range-sum-query-2d-immutable Java Medium 2018-01-22 22:00:59 https://leetcode.com/submissions/detail/137348080/
322 coin-change Java Medium 2019-04-11 16:15:08 https://leetcode.com/submissions/detail/221650701/
337 house-robber-iii Java Medium 2018-03-05 01:14:50 https://leetcode.com/submissions/detail/143412400/
343 integer-break Java Medium 2018-03-24 18:03:03 https://leetcode.com/submissions/detail/146689436/
347 top-k-frequent-elements Java Medium 2018-08-21 23:48:00 https://leetcode.com/submissions/detail/170811643/
354 russian-doll-envelopes Java Hard 2018-02-28 20:45:13 https://leetcode.com/submissions/detail/142792816/
371 sum-of-two-integers Java Medium 2018-02-12 11:42:16 https://leetcode.com/submissions/detail/140523546/
376 wiggle-subsequence Java Medium 2018-03-24 18:28:27 https://leetcode.com/submissions/detail/146690864/
378 kth-smallest-element-in-a-sorted-matrix Java Medium 2018-03-19 07:55:54 https://leetcode.com/submissions/detail/145801668/
407 trapping-rain-water-ii Java Hard 2018-02-21 13:47:04 https://leetcode.com/submissions/detail/141715106/
445 add-two-numbers-ii Java Medium 2018-02-12 14:05:38 https://leetcode.com/submissions/detail/140544910/
454 4sum-ii Java Medium 2018-02-12 11:12:08 https://leetcode.com/submissions/detail/140518628/
491 increasing-subsequences Java Medium 2018-03-09 20:55:20 https://leetcode.com/submissions/detail/144247554/
539 minimum-time-difference Java Medium 2018-02-21 15:15:32 https://leetcode.com/submissions/detail/141728222/
547 number-of-provinces Java Medium 2019-01-13 18:42:36 https://leetcode.com/submissions/detail/200925787/
563 binary-tree-tilt Java Easy 2018-05-02 17:05:15 https://leetcode.com/submissions/detail/152477334/
583 delete-operation-for-two-strings Java Medium 2018-02-28 01:36:08 https://leetcode.com/submissions/detail/142653996/
646 maximum-length-of-pair-chain Java Medium 2018-02-28 20:19:19 https://leetcode.com/submissions/detail/142791083/
653 two-sum-iv-input-is-a-bst Java Easy 2018-02-10 19:31:41 https://leetcode.com/submissions/detail/140260025/
673 number-of-longest-increasing-subsequence Java Medium 2018-02-28 18:12:00 https://leetcode.com/submissions/detail/142783323/
684 redundant-connection Java Medium 2019-01-13 19:11:56 https://leetcode.com/submissions/detail/200928137/
695 max-area-of-island Java Medium 2018-03-26 13:15:25 https://leetcode.com/submissions/detail/146995937/
712 minimum-ascii-delete-sum-for-two-strings Java Medium 2018-02-28 13:15:34 https://leetcode.com/submissions/detail/142741084/
747 min-cost-climbing-stairs Java Easy 2018-02-27 23:53:32 https://leetcode.com/submissions/detail/142644338/
778 reorganize-string Java Medium 2018-02-21 21:17:48 https://leetcode.com/submissions/detail/141750948/
993 tallest-billboard Java Hard 2018-12-14 21:34:59 https://leetcode.com/submissions/detail/195067385/

Detail

1.两数之和

solution1

最直观暴力原生的做法，遍历每个位置i, 看是否有j能够和它组成一个和。

for(int i=0; i< arr.length; i++){
    for(j=i+1; j< arr.length; j++){
        if(arr[i] = arr[j] == sum){
            return (i,j);
        }
    }
}

时间复杂度O(n*n), 空间复杂度O(1)

solution2(prefer)

遍历每一个位置i,看前面是否出现过值sum-arr[i], 如果有，则找到了两数只和。过程中需要借助一个map维护value->index的映射。

function int[] twoSum(int[] arr, int target){
    int[] res = new int[2];
    Map<Integer,Integer> map= new HashMap<>();
    for(int i=0; i< arr.length; i++){
        if(map.contains(target - arr[i])){      
            res[0] = map.get(target - arr[i]);
            res[1] = i;
            return res;
        }
        map.put(arr[i],i);
    }
    return res;
}

solution3

如果输入是一个有序列表，那么可以用双指针夹逼。时间复杂度O(n),空间复杂度O(1)。

function int[] twoSum(int[] arr, int target){
    int start = 0;
    int end = arr.length -1;
    while(start > end){
        if(arr[start] + arr[end] == target){
            return (start,end); 
        }
        if(arr[start] + arr[end] > target){
            start++;
        }else {
            end --;
        }
    }
}

如果输入非有序列表，那么可以先排序O(nLogn), 在执行如上算法。总体时间复杂度O(nLogn)， 空间复杂度O(n)

91. 二叉搜索树构成种类

对于任意一个数字i，根据BST树的性质，比i小的数字都应该在左边，比i大的数字都应在在右边。因此，可以枚举每一个root节点, 对于每一个root节点i，countBSTs(1,n) = countBSTs(1,i-1) * countBSTs(i+1,n), 因此就递归拆机成了两个子问题。

int countBST(int start, int end){
    if(start > end){
        return 0;
    }
    if(start == end){
        1;
    }
    int count =0;
    for(int i=start; i <= end ; i++){
        count += countBST(start, i-1) * countBST(i+1, end);
    }
    return count;
}

画个图，中间存在重复子过程，因此需要保存运算保证中的中间结果--> 带备忘录的递归。