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; } } }
|
并查集算法