字节算法题

动态规划

• 基本思想：问题的最优解如果可以由子问题的最优解推导得到，则可以先求解子问题的最优解，在构造原问题的最优解；若子问题有较多的重复出现，则可以自底向上从最终子问题向原问题逐步求解。

1.具有相同的子问题：我们必须保证我们分割成的子问题也能按照相同的方法分割成更小的自问题， 并这些自问题的最终分割情况是可以解决的。
2.满足最优子结构：就是一个决策的子决策也是最优的
3.无后效性：这是DP中最重要的一点， 他要求每个子问题的决策不能对后面其他未解决的问题产影响， 如果产生就无法保证决策的最优性， 这就是无后效性。往往需要我们找到一个合适的状态。


自己设计HashMap

class MyHashMap {
    private class Pair {
        private int key;
        private int value;
        public Pair(int key, int value) {
            this.key = key;
            this.value = value;
        }
        public int getKey() {
            return key;
        }
        public int getValue() {
            return value;
        }
        public void setValue(int value) {
            this.value = value;
        }
    }
    private static final int BASE = 769;
    private LinkedList[] data;
    public MyHashMap() {
        data = new LinkedList[BASE];
        for (int i = 0; i < BASE; ++i) {
            data[i] = new LinkedList<Pair>();
        }
    }
    public void put(int key, int value) {
        int h = hash(key);
        Iterator<Pair> iterator = data[h].iterator();
        while (iterator.hasNext()) {
            Pair pair = iterator.next();
            if (pair.getKey() == key) {
                pair.setValue(value);
                return;
            }
        }
        data[h].offerLast(new Pair(key, value));
    }
    public int get(int key) {
        int h = hash(key);
        Iterator<Pair> iterator = data[h].iterator();
        while (iterator.hasNext()) {
            Pair pair = iterator.next();
            if (pair.getKey() == key) {
                return pair.value;
            }
        }
        return -1;
    }
    public void remove(int key) {
        int h = hash(key);
        Iterator<Pair> iterator = data[h].iterator();
        while (iterator.hasNext()) {
            Pair pair = iterator.next();
            if (pair.key == key) {
                data[h].remove(pair);
                return;
            }
        }
    }
    private static int hash(int key) {
        return key % BASE;
    }
}

1. 两数之和

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{i, map.get(target - nums[i])};
            }
            map.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }
}

2. 两数相加

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            int sum = x + y + carry;
            ListNode newHead = new ListNode(sum % 10);
            cur.next = newHead;
            cur = newHead;
            carry = sum / 10;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        return dummy.next;
    }
}

3. 无重复字符的最长子串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0;
        int maxLen = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            window.put(c, window.getOrDefault(c, 0) + 1);
            right++;
            while (window.get(c) > 1) {
                char rc = s.charAt(left);
                window.put(rc, window.get(rc) - 1);
                left++;
            }
            maxLen = Math.max(maxLen, right - left);
        }
        return maxLen;
    }
}

215. 数组中的第K个最大元素

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int val : nums) {
            if (pq.size() < k) {
                pq.offer(val);
            } else if (val > pq.peek()) {
                pq.poll();
                pq.offer(val);
            }
        }
        return pq.peek();
    }
}

25. K 个一组翻转链表

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int val : nums) {
            if (pq.size() < k) {
                pq.offer(val);
            } else if (val > pq.peek()) {
                pq.poll();
                pq.offer(val);
            }
        }
        return pq.peek();
    }
}

146. LRU 缓存机制

重点在makeRecently——remove之后再put

class LRUCache {
    int cap;
    //有序的双向链表
    LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
    public LRUCache(int capacity) {
        this.cap = capacity;
    }
    //get操作会有一次makeRecently
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        makeRecently(key);
        return cache.get(key);
    }
    //put操作如果key存在的话会更新值再做makerecently
    //如果不存在且大于容量会通过迭代器remove掉OldKey
    public void put(int key, int val) {
        if (cache.containsKey(key)) {
            cache.put(key, val);
            makeRecently(key);
            return;
        }
        if (cache.size() >= this.cap) {
            // 链表头部就是最久未使用的 key
            int oldKey = cache.keySet().iterator().next();
            cache.remove(oldKey);
        }
        // 将新的 key 添加链表尾部
        cache.put(key, val);
    }
    private void makeRecently(int key) {
        int val = cache.get(key);
         // 删除 key，重新插入到队尾
        cache.remove(key);
        cache.put(key, val);
    }
}

class LRUCache {
    private HashMap<Integer, Node> map;
    private DoubleList cache;
    private int cap;
    public LRUCache(int capacity) {
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }
    public int get(int key) {
        if (!map.containsKey(key))
            return -1;
        int val = map.get(key).val;//Node.val
        // 利用 put 方法把该数据提前
        put(key, val);
        return val;
    }
    public void put(int key, int val) {
        // 先把新节点 x 做出来
        Node x = new Node(key, val);
        if (map.containsKey(key)) {
            // 删除旧的节点，新的插到头部
            cache.remove(map.get(key));
            cache.addFirst(x);
            // 更新 map 中对应的数据
            map.put(key, x);
        } else {
            if (cap == cache.size()) {
                // 删除链表最后一个数据
                Node last = cache.removeLast();
                map.remove(last.key);
            }
            // 直接添加到头部
            cache.addFirst(x);
            map.put(key, x);
        }
    }
}
class Node {
    public int key, val;
    public Node next, prev;
    public Node(int k, int v) {
        this.key = k;
        this.val = v;
    }
}
class DoubleList {  
    // 头尾虚节点
    private Node head, tail;  
    private int size;
    public DoubleList() {
        // 初始化双向链表的数据
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
        size = 0;
    }
    // 在链表尾部添加节点 x，时间 O(1)
    public void addLast(Node x) {
        x.prev = tail.prev;
        x.next = tail;
        tail.prev.next = x;
        tail.prev = x;
        size++;
    }
    // 删除链表中的 x 节点（x 一定存在）
    public void remove(Node x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;
        size--;
    }
    // 删除链表中第一个节点，并返回该节点，时间 O(1)
    public Node removeFirst() {
        if (head.next == tail)
            return null;
        Node first = head.next;
        remove(first);
        return first;
    }
    // 返回链表长度，时间 O(1)
    public int size() { return size; }
}

15. 三数之和

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        int len = nums.length;
        if (nums == null || len < 3) {
            return ret;
        }
        Arrays.sort(nums);
        for (int i = 0; i < len; i++) {
            int L = i + 1;
            int R = len - 1;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            while (L < R) {
                int sum = nums[i] + nums[L] + nums[R];
                if (sum == 0) {
                    ret.add(Arrays.asList(nums[i],nums[L],nums[R]));
                    while (L < R && nums[L] == nums[L + 1]) L++;
                    while (L < R && nums[R] == nums[R - 1]) R--;
                    L++;
                    R--;
                } else if (sum < 0){
                    L++;
                } else {
                    R--;
                }
            }
        }
        return ret;
    }
}

103. 二叉树的锯齿形层序遍历

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int cnt = queue.size();
            List<Integer> temp = new ArrayList<>();
            while (cnt-- > 0) {
                TreeNode node = queue.poll();
                temp.add(node.val);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            if (ret.size() % 2 == 0) {
                ret.add(new ArrayList<>(temp));
            } else {
                Collections.reverse(temp);
                ret.add(new ArrayList<>(temp));
            }
        }
        return ret;
    }
}

160. 相交链表

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

236. 二叉树的最近公共祖先

想象一个最简单场景——p, q为root的左右子树，则left和right都不为null
都为null则返回null

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
       if (root == null || root == p || root == q) return root;
       TreeNode left = lowestCommonAncestor(root.left, p, q);
       TreeNode right = lowestCommonAncestor(root.right, p, q);
       if (left == null && right == null) return null;
       else if (left != null && right != null) return root;
       else return left == null ? right : left;
    }
}

42. 接雨水

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        int[] max_r = new int[len];
        int[] max_l = new int[len];
        int res = 0;
        for (int i = 1; i < len; i++) {
            max_l[i] = Math.max(max_l[i - 1], height[i - 1]);
        }
        for (int j = len - 2; j >= 0; j--) {
            max_r[j] = Math.max(max_r[j + 1], height[j + 1]);
        }
        for (int i = 0; i < len; i++) {
            int min = Math.min(max_l[i], max_r[i]);
            if (min <= height[i]) continue;
            else {
                res += min - height[i];
            }
        }
        return res;
    }
}

优化：空间复杂度降为O(1)——双指针

public int trap(int[] height) {
    if (height.length == 0) return 0;
    int sum = 0;
    int n = height.length;
    int left = 0, right = n - 1;
    int l_max = height[0];
    int r_max = height[n - 1];
    while (left <= right) {
        l_max = Math.max(l_max, height[left]);
        r_max = Math.max(r_max, height[right]);
        if (l_max < r_max) {
            sum += l_max - height[left];
            left++;
        } else {
            sum += r_max - height[right];
            right--;
        }
    }
    return sum;
}

415. 字符串相加

class Solution {
    public String addStrings(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        int carry = 0, i = num1.length() - 1, j = num2.length - 1;
        while (i >= 0 || j >= 0 || carry != 0) {
            if(i>=0) carry += num1.charAt(i)-'0';
            if(j>=0) carry += num2.charAt(j)-'0';
            sb.append(carry%10);
            carry /= 10;
            i--;
            j--;
        }
        return sb.reverse().toString();
    }
}

54. 螺旋矩阵

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix == null || matrix.length == 0) return res;
        int t = 0;
        int l = 0;
        int b = matrix.length - 1;
        int r = matrix[0].length - 1;
        while (true) {
            for (int i = l; i <= r; i++) res.add(matrix[t][i]);
            if (++t > b) break;
            for (int i = t; i <= b; i++) res.add(matrix[i][r]);
            if (--r < l) break;
            for (int i = r; i >= l; i--) res.add(matrix[b][i]);
            if (--b < t) break;
            for (int i = b; i >= t; i--) res.add(matrix[i][l]);
            if (++l > r) break;
        }
        return res;
    }
}

88. 合并两个有序数组

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int len1 = m - 1;
        int len2 = n - 1;
        int len = m + n - 1;
        while (len1 >= 0 && len2 >= 0) {
            nums1[len--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--];
        }
        //如果走完nums1 nums2里面的元素还没有转移完，一定是比之前比较和和转移小的元素
        //直接拷贝到nums1的前面
        while (len2 >= 0) {
            nums1[len--] = nums2[len2--];
        }
    }
}

33. 搜索旋转排序数组

class Solution {
    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            // 先根据 nums[mid] 与 nums[lo] 的关系判断 mid 是在左段还是右段 
            if (nums[mid] >= nums[lo]) {
                // 再判断 target 是在 mid 的左边还是右边，从而调整左右边界 lo 和 hi
                if (target >= nums[lo] && target < nums[mid]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else {
                if (target > nums[mid] && target <= nums[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return -1;
    } 
}

200. 岛屿数量

class Solution {
    private int m, n;
    private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public int numIslands(char[][] grid) {
        m = grid.length;
        n = grid[0].length;
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    private void dfs(char[][] grid, int r, int c) {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] != '1') {
            return;
        }
        grid[r][c] = '2';
        for (int[] d : direction) {
            dfs(grid, r + d[0], c + d[1]);
        }
    }
}

199. 二叉树的右视图

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int cnt = queue.size();
            while (cnt-- > 0) {
                TreeNode temp = queue.poll();
                if (cnt == 0) {
                    res.add(temp.val);
                }
                if (temp.left != null) queue.add(temp.left);
                if (temp.right != null) queue.add(temp.right);
            }
        }
        return res;
    }
}

31. 下一个排列

class Solution {
    public void nextPermutation(int[] nums) {
        int len = nums.length;
        int firstIndex = -1;
        //1.需要将后面大数的与前面小数的交换
        for (int i = len - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                firstIndex = i;
                break;
            }
        }
        //2.如果不存在逆序整个数组
        if (firstIndex == -1) {
            reverse(nums, 0, nums.length - 1);
            return;
        }
        int secondIndex = -1;
        //3.从后往前找尽可能的大数，因为firstindex后面的是降序
        for (int i = len - 1; i >= 0; i--) {
            if (nums[i] > nums[firstIndex]) {
                secondIndex = i;
                break;
            }
        }
        //4.交换大数与小数
        swap(nums, firstIndex, secondIndex);
        //5.firstindex后面是降序，reverse使其升序
        reverse(nums, firstIndex + 1, nums.length - 1);
    }
    private void reverse(int[] nums, int i, int j) {
        while (i < j) {
            swap(nums, i++, j--);
        }
    }
    private void swap(int[] nums, int i, int i1) {
        int tmp = nums[i];
        nums[i] = nums[i1];
        nums[i1] = tmp;
    }
}

102. 二叉树的层序遍历

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int cnt = queue.size();
            List<Integer> temp = new ArrayList<>();
            while (cnt-- > 0) {
                TreeNode node = queue.poll();
                temp.add(node.val);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            ret.add(new ArrayList<>(temp));
        }
        return ret;
    }
}

300. 最长递增子序列

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return n;
        }
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int res = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

105. 从前序与中序遍历序列构造二叉树

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return traverse(preorder, 0, preorder.length - 1,
                 inorder, 0, inorder.length - 1);
    }
    private TreeNode traverse(int[] preorder, int pS, int pE,
                          int[] inorder, int iS, int iE) {
        if (pS > pE) return null;
        int rootVal = preorder[pS];
        int index = -1;
        for (int i = iS; i <= iE; i++) {
            if (inorder[i] == rootVal) {
                index = i;
                break;
            }
        }
        TreeNode root = new TreeNode(rootVal);
        int leftL = index - iS;
        root.left = traverse(preorder, pS + 1, pS +leftL,  
                             inorder, iS, index - 1);
        root.right = traverse(preorder, pS +leftL + 1, pE, 
                              inorder, index + 1, iE);
        return root; 
    }
}

20. 有效的括号

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') stack.push(')');
            else if (c == '[') stack.push(']');
            else if (c == '{') stack.push('}');
            //没有考虑stack.isEmpty(),当只有右括号的时候不会入栈，此时栈是空的，不用后面的判断语句就可返回false
            else if (stack.isEmpty() || c != stack.pop()) return false;
        }
        //只有左括号的情况
        return stack.isEmpty();
    }
}

46. 全排列

class Solution {
    List<List<Integer>> ret = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0) return ret;
        List<Integer> track = new ArrayList<>();
        boolean[] hasVisited = new boolean[nums.length];
        backtrack(nums, track, hasVisited);
        return ret;
    }
    private void backtrack(int[] nums, List<Integer> track, boolean[] visited) {
        if (track.size() == nums.length) {
            ret.add(new ArrayList<>(track));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            track.add(nums[i]);
            backtrack(nums, track, visited);
            track.remove(track.size() - 1);
            visited[i] = false;
        }
        return;
    } 
}

56. 合并区间

class Solution {
    public int[][] merge(int[][] intervals) {
        int len = intervals.length;
        Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
        int[][] res = new int[len][2];
        int idx = -1;//索引
        for (int[] interval : intervals) {
            //判断遍历元素和结果数组
            if (idx == -1 || interval[0] > res[idx][1]) {
                res[++idx] = interval;
            } else {
                res[idx][1] = Math.max(res[idx][1], interval[1]);
            }
        }
        //因为合并区间之后会小于len，所以要截取要不然会有[0, 0]
        return Arrays.copyOf(res, idx + 1);
    } 
}

143. 重排链表

class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        ListNode slow = head, fast = head.next;
        while (fast.next != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode needReverse = reverse(slow.next);
        slow.next = null;
        while (needReverse != null) {
            ListNode next = head.next;
            ListNode needNext = needReverse.next;
            needReverse.next = head.next;
            head.next = needReverse;
            head = next;
            needReverse = needNext;
        }
    }
    private ListNode reverse(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(-1);
        while (head != null) {
            ListNode next = head.next;
            head.next = dummy.next;
            dummy.next = head;
            head = next;
        }
        return dummy.next;
    }
}

112. 路径总和

//错误写法
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        if (root.left == null && root.right == null && targetSum == root.val) {
            return true;
        }
        hasPathSum(root.left, targetSum - root.val);
        hasPathSum(root.right, targetSum - root.val);
        return false;
    }
}
//函数返回类型是boolean类型的，所以递归的时候直接返回就可以了
//对递归理解还是不够
return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);

129. 求根节点到叶节点数字之和

字节实习面试算法题

public int sumNumbers(TreeNode root) {
    return helper(root, 0);
}
public int helper(TreeNode root, int i){
    if (root == null) return 0;
    int temp = i * 10 + root.val;
    if (root.left == null && root.right == null)
        return temp;
    return helper(root.left, temp) + helper(root.right, temp);
}