class Solution { // 二进制 // 将当前元素与1按位与，计算二进制中1的个数 public int[] countBits(int n) { int[] res= new int[n + 1]; for (int i = 0; i <=n; i++) { int count = 0; int tmp = i; while (tmp != 0) { if ((tmp & 1) == 1) { count++; } tmp >>= 1; } res[i] = count; } return res; } }
Interview-Notes
class Solution { //检查x和y中的二进制不同的位数，可以先计算x异或y，x^y //再利用按位与判断尾数是否为1 xor&1 public int hammingDistance(int x, int y) { int res = x^y, hammingDistance = 0; while (res != 0) { if ((res & 1) == 1) { hammingDistance++; } res >>= 1; } return hammingDistance; } }
/** * 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 { // 创建一个最小堆，存储所有的链表的头结点，每次从链表中取出一个节点，并将这个节点的下一个节点放入最小堆中 // 这样就可以保证每次取得当前k个节点的最小值 public ListNode mergeKLists(ListNode[] lists) { PriorityQueue<ListNode> pq = new PriorityQueue<>((a,b) -> a.val - b.val); ListNode dummy = new ListNode(-1); ListNode cur = dummy; for (ListNode node :lists) { if (node != null) { // 需要判断是否为空，否则会出现空指针异常，优先队列不能加入空值 pq.offer(node); } } while (!pq.isEmpty()) { cur.next = pq.poll(); cur = cur.next; if (cur.next != null) { pq.offer(cur.next); } } return dummy.next; } }
1. 优先队列 PriorityQueue class Solution { //优先队列存储当前元素值和索引，用大顶堆进行排序 public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; if (n == 1) { return nums; } int[] res = new int[n - k + 1]; //初始化大顶堆 PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> b[0] - a[0]); for (int i = 0; i < k; i++) { pq.offer(new int[]{nums[i],i}); } res[0] = pq.peek()[0]; int j = 1; for (int i = k ; i < n; i++) { pq.offer(new int[]{nums[i],i}); while (pq.peek()[1] < i - k + 1) { //滑动窗口的右边界k，左边界i-k+1 pq.poll(); } res[j++] = pq.peek()[0]; } return res; } } 2.单调队列 Deque
class Solution { public int[] dailyTemperatures(int[] temperatures) { Deque<Integer> stack = new ArrayDeque<>(); int n = temperatures.length; int[] ans = new int[n]; // 默认全是 0 for (int i = 0; i < n; i++) { while (!stack.isEmpty() && temperatures[stack.peekLast()] < temperatures[i]) { int idx = stack.pollLast(); ans[idx] = i - idx; } stack.offerLast(i); } return ans; } }
class Solution { //面积，（索引的差 + 1）*（高度的最小值） // 单调栈 // 对于index位置的最大矩形的款是到左右两边第一次出现比heights[index]小的位置， public int largestRectangleArea(int[] heights) { int n = heights.length; Deque<Integer> stack = new LinkedList<>(); int maxArea = 0; for (int i = 0; i < heights.length; i++) { // 当前柱子比栈顶小，说明找到了右边界 while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) { int top = stack.pop(); // 计算宽度 int maxWidth = stack.isEmpty() ? i : i - stack.peek() - 1; maxArea = Math.max(maxWidth * heights[top], maxArea); } stack.push(i); } // 处理右边没有更小柱子的情况 while (!stack.isEmpty()) { int top = stack.pop(); int maxWidth = stack.isEmpty() ? n : n - stack.peek() - 1; maxArea = Math.max(maxWidth * heights[top], maxArea); } return maxArea; } }
class Solution { // 所有可能，全排列，回溯 List<String> res = new ArrayList<>(); String[] numbers = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; public List<String> letterCombinations(String digits) { if (digits.length() == 0) { return res; } backTracking(digits, 0); return res; } StringBuffer sb = new StringBuffer(); public void backTracking(String digits, int num) { if (num == digits.length()) { res.add(sb.toString()); return; } int index = digits.charAt(num) - '0'; // 这里-'0'得到数字，不能用Inter.valueOf(),这是将字符串转为数字 String tmp = numbers[index]; for (int i = 0; i < tmp.length(); i++) { sb.append(tmp.charAt(i)); backTracking(digits, num + 1); sb.deleteCharAt(sb.length() - 1); } } }
class Solution { // 回溯，全排列 // stringBuffer的append方法和deleteCharAt()方法 // 有效的括号组合，对于任意括号左边的左括号的数量大于等于右括号的数量 // 空间复杂度：O(n) List<String> res; int left, right; int count = 0; StringBuffer sb = new StringBuffer(); public List<String> generateParenthesis(int n) { left = 0; right = 0; count = n; res = new ArrayList<>(); backTracking(); return res; } public void backTracking() { if (right == count) { res.add(sb.toString()); } if (left < count) { // append左括号 sb.append('('); left++; backTracking(); sb.deleteCharAt(sb.length() - 1); left--; } if (right < left) { // append右括号，右括号的数量需要小于左括号的数量 sb.append(')'); right++; backTracking(); sb.deleteCharAt(sb.length() - 1); right--; } } }
class Solution { // 1.回溯 因为是需要返回列表 // 如果是求个数那就是完全背包 // 递归三要素：1.返回值的类型和传递的参数 2.递归终止的条件 3.单层递归的逻辑 List<List<Integer>> res = new ArrayList(); List<Integer> path = new LinkedList(); public List<List<Integer>> combinationSum(int[] candidates, int target) { backTracking(candidates,target,0,0); // 后面俩个0,0 对应sum 和 startIndex 避免重复遍历 return res; } public void backTracking(int[] candidates, int target, int sum, int startIndex) { if (sum == target) { res.add(new ArrayList(path)); return; } if (sum > target) { return; } for (int i = startIndex; i < candidates.length; i++) { sum += candidates[i]; path.add(candidates[i]); backTracking(candidates,target,sum,i); sum -= candidates[i]; path.removeLast(); } } }
class Solution { // 回溯算法，用一个boolean类型的数组标记已经使用过的数字 // 回溯三要素：回溯函数的参数和返回类型、回溯的终止条件、回溯搜索的遍历过程 // 全排列：非常经典的回溯算法，回溯算法的本质上遍历所有的和能效 List<List<Integer>> res = new ArrayList(); List<Integer> path = new LinkedList(); public List<List<Integer>> permute(int[] nums) { boolean[] used = new boolean[nums.length]; backtracking(nums,used); return res; } public void backtracking(int[] nums, boolean[] used) { if (path.size() == nums.length) { res.add(new ArrayList(path)); } for (int i = 0; i < nums.length; i++) { if (used[i] == true) continue; path.add(nums[i]); used[i] = true; backtracking(nums,used); path.remove(path.size() - 1); // 后两步是在回溯，表明当前前缀数字的所有可能性都已经遍历完 used[i] = false; } } // public void backtracking(int[] nums, boolean[] used){ // if(path.size() == nums.length){ // res.add(new ArrayList(path)); // 需要注意：这里是new ArrayList(path) ,不是直接path，因为path是一直在变化的 // return; // } // for(int i = 0; i < nums.length ; i++){ // if(used[i] == true)continue; // path.add(nums[i]); // used[i] = true; // backtracking(nums,used); // path.removeLast(); // used[i] = false; // } // } }