AlgorithmClassfication3
树
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);
}
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;
}
public TreeNode dfs(ListNode head, ListNode tail) {
if (head == tail) {
return null;
}
ListNode mid = getMid(head, tail);
TreeNode node = new TreeNode(mid.val);
node.left = dfs(head, mid);
node.right = dfs(mid.next, tail);
return node;
}
}
|
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;
}
}
|
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;
}
}
|
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;
} 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 + " ");
}
}
|
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;
}
}
|
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 {
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;
}
}
|
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
注意：从该节点往下的路径和
所以此处的参数还是写在里面的，而不是返回值里面
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);
}
}
|
这道题目的做好好好注意一下，
比如拿到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;
}
if (node.right != succ) {
succPar.left = succ.right;
succ.left = node.left;
succ.right = node.right;
} else {
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;
}
}
|
注意：前缀和，高度；从叶子到该节点和
求前缀和，高度等，是从上往下面求的，所以参数放在函数中即可，（求高度返回值里面也要有）。
但是求从底部叶子到顶部的和，需要将值放在返回值中。
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;
}
}
|
这个也是从低向上，所以可以放在外面
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;
}
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);
}
}
|
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) + ")";
}
}
|
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);
}
}
|
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);
}
}
|
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);
}
}
|
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;
while (nextIright < inorder.length && inorder[nextIright] != rootVal) {
nextIright += 1;
}
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;
}
}
|
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
|
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;
}
}
|
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
|
class Solution {
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 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);
}
}
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;
}
}
|
根据这棵树，建图
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
|
class Solution {
int N = 501;
int M = N * 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++;
}
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);
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;
}
}
|
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
|
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<>();
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;
}
}
|
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;
}
}
|
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 {
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;
}
}
|
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;
}
}
|
原地哈希
看数组中数据的范围，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 {
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--;
}
}
return ans;
}
}
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快！
找到题眼，有任意两个元素之间的绝对差，那肯定是最大值，最小值。
优先队列，跟只用一个变量来维护最大最小值的区别就是：如果删除这个最大的，还能知道下一个最大的，而变量维护的不行了，只能添加得来。
此处其实用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) {
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;
}
}
|
还是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) {
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();
}
}
}
|
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];
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main()
{
cin>>n>>m;
for(int i=1; i<=n; i++)
{
p[i]=i;
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;
size[find(b)] += size[find(a)];
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
见，面经章节
并查集 + 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 {
int N = 10009;
int[] parent = new int[N];
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
boolean query(int a, int b) {
return (parent[find(a)] == parent[find(b)]);
}
void union(int a, int b) {
parent[find(a)] = parent[find(b)];
}
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;
for (int i = 0; i < row * col; i++) {
parent[i] = i;
}
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])});
}
}
}
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;
}
}
}
|
并查集算法