Blind 75
勿在浮沙筑高台
Leetcode Blind 75 是由 Facebook 工程师 Yangshun 创建的一个包含 75 道题目的列表，包含了数组、二进制、动态规划、图、区间、链表、矩阵、字符串、树和堆。
如果不想看力扣国际站的，我自己在力扣中国站创建了一个列表：
Restart!
Array
Two Sum✅
两数之和，最能想到的是循环遍历，如果要求时间复杂度为 n，那么只能用空间来换时间，使用 map 来存
code
- 时间复杂度
O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
return new int[] { i, map.get(nums[i]) };
} else {
map.put(target - nums[i], i);
}
}
return null;
}
}- 时间复杂度
code
- 时间复杂度
O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (target == nums[i] + nums[j]) {
return new int[] { i, j };
}
}
}
return null;
}
}- 时间复杂度
Tree Sum
最容易想到的是暴力，非常纯正的暴力方法，在 LeetCode 上会超时
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// 暴力法, 时间复杂度O(n^3)
// 保证不重复的话，暴力到极致：Set存然后添加时Sort
Set<List<Integer>> res = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
for (int k = j + 1; k < nums.length; k++) {
if (0 == nums[i] + nums[j] + nums[k]) {
List<Integer> temp = new ArrayList<>();
temp.add(nums[i]);
temp.add(nums[j]);
temp.add(nums[k]);
Collections.sort(temp);
res.add(temp);
}
}
}
}
return new ArrayList<List<Integer>>(res);
}
}第二种是排序+双指针的方法，因为三数之和是零，所以必然在数组中是正负相加，排序后，正数部分在数组的后面，负数部分在数组的前面。难点是如何写对双指针遍历的部分和跳过重复数字部分。
遍历部分，当前指针的数字为
nums[i]，双指针遍历的低位为nums[j]，j = i + 1， 高位部分为nums[k]，k = len，j++,k—跳过重复部分，对于
i来说要考虑nums[i - 1] == nums[i]是则跳过，对于双指针遍历来说，需要考虑j < k的情况下nums[j] == nums[j++]，对于k同样的nums[k] == nums[k—]，此处的跳过是在找到sum == 0的情况移动双指针的思路，当
sum == 0则将当前数组加入结果集，如果sum > 0则只移动k，如果sum < 0则只移动jcode
- code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// 第一种不用存储的方法
Arrays.sort(nums);
int len = nums.length;
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < len; i++) {
// 跳过重复
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 双指针
int j = i + 1;
int k = len - 1;
while (j < k) {
if (nums[j] + nums[k] + nums[i] == 0) {
List<Integer> temp = new ArrayList<>();
res.add(Arrays.asList(nums[i], nums[j], nums[k]));
while (j < k && nums[j] == nums[j + 1])
j++;
while (j < k && nums[k] == nums[k - 1])
k--;
j++;
k--;
} else if (nums[j] + nums[k] + nums[i] > 0) {
k--;
} else if (nums[j] + nums[k] + nums[i] < 0) {
j++;
}
}
}
return res;
}
}
第三种是排序+哈希表方法
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// 排序 + 哈希表法
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
int len = nums.length;
for (int i = 0; i < len; i++) {
if (i > 0 && nums[i - 1] == nums[i]) {
continue;
}
Set<Integer> set = new HashSet<>();
for (int j = i + 1; j < len; j++) {
int target = -nums[i] - nums[j];
if (set.contains(target)) {
res.add(Arrays.asList(nums[i], nums[j], target));
while (j < len - 1 && nums[j] == nums[j + 1]) {
j++;
}
}
set.add(nums[j]);
}
}
return res;
}
}
Contains Duplicate
hastset 方法
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public boolean containsDuplicate(int[] nums) {
// 最直觉的，变成set，然后比长度
// 复杂度: 时间复杂度O(n) 空间复杂度O(n)
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (set.contains(nums[i])) {
return true;
}
set.add(nums[i]);
}
return false;
}
}
排序方法
code
1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public boolean containsDuplicate(int[] nums) {
// 另外一个直觉的，排序然后比较相邻的两个是否相同
Arrays.sort(nums);
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] == nums[i + 1]) {
return true;
}
}
return false;
}
}
Product of Array Except Self
这道题目更像一道数学题，不是单纯的数组题。要求时间复杂度是 O(n)的话，那么必须在空间上作出妥协
- code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
public int[] productExceptSelf(int[] nums) {
// 数学题，要求时间O(n)，那么必定在空间妥协
int[] leftProduct = new int[nums.length];
int[] rightProduct = new int[nums.length];
Arrays.fill(leftProduct, 1);
Arrays.fill(rightProduct, 1);
for (int i = 1; i < nums.length; i++) {
leftProduct[i] = leftProduct[i - 1] * nums[i - 1];
}
for (int i = nums.length - 2; i >= 0; i--) {
rightProduct[i] = rightProduct[i + 1] * nums[i + 1];
}
for (int i = 0; i < nums.length; i++) {
nums[i] = leftProduct[i] * rightProduct[i];
}
return nums;
}
}
Binary
前提知识
- Sum of Two Integers
- Bitwise operation
- 与 AND、或 OR、异或 XOR、非 NOT
- 与 AND:
&两真为真 - 或 OR:
||一真为真 - 异或 XOR:
^相异为真 - 非 NOT:
~取反
- 与 AND:
- 左移
<<、右移>>
- 与 AND、或 OR、异或 XOR、非 NOT
- Bitwise operation
题目
Number of 1 Bits 位 1 的个数
位运算最经典的问题，对于 Java 来说要使用「无符号右移」，如果使用
>>，负数的话有可能是无限循环code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
// 经典位运算
// 步骤：和1做与运算，然后左移
int count = 0;
while (n != 0) {
int flag = n & 1;
if (flag == 1) {
count++;
}
n = n >>> 1;
}
return count;
}
}
Reverse Bits 颠倒二进制位
这个不是非运算，是类似反转链表或者反转字符串那种
依照与反转字符串，比如我们需要将
hello反转为olleh，只不过该二进制是 32 位的，例子为**10110** 反转为**01101**第一步创建一个空数字来存储结果
res = 00000第二步，进行取数，取出原数字的最低位（最右边）然后添加到
res中，并将 res 左移 1 位，原数字右移一位取数是用与运算
&，即原数字和1相与，结果为000001
2
310110
& 00001
00000然后将其与 res 做或
|运算，结果存储到 res1
2
300000
| 00000
00000res 向左移一位：
000000原数字右移一位：
01011
重复，第二步的演练为
- 取数
1
2
301011
& 00001
10001b. 做或运算：注意或运算一真为一
1
2
3000000
| 001011
001011c. res 向左移一位：
010110d. 原数字右移：
00101
code
1
2
3
4
5
6
7
8
9
10
11
12public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int n) {
int res = 0;
for (int i = 0; i < 32; i++) {
res = res << 1;
res = res | (n & 1);
n = n >>> 1;
}
return res;
}
}
Missing Number 丢失的数字
直观的解法就是排序然后遍历，时间复杂度为 O(n)
- code
1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public int missingNumber(int[] nums) {
// 直观: 排序然后遍历
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (i != nums[i]) {
return i;
}
}
return nums.length;
}
}异或运算
这里要根据异或运算的特性来看，异或运算是“相异为真”
有两个特性：
- 任何数和 0 异或是它本身
- 任何数和它本身做异或，结果是 0
利用这个特性来做这道题目
code
1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public int missingNumber(int[] nums) {
int res = nums.length;
for (int i = 0; i < nums.length; i++) {
res = res ^ nums[i];
}
for (int i = 0; i < nums.length; i++) {
res = res ^ i;
}
return res;
}
}
Sum of Two Integers 两整数之和
不允许使用
+ -的话，那么使用位运算来模拟这个过程。code
1
2
3
4
5
6
7
8
9
10class Solution {
public int getSum(int a, int b) {
while (b != 0) {
int carray = (a & b) << 1;
a = a ^ b;
b = carray;
}
return a;
}
}
Counting Bits 比特位计数
最直观的做法是，对每个数进行和 1 相与然后输出 count，并将每个 count 保存在数组中
- code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public int[] countBits(int n) {
// 直观的做法
int[] res = new int[n + 1];
for (int i = 0; i < n + 1; i++) {
int count = 0;
int temp = i;
while (temp != 0) {
if ((temp & 1) == 1) {
count++;
}
temp >>>= 1;
}
res[i] = count;
}
return res;
}
}第二种动态规划，因为是数字的范围是
[0,n]，所以每个位上的结果具有连续性，这时候可以考虑结果之间的关系。对于任何数字 x，将其右移一位得到的数字 y（即 y = x / 2），y 中 1 的个数一定小于或等于 x 中 1 的个数。因为右移一位相当于除以 2，这可能会导致一个最低位的 1 被移除。
如果 x 是偶数，那么 x 和 y 中 1 的个数是相同的；如果 x 是奇数，那么 x 中 1 的个数比 y 多一个（因为最低位的 1 被移除了）。
所以动态规划的状态转移方程：
1
res[i] = res[i >> 1] + (i & 1)
code
1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public int[] countBits(int n) {
// 第二种是动态规划
// 状态转移方程： res[0] = 0, res[1] = 1
// res[i] = res[i >> 1] + (i & 1)
int[] res = new int[n + 1];
for (int i = 1; i < n + 1; i++) {
res[i] = res[i >> 1] + (i & 1);
}
return res;
}
}
第三种方法是 Brian Kernighan 算法（由 ChatGPT 生成）
它可以用来优化位计数（Counting Bits）的问题。这种方法的核心在于迭代地清除数字最右边的 1，直至数字变为 0，过程中计数增加。这种方法的优势在于它直接跳过了数字中的 0 位，只关注 1 位。
Brian Kernighan 算法的基本原理是：对于任意整数 x，x & (x - 1) 总是能够去掉 x 最右边的 1（即将最右边的 1 变为 0）。重复这个操作，直到 x 变为 0，操作的次数就是 x 中 1 的个数。
这种方法相比直接逐位检查效率更高，特别是对于包含大量 0 的数字。其时间复杂度为 O(nk)，其中 k 表示数字中 1 的个数，通常情况下 k 远小于数字的位数。
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public int[] countBits(int n) {
int[] res = new int[n + 1];
for (int i = 0; i <= n; i++) {
res[i] = countOnes(i);
}
return res;
}
private int countOnes(int x) {
int count = 0;
while (x != 0) {
x = x & (x - 1);
count++;
}
return count;
}
}
Dynamic Programming
- Climbing Stairs
Graph
Interval
Linked List
Reverse a Linked List ✅
两种解法
迭代
- 迭代比较容易理解，弄清楚当前节点
cur，当前节点的前一个节点pre，当前节点的下一个节点next，三者的指向关系就好了 cur是定义中的head，需要定义 pre 作为前一个指针，初始化为null，next作为临时变量来存当前指针的下一个节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
// 边界情况
if (head == null || head.next == null) {
return head;
}
ListNode pre = null;
// 遍历
while (head != null) {
// pre -> cur -> next
// pre <- cur <- next
// step1 先保存next节点
ListNode next = head.next;
// step2 反转当前节点的指针
head.next = pre;
// step3 移动pre和head指针
pre = head;
head = next;
}
return pre;
}
}- 迭代比较容易理解，弄清楚当前节点
递归
递归在我看来非常难以理解，非常抽象，我们都知道递归是将问题划分为一个非常小的问题
递归写法的几个部分：
- 递归终止条件：什么时候退出递归调用
- 递归的核心操作：进行每一次递归调用内的操作
- 返回值
函数签名
1
public class reveseList(ListNode head){}
下面说一下我自己的理解
首先「终止条件」是传入的当前节点为
null或者当前节点的下一个节点为nul即只有一个节点；递归核心部分
递归步骤，比如要反转的链表是
[1 -> 2 -> 3 -> 4 -> 5]当前head节点在1需要做的是递归调用反转 2 到 5 的部分，这部分递归调用实现reveseList(head.next)递归核心，反转当前节点与下一个节点的连接，当递归调用到链表结尾时，开始返回，此时返回的每一层递归都有一个节点。在返回的过程中，将当前节点的下一个节点的下一个节点指向自己，当前节点的下一个节点指向
null，比如节点 4，它的下一个节点是 5，此时 4 的下一个节点的下一个节点需要指向 4，4 的下一个节点指向null递归调用的返回是反转后的头节点（因为递归的每一部分是解决当前的小问题）
code
1
2
3
4
5
6
7
8
9
10
11
12
public ListNode reverseList(ListNode head) {
// 边界情况
if (head == null || head.next == null) {
return head;
}
ListNode nextHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return nextHead;
}
}
Detect Cycle in a Linked List ✅
快慢指针法，一开始想到的就是快慢指针。需要注意遍历跳出的时间
- code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null){
return false;
}
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(fast == slow){
return true;
}
}
return false;
}
}哈希表法
- code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15public class Solution {
public boolean hasCycle(ListNode head) {
// 哈希表法
Set set = new HashSet<ListNode>();
while (head != null) {
if (set.contains(head)) {
return true;
} else {
set.add(head);
}
head = head.next;
}
return false;
}
}
Merge Two Sorted Lists ✅
题目标定是简单的，但是以我的经验来看也不容易写对。
思路：两个链表是有序的，将这两个合并成一个链表，那么不需要新建节点，只需改变节点的指向。
方便处理，需要设置一个哨兵节点，然后当前节点指向哨兵节点；进行比较操作，如果
list1 ≤ list2的值，那么当前节点的下一个指向list1，分别将当前节点和list1向前推进一个节点。重复这个步骤，直到一方的节点为null，由于遍历时list1和list2的节点都在逐步向前推进，那么此时只需将不为空的链表拼接到当前节点的后面。code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummyNode = new ListNode();
ListNode cur = dummyNode;
while(list1 != null && list2 != null){
if(list1.val <= list2.val){
cur.next = list1;
list1 = list1.next;
cur = cur.next;
}else{
cur.next = list2;
list2 = list2.next;
cur = cur.next;
}
}
if(list1 == null){
cur.next = list2;
}else{
cur.next = list1;
}
return dummyNode.next;
}
}
Remove Nth Node From End Of List
两次遍历
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//第一遍遍历，确定链表长度
int len = 0;
ListNode node = head;
while(node != null){
node = node.next;
len++;
}
if(len == n){
return head.next;
}
//删除倒数第N个节点
ListNode node2 = head;
for(int i = 0;i < len - n - 1;i++){
node2 = node2.next;
}
node2.next = node2.next.next;
return head;
}
}
一次遍历
要在一次遍历中删除倒数第 N 个节点，可以采用快慢双指针的写法，fast 比 slow 先走 N 步，然后 slow 再开始走，当
fast走到链表末尾时，slow刚好走到 N 的前一个节点。这里有两个需要注意的点：- 为了方便处理删除头节点的情况，使用虚拟头节点
dummy - 不要在循环中进行交换，循环只是为了遍历
- 为了方便处理删除头节点的情况，使用虚拟头节点
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//双指针遍历
//fast先走n步，然后slow开始走，等fast到结尾时，slow走了len - n 步，刚好是倒数第N个节点
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy;
ListNode slow = dummy;
for(int i = 0;i <= n;i++){
fast = fast.next;
}
while(fast != null){
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return head;
}
}
Reorder List
这个题目非常综合性，考察到了反转链表，合并两个链表，以及找到中间节点的方法（好用的是快慢指针）
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48class Solution {
public void reorderList(ListNode head) {
// 先反转链表后半段，然后再连接🤔
// 获取链表长度
int len = 0;
ListNode lenNode = head;
while (lenNode != null) {
lenNode = lenNode.next;
len++;
}
// 找到中间节点
ListNode halfNode = head;
for (int i = 0; i < len / 2; i++) {
halfNode = halfNode.next;
}
// 断开
ListNode secondHalfHead = halfNode.next;
halfNode.next = null;
ListNode secondHalf = reverseList(secondHalfHead);
ListNode fristHalf = head;
while (fristHalf != null && secondHalf != null) {
ListNode temp1 = fristHalf.next;
ListNode temp2 = secondHalf.next;
fristHalf.next = secondHalf;
secondHalf.next = temp1;
fristHalf = temp1;
secondHalf = temp2;
}
}
// 反转链表
private ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}使用快慢双指针找到中间节点，并断开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43class Solution {
public void reorderList(ListNode head) {
// 先反转链表后半段，然后再连接🤔
// 快慢指针找到中间节点
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 断开
ListNode secondHalfHead = slow.next;
slow.next = null;
ListNode secondHalf = reverseList(secondHalfHead);
ListNode fristHalf = head;
while (fristHalf != null && secondHalf != null) {
ListNode temp1 = fristHalf.next;
ListNode temp2 = secondHalf.next;
fristHalf.next = secondHalf;
secondHalf.next = temp1;
fristHalf = temp1;
secondHalf = temp2;
}
}
// 反转链表
private ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
Matrix
String
Tree
重新用自己的话整理了一遍：二叉树-基本概念
基本面试考到的就是二叉树的遍历了，所以很多题目从二叉树的前中后序遍历以及层序遍历上考虑。
Maximum Depth of Binary Tree 二叉树的最大深度
这道题很直观的想到使用二叉树的层序遍历，但是具体来说，需要变种下，要遍历完一层的节点
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution {
public int maxDepth(TreeNode root) {
// 层序遍历
if (root == null) {
return 0;
}
int res = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode tmp = queue.poll();
if (tmp.left != null) {
queue.offer(tmp.left);
}
if (tmp.right != null) {
queue.offer(tmp.right);
}
}
res++;
}
return res;
}
}第二种是后序遍历
1
2
3
4
5
6
7
8
9class Solution {
public int maxDepth(TreeNode root) {
if (root == null)
return 0;
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Integer.max(leftDepth, rightDepth) + 1;
}
}
Binary Tree Level Order Traversal 二叉树的层序遍历
很简单的层序遍历，但有不同，这个是需要把每层的结果从左到右存起来，跟二叉树的最大深度差不多
- code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null){
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> temp = new ArrayList<>();
for(int i = 0;i < size;i++){
TreeNode node = queue.poll();
temp.add(node.val);
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
}
res.add(temp);
}
return res;
}
}
Validate Binary Search Tree 验证二叉搜索树
很直观的做法，二叉搜索树的中序遍历是有顺序的数组
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public boolean isValidBST(TreeNode root) {
//很直观的二叉搜索树，中序遍历是排好序的
List<Integer> list = new ArrayList<>();
inOrder(root,list);
for(int i = 1;i < list.size();i++){
if(list.get(i) <= list.get(i - 1)){
return false;
}
}
return true;
}
private void inOrder(TreeNode node, List<Integer> list){
if(node == null) return;
inOrder(node.left,list);
list.add(node.val);
inOrder(node.right,list);
}
}
第二种做法，不需要 O(n)的空间复杂度
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution {
private TreeNode prev = null;
public boolean isValidBST(TreeNode root) {
return inOrder(root);
}
private boolean inOrder(TreeNode node){
if(node == null) return true;
if(!inOrder(node.left)) return false;
if(prev != null && prev.val >= node.val) return false;
prev = node;
return inOrder(node.right);
}
}
Binary Tree Zigzag Level Order Traversal 二叉树的锯齿形层序遍历
这道题目是对层序遍历的延伸，Z 字形打印需要弄清楚在那里翻转
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
boolean leftToRight = true;
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> temp = new LinkedList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (leftToRight) {
temp.addLast(node.val);
} else {
temp.addFirst(node.val);
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
res.add(temp);
leftToRight = !leftToRight;
}
return res;
}
}
Kth Smallest Element in a BST 二叉搜索树中第 K 小的元素
非常经典的 TopK 问题啦，这个最直观的解法就是中序遍历存到列表中然后返回，这样的时空复杂度都是 O(n)
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
List<Integer> list;
public int kthSmallest(TreeNode root, int k) {
// 暴力解法： 中序遍历，然后返回
list = new ArrayList<>();
inOrder(root);
return list.get(k - 1);
}
private void inOrder(TreeNode node) {
if (node == null)
return;
inOrder(node.left);
list.add(node.val);
inOrder(node.right);
}
}
还有一个是提前终止的方法，另外不使用数组存储结果。
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
int res = 0;
int count = 0;
public int kthSmallest(TreeNode root, int k) {
// 提前终止的方法
inOrder(root, k);
return res;
}
void inOrder(TreeNode node, int k) {
if (node == null)
return;
inOrder(node.left, k);
count++;
if (count == k) {
res = node.val;
return;
}
inOrder(node.right, k);
}
}
Same Tree 相同的树
这道题目是递归题目，比较两颗树是否相同，用逆向思维，只要确认不同的情况有哪些就好了
code
1
2
3
4
5
6
7
8
9
10
11
12public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null)
return true;
if (p == null || q == null)
return false;
if (p.val != q.val)
return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
Heap
其他题型的补充
Sort
Insertion sort
147. 对链表进行插入排序
重点是理解插入排序的思想，以及往正确位置插入的方法
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27class Solution {
public ListNode insertionSortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode lastSorted = head, cur = head.next;
while (cur != null) {
if (lastSorted.val < cur.val) {
lastSorted = lastSorted.next;
} else {
ListNode prev = dummy;
while (prev.next.val < cur.val) {
prev = prev.next;
}
// 插入
lastSorted.next = cur.next;
cur.next = prev.next;
prev.next = cur;
}
cur = lastSorted.next;
}
return dummy.next;
}
}
题单
另外 k 神的 88 题也不错，当然有重复的。
参考
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 既往不恋！
wechat
alipay
评论
WalineGitalk