Skip to content
No description, website, or topics provided.
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.vscode
1.two-sum
100.same-tree
101.symmetric-tree
102.binary-tree-level-order-traversal
103.binary-tree-zigzag-level-order-traversal
104.maximum-depth-of-binary-tree
107.binary-tree-level-order-traversal-ii
108.convert-sorted-array-to-binary-search-tree
11.container-with-most-water
110.balanced-binary-tree
111.minimum-depth-of-binary-tree
112.path-sum
113.path-sum-ii
125.valid-palindrome
126.word-ladder-ii
127.word-ladder
129.sum-root-to-leaf-numbers
131.palindrome-partitioning
143.reorder-list
144.binary-tree-preorder-traversal
145.binary-tree-postorder-traversal
147.insertion-sort-list
148.sort-list
149.max-points-on-a-line
15.3sum
150.evaluate-reverse-polish-notation
16.3sum-closest
167.two-sum-ii-input-array-is-sorted
17.letter-combinations-of-a-phone-number
18.4sum
19.remove-nth-node-from-end-of-list
199.binary-tree-right-side-view
2.add-two-numbers
20.valid-parentheses
202.happy-number
205.isomorphic-strings
206.reverse-linked-list
209.minimum-size-subarray-sum
21.merge-two-sorted-lists
215.kth-largest-element-in-an-array
216.combination-sum-iii
217.contains-duplicate
219.contains-duplicate-ii
220.contains-duplicate-iii
222.count-complete-tree-nodes
226.invert-binary-tree
23.merge-k-sorted-lists
230.kth-smallest-element-in-a-bst
234.palindrome-linked-list
235.lowest-common-ancestor-of-a-binary-search-tree
236.lowest-common-ancestor-of-a-binary-tree
237.delete-node-in-a-linked-list
24.swap-nodes-in-pairs
242.valid-anagram
25.reverse-nodes-in-k-group
257.binary-tree-paths
26.remove-duplicates-from-sorted-array
27.remove-element
279.perfect-squares
283.move-zeroes
290.word-pattern
3.longest-substring-without-repeating-characters
328.odd-even-linked-list
341.flatten-nested-list-iterator
344.reverse-string
345.reverse-vowels-of-a-string
347.top-k-frequent-elements
349.intersection-of-two-arrays
350.intersection-of-two-arrays-ii
39.combination-sum
4.median-of-two-sorted-arrays
40.combination-sum-ii
401.binary-watch
437.path-sum-iii
438.find-all-anagrams-in-a-string
445.add-two-numbers-ii
447.number-of-boomerangs
450.delete-node-in-a-bst
451.sort-characters-by-frequency
454.4sum-ii
46.permutations
47.permutations-ii
49.group-anagrams
61.rotate-list
71.simplify-path
75.sort-colors
76.minimum-window-substring
77.combinations
78.subsets
80.remove-duplicates-from-sorted-array-ii
82.remove-duplicates-from-sorted-list-ii
83.remove-duplicates-from-sorted-list
86.partition-list
88.merge-sorted-array
90.subsets-ii
92.reverse-linked-list-ii
93.restore-ip-addresses
94.binary-tree-inorder-traversal
98.validate-binary-search-tree
.gitignore
130.被围绕的区域.java
200.岛屿的个数.java
37.解数独.java
417.太平洋大西洋水流问题.java
51.n皇后.java
52.n皇后-ii.java
79.单词搜索.java
LICENSE
Main.java
MinHeap.java
README.md

README.md

license

Visual Studio Code Settings

{
    "terminal.integrated.shell.windows": "cmd.exe",
    "terminal.integrated.shellArgs.windows": ["/k", "D:\\Cmder\\vendor\\init.bat"],
    "files.autoSave": "onFocusChange",
    "leetcode.endpoint": "leetcode-cn",
    "leetcode.defaultLanguage": "java"
}

All

ID Title Solution Difficulty
1 Two Sum Java Easy
2 Add Two Numbers Java Medium
3 Longest Substring without Repeating Characters Java Medium
4 Median of Two Sorted Arrays Java Hard
11 Container with Most Water Java Medium
15 3Sum Java Medium
16 3Sum-Closest Java Medium
17 Letter Combinations of A Phone Number Java Medium
18 4Sum Java Medium
19 Remove Nth Node from End of List Java Medium
21 Merge Two Sorted Lists Java Easy
23 Merge K Sorted Lists Java Hard
24 Swap Nodes in Pairs Java Medium
25 Reverse Nodes in K Group Java Hard
26 Remove Duplicates from Sorted Array Java Easy
27 Remove Element Java Easy
39 Combination Sum Java Medium
40 Combination Sum II Java Medium
46 Permutations Java Medium
47 Permutations II Java Medium
49 Group Anagrams Java Medium
61 Rotate List Java Medium
71 Simplify Path Java Medium
75 Sort Colors Java Medium
76 Minimum Window Substring Java Hard
77 Combinations Java Medium
78 Subsets Java Medium
80 Remove Duplicates from Sorted Array Java Medium
82 Remove Duplicates from Sorted List II Java Medium
83 Remove Duplicates from Sorted List Java Easy
86 Partition List Java Medium
88 Merge Sorted Array Java Easy
90 Subsets II Java Medium
92 Reverse Linked List II Java Medium
93 Restore IP Addresses Java Medium
94 Binary Tree Inorder Traversal Java Medium
98 Validate Binary Search Tree Java Medium
100 Same Tree Java Easy
100 Symmetric Tree Java Easy
102 Binary Tree Level Order Traversal Java Medium
103 Binary Tree Zigzag Level Order Traversal Java Medium
104 Maximum Depth of Binary Tree Java Easy
107 Binary Tree Level Order Traversal II Java Easy
108 Convert Sorted Array to Binary Search Tree Java Easy
110 Balanced Binary Tree Java Easy
111 Minimum Depth of Binary Tree Java Easy
112 Path Sum Java Easy
113 Path Sum II Java Medium
125 Valid Palindrome Java Easy
126 Word Ladder II Java Hard
127 Word Ladder Java Medium
129 Sum Root to Leaf Numbers Java Medium
131 Palindrome Partitioning Java Medium
143 Reorder List Java Medium
144 Binary Tree Preorder Traversal Java Medium
145 Binary Tree Postorder Traversal Java Hard
147 Insertion Sort List Java Medium
148 Sort List Java Medium
149 Max Points on A Line Java Hard
150 Evaluate Reverse Polish Notation Java Medium
167 Two Sum II Input Array is Sorted Java Easy
199 Binary Tree Right Side View Java Medium
202 Happy Number Java Easy
205 Isomorphic Strings Java Easy
206 Reverse Linked List Java Easy
209 Minimum Size Subarray Sum Java Medium
215 Kth Largest Element in An Array Java Medium
216 Combination Sum III Java Medium
217 Contains Duplicate Java Easy
219 Contains Duplicate II Java Easy
220 Contains Duplicate III Java Medium
222 Count Complete Tree Nodes Java Medium
226 Invert Binary Tree Java Easy
230 Kth Smallest Element in A BST Java Medium
234 Palindrome Linked List Java Easy
235 Lowest Common Ancestor of A Binary Search Tree Java Easy
237 Delete Node in A Linked List Java Easy
242 Valid Anagram Java Easy
257 Binary Tree Paths Java Easy
279 Perfect Squares Java Medium
283 Move Zeros Java Easy
290 Word Pattern Java Easy
328 Odd Even Linked List Java Medium
341 Flatten Nested List Iterator Java Medium
344 Reverse String Java Easy
345 Reverse Vowels of A String Java Easy
347 Top K Frequent Elements Java Medium
349 Intersection of Two Arrays Java Easy
350 Intersection of Two Arrays II Java Easy
401 Binary Watch Java Easy
437 Path Sum III Java Easy
438 Find All Anagrams in A String Java Easy
445 Add Two Numbers II Java Medium
447 Number of Boomerangs Java Easy
450 Delete Node in A BST Java Medium
451 Sort Characters by Frequency Java Medium
454 4Sum-II Java Medium

Array

ID Title Solution Difficulty
3 Longest Substring without Repeating Characters Java Medium
11 Container with Most Water Java Medium
26 Remove Duplicates from Sorted Array Java Easy
27 Remove Element Java Easy
75 Sort Colors Java Medium
76 Minimum Window Substring Java Hard
80 Remove Duplicates from Sorted Array Java Medium
88 Merge Sorted Array Java Easy
125 Valid Palindrome Java Easy
167 Two Sum II Input Array is Sorted Java Easy
209 Minimum Size Subarray Sum Java Medium
215 Kth Largest Element in An Array Java Medium
283 Move Zeros Java Easy
344 Reverse String Java Easy
345 Reverse Vowels of A String Java Easy
438 Find All Anagrams in A String Java Easy

循环不变量:一个循环不变量是指在循环开始和循环中每一次迭代时永远为真的量,这意味着在循环中和循环结束时循环不变量和循环终止条件必须同时成立。

数组相关的题目通常考察基础算法,例如排序和查找。或者考察关于程序设计问题,通常使用双索引技术:

  • 对撞指针
  • 滑动窗口 例如翻转字符串等就需要从数组两端开始使用对撞指针,而查找满足要求的字串之类的问题则从数组一端开始使用滑动窗口。

Search Table

ID Title Solution Difficulty
1 Two Sum Java Easy
15 3Sum Java Medium
16 3Sum-Closest Java Medium
18 4Sum Java Medium
49 Group Anagrams Java Medium
149 Max Points on A Line Java Hard
202 Happy Number Java Easy
205 Isomorphic Strings Java Easy
217 Contains Duplicate Java Easy
219 Contains Duplicate II Java Easy
220 Contains Duplicate III Java Medium
242 Valid Anagram Java Easy
290 Word Pattern Java Easy
349 Intersection of Two Arrays Java Easy
350 Intersection of Two Arrays II Java Easy
447 Number of Boomerangs Java Easy
451 Sort Characters by Frequency Java Medium
454 4Sum II Java Medium

通常使用 HashMap 和 HashSet 对数据进行存储,查找的时候就可以在 O(1) 的时间复杂度内完成。

Linked List

ID Title Solution Difficulty
2 Add Two Numbers Java Medium
19 Remove Nth Node from End of List Java Medium
21 Merge Two Sorted Lists Java Easy
23 Merge K Sorted Lists Java Hard
24 Swap Nodes in Pairs Java Medium
25 Reverse Nodes in K Group Java Hard
61 Rotate List Java Medium
82 Remove Duplicates from Sorted List II Java Medium
83 Remove Duplicates from Sorted List Java Easy
86 Partition List Java Medium
92 Reverse Linked List II Java Medium
143 Reorder List Java Medium
147 Insertion Sort List Java Medium
148 Sort List Java Medium
206 Reverse Linked List Java Easy
234 Palindrome Linked List Java Easy
237 Delete Node in A Linked List Java Easy
328 Odd Even Linked List Java Medium
445 Add Two Numbers II Java Medium

如果需要操作链表的头节点时,通常设置虚拟头节点。同时根据问题描述,通常还可以使用快慢指针对链表进行遍历,以保证可以在一趟扫描中完成任务。

Stack & Queue

ID Title Solution Difficulty
20 Valid Parentheses Java Easy
23 Merge K Sorted Lists Java Hard
71 Simplify Path Java Medium
94 Binary Tree Inorder Traversal Java Medium
102 Binary Tree Level Order Traversal Java Medium
103 Binary Tree Zigzag Level Order Traversal Java Medium
107 Binary Tree Level Order Traversal II Java Easy
126 Word Ladder II Java Hard
127 Word Ladder Java Medium
144 Binary Tree Preorder Traversal Java Medium
145 Binary Tree Postorder Traversal Java Hard
150 Evaluate Reverse Polish Notation Java Medium
199 Binary Tree Right Side View Java Medium
279 Perfect Squares Java Medium
341 Flatten Nested List Iterator Java Medium
347 Top K Frequent Elements Java Medium

无权图的最短路径可以使用队列进行广度优先搜索。

Binary Tree & Recursion

ID Title Solution Difficulty
98 Validate Binary Search Tree Java Medium
100 Same Tree Java Easy
100 Symmetric Tree Java Easy
104 Maximum Depth of Binary Tree Java Easy
108 Convert Sorted Array to Binary Search Tree Java Easy
110 Balanced Binary Tree Java Easy
111 Minimum Depth of Binary Tree Java Easy
112 Path Sum Java Easy
113 Path Sum II Java Medium
129 Sum Root to Leaf Numbers Java Medium
222 Count Complete Tree Nodes Java Medium
226 Invert Binary Tree Java Easy
230 Kth Smallest Element in A BST Java Medium
235 Lowest Common Ancestor of A Binary Search Tree Java Easy
236 Lowest Common Ancestor of A Binary Tree Java Medium
257 Binary Tree Paths Java Easy
437 Path Sum III Java Easy
450 Delete Node in A BST Java Medium

主要还是利用二叉树其本身递归的结构进行递归解题,同时还有二叉搜索树中序遍历为有序数组这个特点。

Recursion & Backtracking

ID Title Solution Difficulty
17 Letter Combinations of A Phone Number Java Medium
39 Combination Sum Java Medium
40 Combination Sum II Java Medium
46 Permutations Java Medium
47 Permutations II Java Medium
77 Combinations Java Medium
78 Subsets Java Medium
90 Subsets II Java Medium
93 Restore IP Addresses Java Medium
131 Palindrome Partitioning Java Medium
216 Combination Sum III Java Medium
401 Binary Watch Java Easy

排列组合问题。回溯法的套路通常是: 已经在 [0, start) 找到部分结果,对于剩下的另一部分在 [start, n] 中使用循环和递归进行查找。"部分结果"在递归结束后需要恢复原来的状态,在查找另一部分结果之前可以分析能否剪枝。

1. Two Sum

遍历到 nums[i] 时,判断 map 中是否存在 target - nums[i],是则获取其在数组中的索引,否则加入 map。

2. Add Two Numbers

遍历链表,进行计算,需要注意进位问题。

3. Longest Substring Without Repeating Characters

双索引中滑动窗口的方法,当窗口读入字符 s.charAt(j) 时,查看哈希表判断前面字符中是否有该字符,有则获取其索引 index,将 i 移动到 index + 1,同时移除哈希表中对应的键并且加入新字符;否则直接加入哈希表。

11. Container With Most Water

双索引中滑动窗口的方法。根据木桶定律,每次换掉容器短的线段,才有可能装更多的水。

15. 3Sum

在 2Sum 中题目假设每种输入只会对应一个答案,因此可以使用 Map 将时间复杂度控制在 O(N),因此不需要对数组进行排序。而本问题需要返回所有答案,因此时间复杂度肯定大于 O(N),所以可以对数组进行排序,然后将问题转化为求解有序数组中两个数和为某个数。即从 [i + 1, nums.length] 的有序元素中找到和为 -nums[i] 的两个数,使用双索引技术即可。

16. 3Sum-Closest

类似 3Sum,在循环过程中,计算当前三个数的和 sum 与 target 的差,与之前的差进行比较。如果差的绝对值更小,则更接近。然后根据 sum 与 target 的大小进行移动指针。

17. Letter Combinations of A Phone Number

此类问题也叫树形问题,最精简单的方法就是像二叉树一样使用递归解题。如果当前字符不是最后一个字符,那么就递归计算当前字符后面的的所有字符能够构成的字符串列表,然后双重循环构造当前字符能够表示的字符与该列表的拼接结果;否则直接返回当前字符能表示的字符。 或者使用回溯法,也是递归,只不过前者是从最后一个字符往前计算,回溯法是从前往后计算,每次需要将当前计算的结果传给下一步。回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。 通常用递归的方法来实现,解决一些排列组合问题,当递归到终点得到一种答案后回到上一步,继续往下走,直到遍历完所有情况,和图的深度优先搜索一样,因此也叫 DFS。

18. 4Sum

直接在 3Sum 的基础上加一层循环。

  • 时间复杂度:O(N^3)
  • 空间复杂度:O(N^3)

19. Remove Nth Node from End of List

本科的时候从网上看到腾讯有一道笔试题就是只扫描一趟,如何找到链表中间的节点。看了答案就觉得好奇妙啊!设置两个指针,一个每次移动两个节点,一个每次移动一个节点,当快的那个移动到链表末尾的时候,慢的那个就是要找的节点。原来这些题都是有套路的,只可惜以前没人带,强烈推荐这套视频:玩转面试算法

20. Valid Parentheses

栈的应用,主要注意的是:当遍历完字符串后,需要判断栈是否为空。

21. Merge Two Sorted Lists

设置虚拟头节点,比较两个链表的元素,最后需要判断哪个链表还有元素,直接接到结果中。

23. Merge K Sorted Lists

维护一个最小堆,首先放入所有链表的头节点。只要堆不为空就出堆,如果出堆的节点不是还有后继节点,就再将后继节点入堆。或者两两合并链表,需要注意的是如果先合并两个,得到的结果再和第三个合并,直到最后一个,时间复杂度就会比较大;如果每两个合并,得到的结果再每两个合并,即归并排序(迭代或者递归实现分治法)时间复杂度就会比较小。假设一共有 K 个链表,每个链表有 N 个节点,前者的时间复杂度为 (N + N) + (2N + N) + ... + kN = O(NKK),后者的时间复杂度为 (N + N)K/2 + (2N + 2N)K/4 + ... = O(NKlogK)。时间复杂度的分析可以参考主定理。

  • 前者对于第 i 个链表,需要遍历 K - i 次,最后一个链表只需要遍历一次
  • 后者每个链表只需要遍历 logK 次

24. Swap Nodes in Pairs

设置虚拟头节点,两两翻转链表节点。

25. Reverse Nodes in K Group

类似于 #24,只不过每次需要找到第 K + 1 个位置,当 current 到达该位置时,进行下一轮翻转。

26. Remove Duplicates From Sorted Array

设置循环不变量 k 保证 nums 中 [0, ..., k) 的元素值均不重复。由于数组有序,遍历数组到第 i 个元素后,[k, ..., i] 的元素值均不大于 nums[k - 1],如果 nums[i] 值大于 nums[k - 1] 则换到 k 处去。

27. Remove Element

设置循环不变量 k 保证 nums 中 [0, ..., k) 的元素值均不为 val。遍历数组到第 i 个元素后,[k, ..., i] 的元素值均为 val,如果 nums[i] 值不为 val 则换到 k 处去。

39. Combination Sum

为了剪枝需要首先将数组排序,经典的回溯法的套路。

40. Combination Sum II

类似于 #39,排序既可以起到剪枝的作用,还可以保证解集不包含重复的组合。

46. Permutations

这类回溯的题都有一些套路,通常都需要定义一个函数进行递归,函数的参数就是元素集合、当前元素索引和部分结果。在定义的函数中,如果当前元素满足条件则加入 ret;否则记录状态,递归调用该函数遍历其他元素,同时索引和部分结果都有一定的变化;最后恢复状态。

47. Permutations II

类似 #46,为了避免重复元素,通常需要对数组进行排序。在 #46 的基础上多添加一些条件:当 nums[i] 和上一个元素相同,并且上一个元素还没被使用(因为要保留一种情况,所以当相同元素先使用后面的的时候),跳过。

49. Group Anagrams

对字符串中的字符进行排序,然后判断 HashMap 是否有该单词,有则加入其对应的 List。

61. Rotate List

首先计算链表的长度,当 K 等于链表长度时就可以不用翻转,大于链表长度则可以少翻转几次。然后将链表后面的部分接到前面去。

71. Simplify Path

使用栈来存储目录结构,需要注意 "/a/../../b" 此类目录的处理。

75. Sort Colors

计数排序需要遍历数组两次,因此可以使用多路快排的思路。设置循环不变量 zero 和 two 保证 [0, ..., zero] 中元素全为 0, [two, ..., nums.length] 中元素全为 2。索引 i 遍历 (zero, ..., two) 中的元素,(zero, i] 中的元素全为 1。如果 nums[i] 为 0 则换到 zero + 1 处,且 zero 和 i 加一;如果 nums[i] 为 2 则换到 two - 1 处,且 two 减一;如果 nums[i] 为 1 则 i 加一。

76. Minimum Window Substring

双索引中的滑动窗口,使用哈希表记录窗口状态。右指针一直往右移动,直到找到一个子串;左指针一直往右移动,直到该子串为最小子串,记录其长度。然后左指针再往右移动一次,打破子串;右指针继续移动寻找下一个字串。

77. Combinations

注意剪枝的条件,每次回溯需要在 [start, n] 中找 k 个数,当 start 大于 n - k + 1 时,后面的数不足 k 个,因此可以作为剪枝条件。

78. Subsets

类似 #77,回溯法。

80. Remove Duplicates From Sorted Array

设置循环不变量 k 保证 nums 中 [0, ..., k) 相同的元素值不超过两个。遍历数组到第 i 个元素后,[k, ..., i] 的元素值均不大于 nums[k - 1],如果 nums[i] 值大于 nums[k - 1] 则换到 k 处去;如果 nums[i] 值等于 nums[k - 1] 且不等于 nums[k - 2] 则换到 k 处去。

82. Remove Duplicates from Sorted List II

设置虚拟头节点,[dummyHead, pre] 为不含重复元素的链表,用 head 指针遍历链表,在 head 和 head.next 都不为空的情况下,证明有重复的元素,因此找到所有重复的元素,删除。

83. Remove Duplicates from Sorted List

由于给定的是有序列表,因此只需要判断 current 的 next 中的值是否和 current 的相等,是则删除 next。

86. Partition List

遍历两个列表,对节点的值进行判断,需要注意的是:如果最后存在比 x 小的数,即 le 链表不为空,那么 geqHead 链表末尾需要置为 null。

88. Merge Sorted Array

归并排序,为了不开辟新的空间,将数组从后面开始排。设置循环不变量 k 保证 nums1 中 (k, ...] 为有序,m 和 n 遍历完数组后,如果 nums2 有剩余则拷贝到 nums1 中,否则排序完毕。

90. Subsets II

类似 #40,对数组进行排序可以保证解集不包含重复的子集。

92. Reverse Linked List II

head 节点比较特殊,简化代码需要设立虚拟头节点,然后 head 移动到需要翻转的子链表的上一个节点,即 head 的 next 应该指向反转后的子链表的头节点。使用 begin 记录 head.next(即已经反转好的部分链表的尾),使用 end 记录已经反转好的部分链表的头,初始化为空,然后进行翻转。

93. Restore IP Addresses

IP 地址一共分为四部分,每部分的长度为 1~3,如果某一部分以 0 开头,那么就只能是 0,最大为 255。回溯法,递归函数每次传入待分析的字符串、IP 地址有效的那一部分和目前已经分析了几部分。当目前已经分析了三部分,并且待分析的字符串有效,则拼接并且加入 ret;否则遍历待分析字符串,将其分为两部分,如果前半部分有效,则继续递归。

94. Binary Tree Inorder Traversal

使用了 Command 类的前中后序非递归遍历很好理解,也很容易在三者之间切换。不使用 Command 类则只要当前节点不为空,就将其左子节点入栈,然后当前节点指向其左子节点;否则出栈(当前节点的父节点),然后访问出栈后的节点的值,再将其右子节点入栈。

98. Validate Binary Search Tree

记录当前节点的取值范围,判断是否满足,同时递归判断左右子树是否属于有效二叉搜索树。还可以利用二叉搜索树的性质:中序遍历的结果为有序数组。记录每一个节点中序遍历的前驱,判断其是否小于前驱。

100. Same Tree

使用递归,当两个节点都为空时返回 true。当两个节点都不为空时,判断这两个节点的值是否相等,左子树和右子树是否相等。或者使用迭代的方法,维护一个栈,将两棵树的根节点压栈,当栈不为空,则弹出两个节点,如果两个节点都为空,则继续弹出两个节点;如果其中一个为空,则返回 false,否则判断它们的值是否相等。然后压入这两个节点的左子树和右子树。

101. Symmetric Tree

类似 #100,即判断给定的根节点的两个子二叉树是否对称。使用迭代或者递归的方法即可,迭代时节点入栈的顺序和 #100 稍有不同,因为 p 的左子树需要和 q 的右子树进行对比。

102. Binary Tree Level Order Traversal

使用队列存储节点,这里学会了使用 Pair 类来保存节点和其层数。同时也可以使用递归来对二叉树进行遍历。

103. Binary Tree Zigzag Level Order Traversal

类似 #102,遇到奇数层则倒序访问当前层节点。

104. Maximum Depth of Binary Tree

如果当前节点不为空,取左右节点深度的最大值,然后加上一作为当前节点的深度。

107. Binary Tree Level Order Traversal II

类似 #102,既可以使用队列也可以使用递归。只不过在访问节点时,需要将其层数倒序插入。

108. Convert Sorted Array to Binary Search Tree

根据二叉搜索树的特点,中序遍历就是有序数组。因此数组中间的元素即根节点,左边的元素即左子树,右边的元素即右子树。递归生成左右子树。

110. Balanced Binary Tree

如果左右子树的高度差大于 1,则不是平衡二叉树。否则,判断两个子树是否也都是平衡二叉树。

111. Minimum Depth of Binary Tree

与最大深度不同的是,只有叶子节点才能作为终点。即如果当前左右节点都不为空的情况下才能计算深度。

112. Path Sum

类似 #111,只有叶子节点才能作为终点。

113. Path Sum II

类似 #112,但要求保存路径。可以从叶子节点到根节点保存路径,也可以从根节点到叶子节点保存路径。

125. Valid Palindrome

首先对字符串进行预处理,然后双索引中指针对撞的方法。

126. Word Ladder II

类似 #127,由于需要保存所有最短路径,因此难度较大,因此使用 BFS + DFS 进行搜索。值得注意的是,wordList 长度可能很大,例如每个单词长度为 3,则最多可以有 26x26x26 个单词,对于每个单词 curWord,寻找其能转换的单词就需要这么多次的计算。这里则将 wordList 加入 HashSet 中,然后遍历 curWord 可能转换的单词,在判断其是否存在 HashSet 中即可,每次只需要计算 26+26+26 次(HashSet 查找的时间复杂度为 O(1))。

127. Word Ladder

类似 #279,字符串出队后,将 wordList 中与该字符串字有一个字符不同,且没访问过的字符串入队。

129. Sum Root to Leaf Numbers

递归可以使用前向记录和后向记录,由于数字前面的 0 无法记录,所以后向记录只能使用字符串并且回到根节点时需要遍历结果,因此速度比较慢。前向则每到一个节点就记录当前的值 num,如果该节点没有子节点就将其累加到 sum 中,否则递归计算左右子树。最后返回之前需要恢复 num 的值。

131. Palindrome Partitioning

类似 #93,需要注意的是: 基础类型传值,Object 传引用。String、Integer、Double 等 immutable 类型因为没有提供自身修改的函数,即保存 value 的类变量是 Final 属性,无法被修改,只能被重新赋值/生成新的对象每次操作都是新生成一个对象,所以可以认为是传值。因此每次添加到 ret 中的时候需要新建对象,并且递归完后需要删除最后加入的元素。

143. Reorder List

主要分为三个步骤:找到中间的节点,将链表分为两部分;将后面的节点翻转;合并两个链表。

144. Binary Tree Preorder Traversal

首先将根节点压入栈中,然后只要栈不为空就从中弹出节点,弹出节点后访问节点的值,还需要压入其右子节点和左子节点。由于是前序遍历,因此会先遍历左节点,那么在压栈的时候注意先压入右节点。

145. Binary Tree Postorder Traversal

后序遍历非递归形式比较复杂,可以使用逆向的四维,只要当前节点不为空,就将其节点值加入 ret 的最前面,然后入栈,再指向其右子节点;否则出栈(当前节点的父节点),然后当前节点指向其左子节点。

147. Insertion Sort List

相当于新建了一个链表,遍历原链表的元素,然后在新建的链表中找到其位置,插入。

148. Sort List

归并排序的链表实现,因此可以分为两种自顶向下(递归)和自底向上(循环),后者稍微有点麻烦,需要把待排序的链表切出来,排序后再放回原链表。

149. Max Points on A Line

遍历所有点 i,使用 HashMap 记录所有点与点 i 所构成的直线的斜率,Key 为斜率。需要注意的是:可能有重合的点,所以需要另一个变量记录重合的点的个数;计算斜率存在精度问题,因此需要先求最小公约数,然后算约分后的分子和分子,此处不适合用浮点数或者数组作为 Key。因为浮点数 -0.0 != 0.0;数组的 equals 函数比较是否是同一个对象,可以使用 List 或者将分子分母拼接起来作为 Key。

150. Evaluate Reverse Polish Notation

利用栈求解逆波兰式,需要注意的是:在运算的过程中,先出栈的是第二个操作数,后出栈的是第一个操作数。

167. Two Sum II Input Array Is Sorted

可以对每个元素 nums[i] 使用二分查找法,查找 target - nums[i],时间复杂为 O(Nlogn)。或者一边遍历数组,一边将其存入哈希表中,空间复杂度为 O(N)。这里可以使用双索引中指针对撞的方法,从数组两端开始查找,过大则右指针减一,过小则左指针加一。

199. Binary Tree Right Side View

类似 #102,只不过只需要保留每一层最右侧的节点的值。

202. Happy Number

使用 HashSet 记录曾经计算过的数字,如果再次出现则表示进入循环,无解。计算过程独立成一个函数。

205. Isomorphic Strings

由于是一一对应,不能一对多,也不能多对一。因此需要使用 HashMap 的同时使用 HashSet 记录出现过的字符串。

206. Reverse Linked List

链表翻转,注意多设置几个指针:pre, current, next。递归则将链表分成两部分:已经翻转的部分和未翻转的部分。

209. Minimum Size Subarray Sum

滑动窗口,当 [left, ..., right] 中元素的和小于 s 时,right 加一;否则 left 加一。求和后需要判断子数组长度是否最小。

  • 题目还要求实现时间复杂度为 O(NlogN) 的解法,主要思路是构建数组 sums,其元素值 sums[i] = sums[i - 1] + nums[i]。将问题转化为查找 target = sums[i] + s 的索引 k,因此子数组长度为 k - i。需要注意整型数越界问题!

215. Kth Largest Element In An Array

排序后找第 k 大的数时间复杂度为 O(N),借鉴快速排序设置 pivot 的思想将时间复杂度降为 O(N)。选数组首个元素作为 pivot,设置循环不变量保证 (j, ..., end] 中的元素均大于 pivot;当 i > j 时,[begin, ..., j] 中的元素均不大于 pivot。此时若 end - j >= k,即大于 pivot 的元素个数大于等于 k 个,因此继续去 (j, ..., end] 中找第 k 大的数;若大于 pivot 的元素个数等于 k - 1 个,pivot 即为第 k 大的数;否则去 [begin, ..., j] 中找第 k - (end - j) - 1 大的数。递归式为:T(n) = O(N) + T(n/2)

216. Combination Sum III

i > n 可以作为回溯的剪枝条件。

217. Contains Duplicate

遍历数组,将元素存在 HashSet 中进行判断。

219. Contains Duplicate II

遍历数组元素 i,判断其是否存在 HashSet 中,是则返回 True。否则将其加入 set,如果 set 的大小大于 k,则移除元素 nums[i - k]。

220. Contains Duplicate III

类似 #219,使用 TreeSet 有序记录数据,最后判断是否包含 [nums[i] - t, nums[i] + t + 1]。TreeSet 操作的时间复杂度为 O(logN),需要注意的是,加法可能会导致整型数溢出。

222. Count Complete Tree Nodes

递归的方法十分简单,这里可以根据完全二叉树的性质使用迭代求解。满二叉树的节点的个数为:2^height-1,其中 height 为树的高度。因此如果右子树的高度为 height - 1,就表示左子树高度为 height 的满二叉树;否则右子树为高度为 height - 2 的满二叉树。然后使用满二叉树节点个数的公式计算节点数,

226. Invert Binary Tree

使用递归翻转二叉树。先交换子节点,再递归翻转子节点的二叉树。

230. Kth Smallest Element in A BST

使用中序遍历(迭代或者递归),当遍历到第 K 个元素时返回该节点的值。或者利用二叉搜索树的特点,计算左子树节点的个数 leftSize,如果其等于 K - 1,那么当前节点就是第 K 个节点;大于等于 K 则继续去左子树找第 K 大的节点;否则去右子树中找第 K - leftSize - 1 大的节点。由于每次都要对左右子树的节点数进行计算,而进阶要求频繁修改(插入/删除操作)二叉树,可以重新构造二叉树,每个节点还记录该节点左子树的节点的个数,即该节点属于第几大,则在插入或者删除节点的时候,找到该节点的过程中同时修改路径上所有节点的这个值。

234. Palindrome Linked List

先翻转后半部分链表,然后遍历两部分链表的节点值是否相等。无需考虑奇偶数,只要后半部分链表遍历完就行。

235. Lowest Common Ancestor of A Binary Search Tree

根据二分查找树的特点,如果 p 和 q 在 root 的同一侧,则递归计算该侧;否则 root 为待找节点。

236. Lowest Common Ancestor of A Binary Tree

与 #235 不同的是,这里是任意的二叉树。如果当前节点为待找节点之一,则返回当前节点;然后找左子树和右子树,如果左右子树都有待找节点,则 root 为公共祖先,否则继续返回找到的节点。

237. Delete Node in A Linked List

目前位置最简单的一道题了,题目这次不再要求不能改变节点的值,因此直接把下一个节点的值赋值给待删除节点,然后删除下一个节点,由于题目说明给定节点为非末尾节点,因此不需要考虑边界问题。

242. Valid Anagram

遍历字符串统计每个字符个数,加入查找表中再与目标字符串匹配。原问题只有小写字母只需大小为 26 的整型数组,进阶直接使用哈希表。

257. Binary Tree Paths

递归遍历节点。如果当前节点没有子节点,则返回当前节点的值,否则返回当前节点的值与其左右子节点的路径进行拼接后的结果。

279. Perfect Squares

将 n 入队,只要队列不为空,每次取出队首元素,值为 0 则返回 step;否则将其减去 i 的平方后的数入队,同时 step 加一。需要注意的是:每次取出的元素,其减去 i 的平方后的数可能已经在队列中,则需要设置一个数组来记录该数是否已经访问过。即通过对问题进行建模,将问题转化成图的广度优先搜索。

283. Move Zeros

设置循环不变量 k 保证 nums 中 [0, ..., k) 的元素均为非 0 元素。遍历数组到第 i 个元素后,[k, ..., i] 的元素均为 0,如果 nums[i] 为非 0 元素则换到 k 处去。当输入的数组中的元素均为非 0 元素,k 和 i 同时指向同一个非 0 元素,但是不需要交换元素的值。

  • 通过加减法或者异或运算交换两个元素的值:
    public void swap(int[] nums, int i, int j) {
        nums[i] = nums[i] + nums[j]; 
        nums[j] = nums[i] - nums[j];
        nums[i] = nums[i] - nums[j];
    }
    
    public void swap(int[] nums, int i, int j) {
        nums[i] = nums[i] - nums[j];
        nums[j] = nums[i] + nums[j];
        nums[i] = nums[j] - nums[i];
    }
    
    public void swap(int[] nums, int i, int j) {
        nums[i] ^= nums[j];
        nums[j] ^= nums[i];
        nums[i] ^= nums[j];
    }
    这类方法不需要使用辅助变量,思路也简单。但是需要注意的是使用加法有可能导致整数溢出,而且 i == j 则会导致此三种方法交换后元素值为 0。在常见平台上,编译成汇编代码后不使用辅助变量未必更快,因此不建议使用此类方法。
  • 通过函数交换两个元素的值:
    public T swap(T a, T b) { return a; }
    
    a = swap(b, b=a);
    这种方法的原理是先将 b 作为参数传给 swap 函数,然后再给 b 赋值

290. Word Pattern

由于是一一对应,不能一对多,也不能多对一。因此需要使用 HashMap 的同时使用 HashSet 记录出现过的字符串。

328. Odd Even Linked List

设置 evenHead 记录偶数链表的头节点,最后再将偶数链表拼接到奇数链表后面。

341. Flatten Nested List Iterator

将列表逆向存入栈中,在 hasNext() 中如果栈不为空而且栈顶元素不是整型数,则弹出 List,在将 List 中的元素逆向压入栈中,重复操作直到栈为空或者栈顶元素为整型数。栈为空则返回 false。

344. Reverse String

无法直接在原字符串上进行操作,需要将字符串转为字符数组后对字符进行交换。

  • 或者也可以直接使用 StringBuilderreverse 方法:
    StringBuilder sb = new StringBuilder(s);
    return sb.reverse().toString();
    虽然时间复杂度和空间复杂度一样,但是还是双指针的方法运行速度更快。

345. Reverse Vowels Of A String

只需要在交换之前判断字符是否属于元音字符。

347. Top K Frequent Elements

首先使用 HashMap 统计每个数字出现的次数,然后使用优先队列(最大堆)保存 K 个出现次数最大的数,即可将时间复杂度缩小为 O(NlonK),满足题目要求。当 K 远小于 N 时,性能提升较大。若 K 接近 N,可以使用最小堆保存 N - K 个出现次数最大的数,出队或者无法进队的元素则添加到 ret 中,时间复杂度维为 O(Nlog(N - k))。

349. Intersection Of Two Arrays

使用 set 数据结构对数据进行记录,最后将查找结果存到新的 set 中。HashSet 插入查找的时间复杂度为 O(1),TreeSet 插入查找的时间复杂度为 O(logn)。

350. Intersection Of Two Arrays II

使用 map 数据结构对数据进行记录,最后将查找结果存到新的 map 中,同时维护 map 中 key 对应的 value。HashMap 插入查找的时间复杂度为 O(1),TreeMap 插入查找的时间复杂度为 O(logn)。

401. Binary Watch

构造数组,在回溯的时候判断取的是小时还是分钟。

437. Path Sum III

嵌套递归,将问题分为两部分:路径包含当前节点和不包含当前节点。

438. Find All Anagrams In A String

双索引中的滑动窗口,使用哈希表记录窗口状态。

  • 代码详细说明:
    if (map[s.charAt(right) - 'a'] > 0) count--;
    // 哈希表中对应的值减一,不是 p 中的字符对应哈希表中的值也要减一
    map[s.charAt(right) - 'a']--;
    right++;
    // count 为 0 即找到了异位词,将 left 指针存入列表
    if (count == 0) ret.add(left);
    // 当窗口宽度达到 p 的长度后,每次移动右指针也要移动 left 指针
    if (right - left == p.length()) {
        // left 指针指向的字符对应哈希表中的值如果大于等于 0,表示该字符为 p 中没读完的字符,count 加一
        if(map[s.charAt(left) - 'a'] >= 0) count++;
        // 哈希表中对应的值加一,不是 p 中的字符对应哈希表中的值也要加一
        map[s.charAt(left) - 'a']++;
        left++;
    }

445. Add Two Numbers II

类似于 #2,链表表示的两个整数相加。由于数字最高位位于链表开始位置,又不能翻转链表,因此可以借助栈来实现,注意最后的进位。

477. Number of Boomerangs

根据题意,需要设计时间复杂度为 O(N^2) 的算法。把每一个点作为 i,计算点 i 与其他点距离,存入 HashMap 中,并且统计该距离有多少个点。最后根据相同距离点的个数计算答案。

450. Delete Node in A BST

如果待删除节点值比当前节点的小,则去左子树中删除,如果比当前节点的大,则去右子树中删除。如果当前节点为待删除节点:

  • 如果当前节点为叶子节点,直接置为 null
  • 如果当前节点只有一个子节点,那么将当前节点指向其子节点
  • 如果当前节点有两个子节点,则获取左子树中最大节点的值或者右子树中最小节点的值,赋值给当前节点,然后把那个节点删除

451. Sort Characters By Frequency

使用 HashMap 统计字符的频率,使用桶排序,根据频率倒序生成字符串。需要注意的是,在声明完 List 数组后,使用之前需要判断是否为空,否则创建 List。

454. 4Sum-II

由于每个数组长度为 500,因此需要时间复杂度在 O(N^3) 以下。首先使用 HashMap 记录 A 和 B 两个数组元素相加的可能情况,即每个结果与次数。然后遍历 C 和 D 两个数组,判断查找表中是否有相对应得值,并取得该值的次数。

You can’t perform that action at this time.