AlgorithmClassfication3

Article Directory
  1. 1.
    1. 1.1. 109. 有序链表转换二叉搜索树
    2. 1.2. 144. 二叉树的前序遍历
    3. 1.3. 94. 二叉树的中序遍历
    4. 1.4. 145. 二叉树的后序遍历
    5. 1.5. 107. 二叉树的层序遍历 II
    6. 1.6. 230. 二叉搜索树中第K小的元素
    7. 1.7. 240. 搜索二维矩阵 II
    8. 1.8. 297. 二叉树的序列化与反序列化
    9. 1.9. 437. 路径总和 III
      1. 1.9.1. 注意:从该节点往下的路径和
    10. 1.10. 450. 删除二叉搜索树中的节点
    11. 1.11. 563. 二叉树的坡度
      1. 1.11.1. 注意:前缀和,高度;从叶子到该节点和
    12. 1.12. 124. 二叉树中的最大路径和
    13. 1.13. 124. 二叉树中的最大路径和
    14. 1.14. 606. 根据二叉树创建字符串
    15. 1.15. 653. 两数之和 IV - 输入 BST
    16. 1.16. 783. 二叉搜索树节点最小距离
    17. 1.17. 938. 二叉搜索树的范围和
    18. 1.18. 965. 单值二叉树
    19. 1.19. 993. 二叉树的堂兄弟节点
    20. 1.20. 105. 从前序与中序遍历序列构造二叉树
    21. 1.21. 662. 二叉树最大宽度
    22. 1.22. 998. 最大二叉树 II
    23. 1.23. 二叉树的下一个结点
    24. 1.24. 863. 二叉树中所有距离为 K 的结点
    25. 1.25. 987. 二叉树的垂序遍历
    26. 1.26. 96. 不同的二叉搜索树
    27. 1.27. 95. 不同的二叉搜索树 II
    28. 1.28. 98. 验证二叉搜索树
  2. 2. 原地哈希
    1. 2.1. 442. 数组中重复的数据
  3. 3. 优先队列、单调队列、treeset、treemap
    1. 3.1. 1675. 数组的最小偏移量
    2. 3.2. 1438. 绝对差不超过限制的最长连续子数组
    3. 3.3. 队列和栈的相互实现
      1. 3.3.1. 两个栈实现队列
      2. 3.3.2. 两个队列实现栈
    4. 3.4. 641. 设计循环双端队列
  4. 4. 并查集
    1. 4.1. 题1
    2. 4.2. 股票推荐
      1. 4.2.1. 题目
      2. 4.2.2. 输入
    3. 4.3. 1631. 最小体力消耗路径
      1. 4.3.1. 并查集 + Kruskal
    4. 4.4. 947. 移除最多的同行或同列石头

AlgorithmClassfication3

109. 有序链表转换二叉搜索树

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
class Solution {
public TreeNode sortedListToBST(ListNode head) {
return dfs(head, null);
}

// 不包括tail
public ListNode getMid(ListNode head, ListNode tail) {
ListNode slow = head, fast = head;

while (fast != tail && fast.next != tail) {
slow = slow.next;
fast = fast.next.next;
}

return slow;
}

// 不包括tail
public TreeNode dfs(ListNode head, ListNode tail) {
if (head == tail) {
return null;
}
// if (head.next == tail) {
// return new TreeNode(head.val);
// }

ListNode mid = getMid(head, tail);
TreeNode node = new TreeNode(mid.val);

node.left = dfs(head, mid);
node.right = dfs(mid.next, tail);

return node;
}
}

144. 二叉树的前序遍历

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
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
Deque<TreeNode> stack = new ArrayDeque<>();
List<Integer> ans = new ArrayList<>();

if (root == null) {
return ans;
}

stack.offerLast(root);
while (!stack.isEmpty()) {
TreeNode tempNode = stack.pollLast();
ans.add(tempNode.val);

if (tempNode.right != null) {
stack.offerLast(tempNode.right);
}
if (tempNode.left != null) {
stack.offerLast(tempNode.left);
}
}

return ans;
}
}

94. 二叉树的中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
Deque<TreeNode> stack = new ArrayDeque<>();
List<Integer> ans = new ArrayList<>();

if (root == null) {
return ans;
}

while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.offerLast(root);
root = root.left;
}

root = stack.pollLast();
ans.add(root.val);
root = root.right;
}

return ans;
}
}

145. 二叉树的后序遍历

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
48
49
50
51
52
53
54
55
56
57
58
// 方案一,与中序遍历类似
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if (root == null) {
return ans;
}

// 与中序遍历类似
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode prev = null; // 表示上一个被访问到的,因为左右中,所以中间的右边遍历完成才能访问中间
while (!stack.isEmpty() || root != null) {
while (root != null) {
stack.offerLast(root);
root = root.left;
}

root = stack.pollLast();
// 因为左右中,所以有节点不存在,或者有节点是上一个已经访问过了,那么可以访问这个中间节点
if (root.right == null || root.right == prev) {
ans.add(root.val);
prev = root;
root = null; // 注意需要root=null,来取出stack中下面一个
} else {
stack.offerLast(root);
root = root.right; // 右节点存在,并且没有访问过
}
}

return ans;
}
}

// 方法二,与前序遍历类似
// 前序遍历的过程 是 中左右。
// 将其转化成 中右左(就是类似前序遍历,不过这里是遍历中右左,然后反过来打印即可)。也就是压栈的过程中优先压入左子树,在压入右子树。需要两个栈
// 然后将这个结果返回来,这里是利用栈的先进后出倒序打印。
public static void postOrderIteration(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
stack1.push(root);
while (!stack1.isEmpty()) {
TreeNode tempNode = stack1.pop();
stack2.push(tempNode);
if (tempNode.left != null) {
stack1.push(tempNode.left);
}
if (tempNode.right != null) {
stack1.push(tempNode.right);
}
}
while (!stack2.isEmpty()) {
System.out.print(stack2.pop().value + " ");
}
}

107. 二叉树的层序遍历 II

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
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) {
return ans;
}

// 层序遍历,结果使用头插
Deque<TreeNode> queue = new ArrayDeque<>();

queue.offerLast(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> list = new ArrayList<>();

for (int i=0; i<size; i++) {
TreeNode tempNode = queue.pollFirst();
list.add(tempNode.val);
if(tempNode.left != null) {
queue.offerLast(tempNode.left);
}
if (tempNode.right != null) {
queue.offerLast(tempNode.right);
}
}

ans.add(0, list); // 头插
}

return ans;
}
}

230. 二叉搜索树中第K小的元素

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
48
class Solution {
int num = 0, ans = 0;
public int kthSmallest(TreeNode root, int k) {
searchK(root, k);

return ans;
}

public void searchK(TreeNode node, int k) {
if (node == null) { return; }

searchK(node.left, k);
if (++num == k) {
ans = node.val;
return;
}
searchK(node.right, k);
}
}

// 迭代
class Solution {
/**
* 使用栈进行迭代中序遍历,这样就没有递归中序遍历的全局变量了
* @param root
* @param k
* @return
*/
public int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> stack = new ArrayDeque<>();

// 注意此处没有先加入节点这个操作,而是每次不断的把做节点加入
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.offerLast(root);
root = root.left;
}

root = stack.pollLast();
if (--k == 0) {
return root.val;
}
root = root.right;
}

return root.val;
}
}

240. 搜索二维矩阵 II

297. 二叉树的序列化与反序列化

437. 路径总和 III

路径 不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。

注意:从该节点往下的路径和

所以此处的参数还是写在里面的,而不是返回值里面

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
class Solution {
int ans = 0;
public int pathSum(TreeNode root, int targetSum) {

dfs1(root, targetSum);

return ans;
}

// 遍历所有的节点
public void dfs1(TreeNode node, int targetSum) {

if (node == null) {
return;
}

dfs2(node, targetSum, 0);
dfs1(node.left, targetSum);
dfs1(node.right, targetSum);
}

// 以该节点为跟节点的所有路径和
public void dfs2(TreeNode node, int targetSum, int val) {

if (node == null) {
return;
}

val += node.val;
if (val == targetSum) {
ans += 1;
}
dfs2(node.left, targetSum, val);
dfs2(node.right, targetSum, val);
}
}

450. 删除二叉搜索树中的节点

这道题目的做好好好注意一下,

比如拿到a的left指针node,如果给这个指针赋成别的地址,那么之前的a的left指针是没有变的,因为指向的是固定的地址(除非更改a的left值),而不是指针的指针。

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
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
// 注意,是二叉搜索树呀
// 首先找到,要被删除的节点
TreeNode node = root, nodePar = null;

while (node != null) {
if (key < node.val) {
nodePar = node;
node = node.left;
} else if (key > node.val) {
nodePar = node;
node = node.right;
} else {
break;
}
}

if (null == node) {
return root;
}

// 然后分类删除
if (node.left == null && node.right == null) {
node = null;
} else if (node.left == null) {
node = node.right;
} else if (node.right == null) {
node = node.left;
} else {
// 找出右边节点的最小节点,用它代替到该节点,然后删除
TreeNode succ = node.right, succPar = node;
while (succ.left != null) {
succPar = succ;
succ = succ.left;
}

// 然后将找到的后记节点succ放到node的位置,下面这个判断是succ就是node.right
if (node.right != succ) {
succPar.left = succ.right;
succ.left = node.left;
succ.right = node.right;
} else {
// 如果succ就是node.right,node没有左边节点,直接这样就行
succ.left = node.left;
}
node = succ;
}

if (nodePar == null) { // 被删除的是父节点
return node;
} else if (nodePar.left != null && nodePar.left.val == key) {
nodePar.left = node;
} else {
nodePar.right = node;
}

return root;
}
}

563. 二叉树的坡度

注意:前缀和,高度;从叶子到该节点和

求前缀和,高度等,是从上往下面求的,所以参数放在函数中即可,(求高度返回值里面也要有)。

但是求从底部叶子到顶部的和,需要将值放在返回值中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
int ans = 0;

public int findTilt(TreeNode root) {
dfs(root);

return ans;
}

public int dfs(TreeNode node) {
if (node == null) {
return 0;
}

int sumLeft = dfs(node.left);
int sumRight = dfs(node.right);

ans += Math.abs(sumRight - sumLeft);
return node.val + sumLeft + sumRight;
}
}

124. 二叉树中的最大路径和

这个也是从低向上,所以可以放在外面

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
class Solution {
int maxSum = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
maxGain(root);
return maxSum;
}

public int maxGain(TreeNode node) {
if (node == null) {
return 0;
}

// 递归计算左右子节点的最大贡献值
// 只有在最大贡献值大于 0 时,才会选取对应子节点
int leftGain = Math.max(maxGain(node.left), 0);
int rightGain = Math.max(maxGain(node.right), 0);

// 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
int priceNewpath = node.val + leftGain + rightGain;

// 更新答案
maxSum = Math.max(maxSum, priceNewpath);

// 返回节点的最大贡献值
return node.val + Math.max(leftGain, rightGain);
}
}

124. 二叉树中的最大路径和

606. 根据二叉树创建字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public String tree2str(TreeNode root) {
return dfs(root);
}

public String dfs(TreeNode node) {
if (node == null) {
return "";
}

if (node.left == null && node.right == null) {
return "" + node.val;
}
if (node.right == null) {
return node.val + "(" + dfs(node.left) + ")";
}
return node.val + "(" + dfs(node.left) + ")(" + dfs(node.right) + ")";
}
}

653. 两数之和 IV - 输入 BST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
Set<Integer> set = new HashSet<Integer>();

public boolean findTarget(TreeNode root, int k) {
return dfs(root, k);
}

public boolean dfs(TreeNode node, int k) {
if (node == null) {
return false;
}

if (set.contains(k - node.val)) {
return true;
}

set.add(node.val);
return dfs(node.left, k) || dfs(node.right, k);
}
}

783. 二叉搜索树节点最小距离

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
class Solution {
// 二叉搜索树,中序遍历的同时,检查一遍就好
TreeNode pre = null;
int ans = Integer.MAX_VALUE;
public int minDiffInBST(TreeNode root) {
dfs(root);

return ans;
}

public void dfs(TreeNode node) {
if (node == null) {
return;
}

dfs(node.left);

if (pre == null) {
pre = node;
} else {
ans = Math.min(Math.abs(node.val - pre.val), ans);
pre = node;
}

dfs(node.right);
}
}

938. 二叉搜索树的范围和

965. 单值二叉树

993. 二叉树的堂兄弟节点

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
class Solution {
int xDepth = -2;
int yDepth = -1;
TreeNode par = null;
int x, y;
boolean ans = false;

public boolean isCousins(TreeNode root, int x, int y) {
if (root.val == x || root.val == y) {
return false;
}
this.x = x; this.y = y;

dfs(root, 1, null);

return ans;
}

public void dfs(TreeNode node, int height, TreeNode parent) {
if (node == null) {
return;
}

if (node.val == x) {
xDepth = height;
if (par == null) {
par = parent;
} else {
if (xDepth == yDepth && par != parent) {
ans = true;
}
}
} else if (node.val == y) {
yDepth = height;
if (par == null) {
par = parent;
} else {
if (xDepth == yDepth && par != parent) {
ans = true;
}
}
}

dfs(node.left, height+1, node);
dfs(node.right, height+1, node);
}
}

105. 从前序与中序遍历序列构造二叉树

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
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return fenzhi(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
}

public TreeNode fenzhi(int[] preorder, int[] inorder, int proot, int pright, int ileft, int iright) {
if (!(proot <= pright && ileft <= iright)) {
return null;
}

// 前序遍历中的第一个节点就是根节点
int rootVal = preorder[proot];
TreeNode node = new TreeNode(rootVal);

// 找到新的区间,注意无重复元素
int nextIright = ileft;
// 当前在porder中左边第一个是根,然后我要去中序遍历中找到根,然后将他们分开,进行分治
while (nextIright < inorder.length && inorder[nextIright] != rootVal) {
nextIright += 1;
}

// nextIright - ileft就是左子树的节点数目
node.left = fenzhi(preorder, inorder, proot + 1, nextIright - ileft + proot, ileft, nextIright-1);
node.right = fenzhi(preorder, inorder, nextIright - ileft + proot + 1, pright, nextIright+1, iright);

return node;
}
}

662. 二叉树最大宽度

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
48
49
50
51
52
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
class Pair {
TreeNode node;
int index;

Pair(TreeNode node, int index) {
this.node = node;
this.index = index;
}
}

public int widthOfBinaryTree(TreeNode root) {
Deque<Pair> queue = new ArrayDeque<>();

queue.offerLast(new Pair(root, 0));
int ans = 1;

while (!queue.isEmpty()) {
int size = queue.size();

ans = Math.max(queue.peekLast().index - queue.peekFirst().index + 1, ans);

for (int i = 0; i < size; i++) {
Pair pair = queue.pollFirst();

if (pair.node.left != null) {
queue.offerLast(new Pair(pair.node.left, 2 * pair.index));
}
if (pair.node.right != null) {
queue.offerLast(new Pair(pair.node.right, 2 * pair.index + 1));
}
}
}

return ans;
}
}

998. 最大二叉树 II

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
/**
val放在nums的最后,那么val这个节点添加的时候
肯定是在树的右边
*/
public TreeNode insertIntoMaxTree(TreeNode root, int val) {
if (root == null) {
return null;
}

if (val > root.val) {
TreeNode newRoot = new TreeNode(val);
newRoot.left = root;
return newRoot;
}

TreeNode node = root;
TreeNode pre = null;
while (node != null && node.val > val) {
pre = node;
node = node.right;
}

TreeNode temp = new TreeNode(val);
temp.left = pre.right;
pre.right = temp;


return root;
}
}

二叉树的下一个结点

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
import java.util.*;
/*
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;

TreeLinkNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode) {
findNextInOrder(findRoot(pNode));


for (int i = 0; i < nodes.size(); i++) {
if (nodes.get(i) == pNode) {
if (i < nodes.size() - 1) {
return nodes.get(i + 1);
}

return null;
}
}

return null;
}

// 首先找出父亲节点
public TreeLinkNode findRoot(TreeLinkNode node) {
while (node.next != null) {
node = node.next;
}

return node;
}

List<TreeLinkNode> nodes = new ArrayList<>();
// 中序遍历找到下一个
public void findNextInOrder(TreeLinkNode node) {
if (node == null) {
return;
}

findNextInOrder(node.left);
nodes.add(node);
findNextInOrder(node.right);
}
}

// 方法二
/**
如果给出的结点有右子节点,则最终要返回的下一个结点即右子树的最左下的结点
如果给出的结点无右子节点,且当前结点是其父节点的左子节点,则返回其父节点
如果给出的结点无右子节点,且当前结点是其父节点的右子节点,则先要沿着左上方父节点爬树,一直爬到当前结点是其父节点的左子节点为止,返回的就是这个父节点;或者没有满足上述情况的则返回为NULL
**/

import java.util.*;
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode) {
// 情况一
if(pNode.right != null) {
TreeLinkNode rchild = pNode.right;
// 一直找到右子树的最左下的结点为返回值
while(rchild.left != null) rchild = rchild.left;
return rchild;
}

// 情况二
if(pNode.next != null && pNode.next.left == pNode) {
return pNode.next;
}

// 情况三
if(pNode.next != null) {
TreeLinkNode ppar = pNode.next;
// 沿着左上一直爬树,爬到当前结点是其父节点的左自己结点为止
while(ppar.next != null && ppar.next.right == ppar) ppar = ppar.next;
return ppar.next;
}
return null;
}
}

863. 二叉树中所有距离为 K 的结点

根据这棵树,建图
1 使用map直接索引到父亲节点,这样就能根图一样做了
2.1 使用邻接表来做,数组+链表
2.2 使用邻接表,链式星向图

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
/**
根据这棵树,建图
1 使用map直接索引到父亲节点,这样就能根图一样做了
2.1 使用邻接表来做,数组+链表
2.2 使用邻接表,链式星向图

感觉以后自己做还是首选1,其次2.1
*/
int N = 501; // 节点最多这么点
int M = N * 4; // 每一个节点两条边,所以边的总数为4
int idx = 0; // 边的编号
int[] head = new int[N];
Edge[] g = new Edge[M];
class Edge {
int u, v, next;
}

public void add(int u, int v) {
g[idx].u = u;
g[idx].v = v;
g[idx].next = head[u];
head[u] = idx++; // head,表示以u为节点的边的个数,一条条串联起来
}

public void buildTree(TreeNode node) {
if (node == null) {
return;
}

if (node.left != null) {
add(node.val, node.left.val);
add(node.left.val, node.val);
buildTree(node.left);
}
if (node.right != null) {
add(node.val, node.right.val);
add(node.right.val, node.val);
buildTree(node.right);
}
}

boolean[] visited = new boolean[N];
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
List<Integer> ans = new ArrayList<>();
Arrays.fill(head, -1);
for (int i = 0; i < M; i++) {
g[i] = new Edge();
}
buildTree(root);

// 使用BFS查找,以target为源
int depth = 0;
Deque<Integer> queue = new ArrayDeque<>();
queue.offerLast(target.val);
visited[target.val] = true;

while (!queue.isEmpty()) {
if (depth == k) {
while (!queue.isEmpty()) {
ans.add(queue.pollFirst());
}
break;
}

int size = queue.size();
for (int i = 0; i < size; i++) {
int node = queue.pollFirst();

// 层次遍历的时候,首先找到以该节点为头,得到的所有边
for (int j = head[node]; j != -1; j = g[j].next) {
// 判断来的那个节点不能被访问了
if (!visited[g[j].v]) {
queue.offerLast(g[j].v);
visited[g[j].v] = true;
}
}
}
depth += 1;
}

return ans;
}
}

987. 二叉树的垂序遍历

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
// 得用层序遍历吧
class TNode extends TreeNode {
int[] loc;
int ceng;

TNode(TreeNode node, int[] loc, int ceng) {
super(node.val, node.left, node.right);
this.loc = loc;
this.ceng = ceng;
}
}

public List<List<Integer>> verticalTraversal(TreeNode root) {
Deque<TNode> queue = new ArrayDeque<>();
// 1000,最多10层,列的个数最多-512~512
// 0 + 1000的偏移
List<TNode> all = new ArrayList<>();

int ceng = 1;
queue.offerLast(new TNode(root, new int[]{0, 0}, ceng));
while (!queue.isEmpty()) {
int size = queue.size();
ceng += 1;

for (int i = 0; i < size; i++) {
TNode tNode = queue.pollFirst();
int[] loc = tNode.loc;

all.add(tNode);

if (tNode.left != null) {
queue.offerLast(new TNode(tNode.left, new int[]{loc[0]+1, loc[1]-1}, ceng));
}
if (tNode.right != null) {
queue.offerLast(new TNode(tNode.right, new int[]{loc[0]+1, loc[1]+1}, ceng));
}
}

}

// 先按照列,在按照行,在按照数值
Collections.sort(all, (a, b) -> {
if (a.loc[1] != b.loc[1]) {
return a.loc[1] - b.loc[1];
} else if (a.loc[0] != b.loc[0]) {
return a.loc[0] - b.loc[0];
}
return a.val - b.val;
});

List<List<Integer>> ans = new ArrayList<>();
List<Integer> list = new ArrayList<>();
list.add(all.get(0).val);
ans.add(list);
for (int i = 1; i < all.size(); i++) {
if (all.get(i-1).loc[1] == all.get(i).loc[1]) {
ans.get(ans.size()-1).add(all.get(i).val);
} else {
List<Integer> list1 = new ArrayList<>();
list1.add(all.get(i).val);
ans.add(list1);
}
}

return ans;
}
}

96. 不同的二叉搜索树

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
class Solution {
// 记忆化搜索
int[][] mem;
public int numTrees(int n) {
mem = new int[n+1][n+1];
return dfs(1, n);
}

public int dfs(int left, int right) {
if (left >= right) { // 注意,此处
return 1;
}

if (mem[left][right] != 0) {
return mem[left][right];
}

int ans = 0;
for (int i = left; i <= right; i++) {
int leftAns = dfs(left, i - 1);
int rightAns = dfs(i + 1, right);

ans += leftAns * rightAns;
}
mem[left][right] = ans;

return ans;
}
}

95. 不同的二叉搜索树 II

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
48
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<TreeNode> generateTrees(int n) {
List<TreeNode> ans = new ArrayList<>();

return dfs(0, n-1);
}

public List<TreeNode> dfs(int left, int right) {
List<TreeNode> ans = new ArrayList<>();
if (left > right) {
ans.add(null);
return ans;
}

List<TreeNode> nodes = new ArrayList<>();
for (int i = left; i <= right; i++) {
List<TreeNode> leftNodes = dfs(left, i-1);
List<TreeNode> rightNodes = dfs(i+1, right);

for (TreeNode leftNode: leftNodes) {
for (TreeNode rightNode: rightNodes) {
TreeNode node = new TreeNode(i+1);
node.left = leftNode;
node.right = rightNode;
ans.add(node);
}
}
}

return ans;

}
}

98. 验证二叉搜索树

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
class Solution {
public boolean isValidBST(TreeNode root) {
return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

public boolean valid(TreeNode node, long lower, long upper) {
if (node == null) {
return true;
}

if (!(node.val > lower && node.val < upper)) {
return false;
}

return valid(node.left, lower, node.val) && valid(node.right, node.val, upper);
}
}

class Solution {
// 使用中序遍历的思路
public boolean isValidBST(TreeNode root) {
Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
Long pre = Long.MIN_VALUE;

while (!stack.isEmpty() || root != null) {
while (root != null) {
stack.offerLast(root);
root = root.left;
}

root = stack.pollLast();
if (root.val <= pre) {
return false;
}
pre = (long)root.val;
root = root.right;
}

return true;
}
}

原地哈希

442. 数组中重复的数据

看数组中数据的范围,1 <= nums[i] <= n,而且时间复杂度O(n),空间复杂度常量级别,所以肯定要用到原地哈希。

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
class Solution {
/**
原地哈希
然后numx[i]放到nums[i]-1的位置
*/
public List<Integer> findDuplicates(int[] nums) {
List<Integer> ans = new ArrayList<>();

// 注意,需要两遍,第一遍换到
for (int i=0; i<nums.length; i++) {
// 这是代表已经放在该放的地方了
if (nums[i] < 0 || nums[i]-1 == i) { continue; }
if (nums[nums[i]-1] == nums[i]) {
ans.add(nums[i]);
nums[i] = -1 * nums[i]; // 为了防止重复计算
} else {
int temp = nums[nums[i]-1];
nums[nums[i]-1] = nums[i];
nums[i] = temp;
i--; // 注意这里要i--,因为nums[nums[i]-1]放了现在的nums[i],但是被换过来的这个没有验证
}
}

return ans;
}
}


// 方法2
class Solution {
public List<Integer> findDuplicates(int[] nums) {
int n = nums.length;
List<Integer> ans = new ArrayList<Integer>();
for (int i = 0; i < n; ++i) {
int x = Math.abs(nums[i]);
if (nums[x - 1] > 0) {
nums[x - 1] = -nums[x - 1];
} else {
ans.add(x);
}
}
return ans;
}
}

优先队列、单调队列、treeset、treemap

Java中的栈Stack、Deque、ArrayDeque、LinkedList

ArrayDeque用作栈时比Stack快没有疑问,用作队列的时候似乎也会比LinkedList快!

找到题眼,有任意两个元素之间的绝对差,那肯定是最大值,最小值。

优先队列,跟只用一个变量来维护最大最小值的区别就是:如果删除这个最大的,还能知道下一个最大的,而变量维护的不行了,只能添加得来。

treesetpriorityqueue

1675. 数组的最小偏移量

此处其实用treeset更快。

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
class Solution {
public int minimumDeviation(int[] nums) {
// 使用优先队列,或者使用treeset
// treeset的话可以拿到最大值和最小值
// 而优先队列的话只能拿到一个,此处用最大堆,然后维护最小值
// 先把技术全部*2变成偶数,放入最大堆,然后每次将最大值/2放入,若最大值是奇数,终止

// 最大堆
PriorityQueue<Integer> queue = new PriorityQueue<Integer>((a, b) -> b - a);

int ans = Integer.MAX_VALUE, min = Integer.MAX_VALUE;

for (int num: nums) {
int temp = num % 2 == 1 ? num * 2 : num;
queue.offer(temp);
min = Math.min(temp, min);
}

while (true) {
int max = queue.poll();
ans = Math.min(ans, max - min);

if (max % 2 == 1) { break; } // 若最大值是奇数,终止

int temp = max / 2;
min = Math.min(temp, min);
queue.offer(temp);
}

return ans;
}
}

1438. 绝对差不超过限制的最长连续子数组

还是treemap好用啊,单调队列稍微有点麻烦

注意,这个set不能重复,那么可以用map的值来记录个数,这个思想要记住。

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
class Solution {
public int longestSubarray(int[] nums, int limit) {
// 子数组的任意两个元素之间的绝对值差小于等于limitlimit,经典滑动窗口
// 如何维护最大值和最小值,用treeset吧,但是treeset不能重复啊
// 那可以用treemap啊,值就放他的个数,如果个数为0,需要remove
// 用单调队列维护起来稍微麻烦一点,感觉还是treemap好

TreeMap<Integer, Integer> treeMap = new TreeMap<>();
int left = 0, ans = 0;

for (int right = 0; right < nums.length; right++) {
treeMap.put(nums[right], treeMap.getOrDefault(nums[right], 0) + 1);

while (left < right && treeMap.lastKey() - treeMap.firstKey() > limit) {
treeMap.put(nums[left], treeMap.get(nums[left]) - 1);
if (treeMap.get(nums[left]) == 0) {
treeMap.remove(nums[left]);
}
left += 1;
}

ans = Math.max(ans, right - left + 1);
}

return ans;
}
}

队列和栈的相互实现

两个栈实现队列

如果需要弹出队头元素,则将 stack1 中的元素弹出并 push 到 stack2 中,再将 stack2 的栈顶元素弹出,即弹出来队头的元素。

如果 stack2 中非空,再在队尾添加元素的时候仍然添加到 stack1 中,再从 stack2 中弹出队头元素。

如果 stack2 为空,弹出队头元素才需要将 stack1 中的元素转移到 stack2 中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if (stack2.size() == 0) {
while (stack1.size() > 0) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}

两个队列实现栈

两个队列实现栈,弹出元素的时候,把队列中的元素放到另一个队列中,删除最后一个元素。

两个队列始终保持只有一个队列是有数据的。

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
class Solution {
Queue<Integer> queue1 = new LinkedList<>();
Queue<Integer> queue2 = new LinkedList<>();
public boolean push(int node) {
if (!queue1.isEmpty()) {
return queue1.offer(node);
} else {
return queue2.offer(node);
}
}

public int pop() {
if (queue1.isEmpty() && queue2.isEmpty()) {
throw new RuntimeException("栈为空");
}
if (!queue1.isEmpty() && queue2.isEmpty()) {
while (queue1.size() != 1) {
queue2.offer(queue1.poll());
}
return queue1.poll();
} else {
while (queue2.size() != 1) {
queue1.offer(queue2.poll());
}
return queue2.poll();
}
}
}

641. 设计循环双端队列

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
class MyCircularDeque {
int[] nums;
int he, ta, cnt, k;
public MyCircularDeque(int _k) {
k = _k;
nums = new int[k];
}
public boolean insertFront(int value) {
if (isFull()) return false;
he = (he + k - 1) % k;
nums[he] = value; cnt++;
return true;
}
public boolean insertLast(int value) {
if (isFull()) return false;
nums[ta++] = value; cnt++;
ta %= k;
return true;
}
public boolean deleteFront() {
if (isEmpty()) return false;
he = (he + 1) % k; cnt--;
return true;
}
public boolean deleteLast() {
if (isEmpty()) return false;
ta = (ta + k - 1) % k; cnt--;
return true;
}
public int getFront() {
return isEmpty() ? -1 : nums[he];
}
public int getRear() {
return isEmpty() ? -1 : nums[(ta + k - 1) % k];
}
public boolean isEmpty() {
return cnt == 0;
}
public boolean isFull() {
return cnt == k;
}
}

面试官:给你十分钟,写出可以增删查改任意位置插入删除的链表!

并查集

并查集算法

【详解】并查集

题1

题目描述

给定一个包含n个点(编号为1~n)的无向图,初始时图中没有边。

现在要进行m个操作,操作共有三种:

“C a b”,在点a和点b之间连一条边,a和b可能相等;
“Q1 a b”,询问点a和点b是否在同一个连通块中,a和b可能相等;
“Q2 a”,询问点a所在连通块中点的数量;

输入格式

第一行输入整数n和m。

接下来m行,每行包含一个操作指令,指令为“C a b”,“Q1 a b”或“Q2 a”中的一种。

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
48
49
50
#include<iostream>
using namespace std;
const int N=1e5+10;

int n,m;
int p[N],size[N]; //p[N]存每个结点的父结点,size[N]存每个集合的元素个数
//只有祖宗结点的size才有意义

int find(int x) //返回x的祖宗结点+路径优化
{
if(p[x]!=x) p[x]=find(p[x]); //p[x]!=x说明不是祖宗结点
return p[x];
}

int main()
{
cin>>n>>m;
for(int i=1; i<=n; i++)
{
p[i]=i; //刚开始每个元素都是各自在一个集合内,此时所有元素的p[x]=x
size[i]=1; // 刚开始每个集合都只有一个元素
}

while(m--)
{
char op[5];
int a,b;
cin>>op;

if(op[0] == 'C') //合并
{
cin>>a>>b;
if(find(a) == find(b)) continue; //a和b已经在一个集合了
size[find(b)] += size[find(a)]; //合并后b(size)=b(size)+a(size)
p[find(a)] = find(b);
}
else if(op[1] == '1') //查询是否在同一集合
{
cin>>a>>b;
if(find(a) == find(b)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
else //查询集合内元素个数
{
cin>>a;
cout<<size[find(a)]<<endl;
}
}
return 0;
}

股票推荐

ZOOM秋招笔试

题目

完成股票推荐系统设计,每个用户可能关注几个公司,比如A,B,C,如果有另一个用户只关注了A,那么就会给他推荐B,C。这时候如果来了一个用户关注C,D,那么后来关注C的用户,都会推荐A,B,关注A的用户都会推荐BCD。在有上面的关系后,求用户查询的时候,会给它推荐的公司的个数。

输入

第一行输入q表示操作次数 接下来输入一次操作 共有两种操作 1.注册 格式为 1 name n 表示有一个name的人关注了n个股票 第二行输入n个字符串表示这n个股票 n个字符串不相同 2.查询 格式为 输入2 name 表示查询系统会给此人推荐多少股票 保证至少有一次查询 例

5
1 Alice 2
Zoom Apple
2 Bob
2 Alice
1 Bob 2
Apple MicroSoft
2 Bob

见,面经章节

1631. 最小体力消耗路径

并查集 + Kruskal

一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值最大值 决定的。

而不是,所有体力值之和决定的

注意:

1 合并成为联通图什么的,首先是根据题目意思看需要如何建图,比如这一题要用可如斯特,所以需要[a, b, w],编号1,编号2,然后权重

2 然后为了合并,需要将二维的index改成一维的编号,比如是个矩阵,那么$x * col + y$这个编号就好,

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
package org.jcwang.zoom;

import java.util.*;

public class UnionFind1 {
public static void main(String[] args) {
Solution solution = new UnionFind1().new Solution();
System.out.println(solution.minimumEffortPath(new int[][]{{1,10,6,7,9,10,4,9}}));
}

public class Solution {
/**
考虑并查集 + Krustal
*/
// 1 并查集,变量(parent代表该编号的父节点编号是谁,所以节点编号需要一维,而且数组的大小一定要能满足题目所有的点)\
int N = 10009;
int[] parent = new int[N];
// 2 并查集:查找根节点
int find(int x) {
if (parent[x] != x) {
// 让所有查到到的该路径节点的parent直接指向最终的父节点编号,加快下次遍历
parent[x] = find(parent[x]);
}
return parent[x];
}
// 3 并查集:查询是否联通,看两个根节点是否一致
// 注意,下面find已经找到根了,parent[find(a)]是等于find(a)的,所以其实简写也没关系的
boolean query(int a, int b) {
return (parent[find(a)] == parent[find(b)]);
}
// 4 并查集:融合,两个根容易下就行
void union(int a, int b) {
// 当然,此处没有优化,没有考虑a和b哪一个深,如果a深,那么最好parent[b] = parent[a]
// 要实现优化的话,需要多一个变量rank[]记录深度
parent[find(a)] = parent[find(b)];
}
// 5 并查集,得到编号,本身一维的就不会需要这个函数了
int col;
int row;
int getIndex(int x, int y) {
return x * col + y;
}

public int minimumEffortPath(int[][] heights) {
col = heights[0].length;
row = heights.length;

// 6 首先初始化并查集
for (int i = 0; i < row * col; i++) {
parent[i] = i;
}

// 由于需要Krustal,所以使用点-点-权重的建图方式
// 预处理出所有的边
// edge 存的是 [a, b, w]:代表从 a 到 b 的体力值为 w
// 虽然我们可以往四个方向移动,但是只要对于每个点都添加「向右」和「向下」两条边的话,其实就已经覆盖了所有边了
List<int[]> edges = new ArrayList<>();
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
int cur = getIndex(i, j);

// 往下
if (i + 1 < row) {
int next = getIndex(i+1, j);
edges.add(new int[]{cur, next, Math.abs(heights[i][j] - heights[i+1][j])});
}
// 往右
if (j + 1 < col) {
int next = getIndex(i, j+1);
edges.add(new int[]{cur, next, Math.abs(heights[i][j] - heights[i][j+1])});
}
}
}

// krustal算法需要排序
Collections.sort(edges, (a, b) -> (a[2] - b[2]));

int start = getIndex(0, 0);
int end = getIndex(row - 1, col - 1);
// 从小边开始添加
for (int[] edge : edges) {
int x = edge[0], y = edge[1], w = edge[2];
if (!query(x, y)) { // 需要判断,不联通的时候,才添加
union(x, y);

// 若起点和终点都联通了,那么路径已经通了
if (query(start, end)) {
return w;
}
}
}

return 0;
}
}
}

947. 移除最多的同行或同列石头

并查集算法

Author: Jcwang

Permalink: http://example.com/2022/06/09/AlgorithmClassfication3/