字节跳动

牛客高频

LRU（双向链表 + HashMap）

  1. // 双向链表，用于修改LRU顺序
  2. public static class ListNode {
  3.     ListNode next;
  4.     ListNode pre;
  5.     int key;
  6.     int val;
  8.     public ListNode(int key, int val) {
  9.         this.key = key;
  10.         this.val = val;
  11.     }
  12. }
  14. // 快速查找LRU中的节点，key为LRU节点的key，val为LRU节点本身的ListNode
  15. Map<Integer, ListNode> map = new HashMap<>();
  16. // 虚拟头
  17. ListNode head = new ListNode(-1, -1);
  18. // 虚拟尾
  19. ListNode tail = new ListNode(-1, -1);
  20. int k;
  22. public int[] LRU (int[][] operators, int k) {
  23.     // 设置虚拟头、尾节点，方便头插节点、尾删节点与节点前移
  24.     head.next = tail;
  25.     tail.pre = head;
  26.     this.k = k;
  27.     int resultSize = (int)Arrays.stream(operators).filter(o -> o.length == 2).count();
  28.     int[] result = new int[resultSize];
  29.     int count = 0;
  30.     for(int i = 0; i < operators.length; i++) {
  31.         int[] operator = operators[i];
  32.         if(operator[0] == 1) {
  33.             set(operator[1], operator[2]);
  34.         } else if(operator[0] == 2) {
  35.             int val = get(operator[1]);
  36.             result[count] = val;
  37.             count ++;
  38.         }
  39.     }
  40.     return result;
  41. }
  43. // 节点前移，当get命中了节点、set插入了新节点时调用，将命中/新增的节点放到链表头部
  44. public void putToHead(ListNode node){
  45.     node.next = head.next;
  46.     node.pre = head;
  47.     head.next.pre = node;
  48.     head.next = node;
  49. }
  51. // LRU的get方法
  52. public int get(int key) {
  53.     if(!map.containsKey(key)) {
  54.         return -1;
  55.     }
  56.     putToHead(map.get(key));
  57.     return node.val;
  58. }
  60. // LRU的set方法
  61. public void set(int key, int val) {
  62.     if(get(key) != -1) {
  63.         map.get(key).val = val;
  64.     } else {
  65.         if(map.size() == this.k) {
  66.             map.remove(tail.pre.key);
  67.             // 删除超过长度的LRU队列最后一个节点
  68.             tail.pre.pre.next = tail;
  69.             tail.pre = tail.pre.pre;
  70.         }
  71.         ListNode newNode = new ListNode(key, val);
  72.         map.put(key, newNode);
  73.         putToHead(newNode);
  74.     }
  75. }
  77. public void putToHead(ListNode node){
  78.     // 已存在节点移到头部需要的操作
  79.     if(node.pre != null) {
  80.         node.pre.next = node.next;
  81.     }
  82.     if(node.next != null) {
  83.         node.next.pre = node.pre;
  84.     }
  86.     node.next = head.next;
  87.     node.pre = head;
  88.     head.next.pre = node;
  89.     head.next = node;
  90. }

两个只出现一次的数字（XOR位运算）

  1. public int[] singleNumber(int[] nums) {
  2.     int[] res = new int[2];
  3.     // 两个结果数字的xor结果
  4.     int xor = 0;
  5.     for(int num : nums) {
  6.         xor ^= num;
  7.     }
  9.     // 保存xor第一位为1的bit位idx
  10.     int idx = 0;
  11.     while((xor & (1 << idx)) == 0) {
  12.         idx++;
  13.     }
  15.     // 分两次单独寻找出现一次的数字
  16.     int res1 = 0, res2 = 0;
  17.     for(int num : nums) {
  18.         if((num & (1 << idx)) == 0) {
  19.             res1 ^= num;
  20.         } else {
  21.             res2 ^= num;
  22.         }
  23.     }
  24.     res[0] = res1;
  25.     res[1] = res2;
  26.     return res;
  27. }

国际化电商

接雨水问题（双指针）

  1. // 双指针做法
  2. public long maxWater (int[] arr) {
  3.     int left = 0, right = arr.length - 1;
  4.     int height = 0;
  5.     long result = 0;
  6.     while(left < right) {
  7.         int minHeight = Math.min(arr[left], arr[right]);
  8.         // 保存双指针指向最矮的边与已有高度的最大值作为上界
  9.         height = Math.max(minHeight, height);
  10.         // 最矮边高度作为下界求结果
  11.         if(arr[left] >= arr[right]) {
  12.             result += height - arr[right];
  13.             right --;
  14.         } else {
  15.             result += height - arr[left];
  16.             left ++;
  17.         }
  18.     }
  19.     return result;
  20. }

改版接雨水问题（双指针）

一批隔板，相邻距离为1，隔板不占体积，能蓄多少水？如[3, 2, 5, 4, 6, 2]返回18。
image.png

  1. public int trap(int[] arr) {
  2.     int l = 0, r = arr.length - 1;
  3.     int lHeight = 0, rHeight = 0;
  4.     int res = 0;
  5.     while (l < r) {
  6.         if (arr[l] < arr[r]) {
  7.             lHeight = Math.max(lHeight, arr[l]);
  8.             res += lHeight;
  9.             l++;
  10.         } else {
  11.             rHeight = Math.max(rHeight, arr[r]);
  12.             res += rHeight;
  13.             r--;
  14.         }
  15.     }
  16.     return res;
  17. }

二叉树路径和问题（递归 + DFS回溯）

  1. // 最终结果
  2. List<List<Integer>> result = new ArrayList<>();
  3. // DFS保存的路径
  4. List<Integer> path = new ArrayList<Integer>();
  6. public void traverse(TreeNode root, int sum, int targetSum) {
  7.     if(root == null){
  8.         return;
  9.     }
  10.     sum += root.val;
  11.     path.add(root.val);
  13.     // root为叶子结点，且求和与目标一致，将结果保存
  14.     if(root.left == null && root.right == null && sum == targetSum) {
  15.         result.add(new ArrayList(path));
  16.     }
  18.     // 递归左子树
  19.     traverse(root.left, sum, targetSum);
  20.     // 递归右子树
  21.     traverse(root.right, sum, targetSum);
  23.     // 路径回溯
  24.     path.remove(path.size() - 1);
  25. }
  27. public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
  28.     traverse(root, 0, targetSum);
  29.     return result;
  30. }

二叉树最近公共祖先（递归）

  1. public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  2.     if(root == null) {
  3.         return null;
  4.     }
  5.     // val相同的点必为公共祖先
  6.     if(root.val == p.val || root.val == q.val) {
  7.         return root;
  8.     }
  10.     // 递归得到左子树与右子树分别的公共祖先
  11.     TreeNode leftSub = lowestCommonAncestor(root.left, p, q);
  12.     TreeNode rightSub = lowestCommonAncestor(root.right, p, q);
  13.     // 左右子树不为null，根为公共祖先
  14.     if(leftSub != null && rightSub != null) {
  15.         return root;
  16.     } else if(leftSub == null) { // 左子树不包含公共祖先，返回右子树的根
  17.         return rightSub;
  18.     } else { // 右子树不包含公共祖先，返回左子树的根
  19.         return leftSub;
  20.     }
  21. }

完全平方数（DP）

  1. public int numSquares(int n) {
  2.     int[] dp = new int[n + 1];
  3.     for(int i = 1; i <= n; i++) {
  4.         int min = Integer.MAX_VALUE;
  5.         for(int num = 1; num * num <= i; num++) {
  6.             min = Math.min(min, dp[i - num * num]);
  7.         }
  8.         dp[i] = min + 1;
  9.     }
  10.     return dp[n];
  11. }

合并区间（贪心）

  1. public int[][] merge(int[][] intervals) {
  2.         if (intervals.length == 0) {
  3.             return new int[0][2];
  4.         }
  5.         // 排序后遍历
  6.         Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
  7.         List<int[]> res = new ArrayList<>();
  8.         int last = 0;
  9.         for(int i = 0; i < intervals.length; i++) {
  10.             int l = intervals[i][0], r = intervals[i][1];
  11.             last = res.size() - 1;
  12.             // 判断已确定上界和当前下界是否重合，不重合就新增结果
  13.             if(res.size() == 0 || res.get(last)[1] < l) {
  14.                 res.add(new int[]{l, r});
  15.             } else {
  16.                 // 重合则合并
  17.                 res.get(last)[1] = Math.max(res.get(last)[1], r);
  18.             }
  19.         }
  20.         return res.toArray(new int[res.size()][2]);
  21.     }

统计出现次数（双指针）

数组两端到中间降序排列，求数组中出现的不同数字个数，如[4, 5, 6, 9, 7, 6, 5, 1]返回6。

  1. public int differentNum(int arr[]) {
  2.     int res = 0;
  3.     int l = 0, r = arr.length - 1;
  4.     while (l <= r) {
  5.         // 保存双指针两侧小的值
  6.         int cache = Math.min(arr[l], arr[r]);
  7.         if (cache == arr[l]) {
  8.             while (l < arr.length && cache == arr[l]) {
  9.                 l++;
  10.             }
  11.         }
  12.         if (cache == arr[r]) {
  13.             while (r >= 0 && cache == arr[r]) {
  14.                 r--;
  15.             }
  16.         }
  17.         res++;
  18.     }
  19.     return res;
  20. }