今天回顾一下这几道算法

java">//最小栈//思路： 定义一个带有val、min、next 三个属性的节点，其中min表示除当前节点外剩余节点中最小的节点值，//以链表的形式存储节点，每次push节点都是插入到root后一个节点，删除也是root后一个节点，每次插入/删除都需要//更新root和插入/删除节点的min值class MinStack {class Node {int val, min;Node next;public Node() {this.min = Integer.MAX_VALUE;}public Node(int val) {this.val = val;}public Node(int val, Node next) {this.val = val;this.next = next;}}Node root;public void push(int val) {Node node = new Node(val, root.next);node.min = root.min;root.next = node;root.min = Math.min(root.min, val);}public void pop() {Node cur = root.next;if (cur.val == root.min) {root.min = cur.min;}root.next = cur.next;cur.next = null;}public Node getTop() {return root.next;}public int getMin() {return root.min;}}//前K个高频元素//思路： 采用桶排序思路，就是先用hashMap统计每个元素出现的次数，然后在以value为索引，key为值存储到一个list//集合数组中，我们只需要从尾遍历list即可找到前k个高频元素public int[] topKFrequent(int[] nums, int k) {HashMap<Integer, Integer> map = new HashMap<>();for (int num : nums) {if (map.containsKey(num)) {map.put(num, map.get(num) + 1);} else {map.put(num, 1);}}List<Integer>[] list = new List[nums.length + 1];for (int key : map.keySet()) {int value = map.get(key);if (list[value] == null) {list[value] = new ArrayList<>();}list[value].add(key);}int[] res = new int[k];for (int i = nums.length, j = 0; i >= 0 && j < k; i--) {if (list[i] != null) {for (int num : list[i]) {res[j++] = num;}}}return res;}//比特位计数//0  01  10  11  100  101  110  111//0  1   2   3   4    5    6    7//思路： 维护一个highBit记录当前为2整数次幂元素的最高位是第几位//其中存在这么一个关系  bits[i] = bits[i - highBit] + 1;//bits[i] 表示元素i的比特位有多少个1public int[] countBits(int n) {int[] bits = new int[n + 1];int highBit = 0;for (int i = 1; i <= n; i++) {if ((i & (i - 1)) == 0) {highBit = i;}bits[i] = bits[i - highBit] + 1;}return bits;}//打家劫舍III//思路： 定义两个map存储最大值，f存储选中当前节点时的最大值//g存储不选中当前节点时的最大值Map<TreeNode, Integer> f = new HashMap<>();Map<TreeNode, Integer> g = new HashMap<>();public int rob(TreeNode root) {dfs(root);return Math.max(f.getOrDefault(root, 0), g.getOrDefault(root, 0));}private void dfs(TreeNode node) {if (node == null) {return;}dfs(node.left);dfs(node.right);f.put(node, node.val + g.getOrDefault(node.left, 0) +g.getOrDefault(node.right, 0));g.put(node, Math.max(f.getOrDefault(node.left, 0), g.getOrDefault(node.left, 0)) +Math.max(f.getOrDefault(node.right, 0), g.getOrDefault(node.right, 0)));}//寻找重复数//思路： 因为数组是【1，n】的，且存在重复数，我们//可以把value当作数组索引，然后利用快慢指针思想进行遍历public int findDuplicate(int[] nums) {int slow = 0, fast = 0;do {slow = nums[slow];fast = nums[nums[fast]];} while (slow != fast);slow = 0;while (slow != fast) {slow = nums[slow];fast = nums[fast];}return slow;}