[知识总结] 【CodeTop x LeetCode】Page 4 ： 61-80面试高频算法题题解

更多答案也可以关注我的GitHub算法仓库——Algorithm

所有代码都是在力扣上提交通过的，保证代码的正确无误

基础数据结构：

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 TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode() {}
       TreeNode(int val) { this.val = val; }
       TreeNode(int val, TreeNode left, TreeNode right) {
           this.val = val;
           this.left = left;
           this.right = right;
       }
    }

155.最小栈

使用 辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。

• 当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中
• 当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出
• 在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中

class MinStack {
    ArrayDeque<Integer> stack;
    ArrayDeque<Integer> minStack;
    public MinStack() {
        stack = new ArrayDeque<>();
        minStack = new ArrayDeque<>();
        minStack.push(Integer.MAX_VALUE);
    }
    public void push(int val) {
        stack.push(val);
        minStack.push(Math.min(val, minStack.peekFirst()));
    }
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    public int top() {
        return stack.peekFirst();
    }
    public int getMin() {
        return minStack.peekFirst();
    }
}

41.缺失的第一个正数

缺失的正数一定在[1, nums.length+1]中，由于题目限制空间复杂度为O(1)，我们需要修改原数组，结合数组下标的特性来替代哈希表。

public int firstMissingPositive(int[] nums) {
    int l = nums.length;
    //将所有小于等于0的数置为l+1
    for (int i = 0; i < l; i++) {
        if (nums[i] <= 0) {
            nums[i] = l+1;
        }
    }
    for (int i = 0; i < l; i++) {
        int temp = Math.abs(nums[i]);
        if (temp <= l) {
            nums[temp-1] = -Math.abs(nums[temp-1]);
        }
    }
    //寻找下标对应的第一个正数，返回该下标
    for (int i = 0; i < l; i++) {
        if (nums[i] > 0) {
            return i+1;
        }
    }
    return l+1;
}

718.最长重复子数组

这里要注意是连续子数组，不同于字符串的子序列，所以状态转移方程中不相等的情况下：dp[i][j] = 0;

1. 动规：时间O(MN)，空间O(MN)
2. 滑动窗口： O((N+M)×min(N,M)) ，空间 O(1)

public int findLength(int[] nums1, int[] nums2) {
    int[][] dp = new int[nums1.length+1][nums2.length+1];
    int res = 0;
    for (int i = 1; i <= nums1.length ; i++) {
        for (int j = 1; j <= nums2.length; j++) {
            if (nums1[i-1] == nums2[j-1]) {
                dp[i][j] = 1 + dp[i-1][j-1];
            } else {
                dp[i][j] = 0;
            }
            res = Math.max(res, dp[i][j]);
        }
    }
    return res;
}

234.回文链表

时间O(n)，空间O(1)，思路还是比较好想的

• 快慢指针找中点
• 翻转一半
• 再遍历比较

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head.next == null) {
            return true;
        }
        ListNode slow = head, fast = head, slowPre = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slowPre = slow;
            slow = slow.next;
        }
        ListNode l2 = slow.next, l1;
        if (fast.next != null) {
            slowPre = slow;
        }
        slowPre.next = null;
        l1 = reverseList(head);
        while (l1 != null && l2 != null) {
            if (l1.val != l2.val) {
                return false;
            }
            l1 = l1.next;
            l2 = l2.next;
        }
        return true;
    }

    public ListNode reverseList(ListNode head) {
        ListNode prev = null, next = null;
        while (head != null) {
            next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}

78.子集

记原序列中元素的总数为 n。原序列中的每个数字 ai 的状态可能有两种，即「在子集中」和「不在子集中」。

我们用 1 表示「在子集中」，0 表示不在子集中，那么每一个子集可以对应一个长度为 n 的 0/1 序列，第 i 位表示 ai是否在子集中。

（这里会用到位运算）

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> t = new ArrayList<>();
    int n = nums.length;
    for (int i = 0; i < (1 << n); i++) {
        t.clear();
        for (int j = 0; j < n; j++) {
            if ((i & (1 << j)) != 0) {
                t.add(nums[j]);
            }
        }
        res.add(new ArrayList<>(t));
    }
    return res;
}

112.路径总和

递归

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return sum == root.val;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

98.验证二叉搜索树

两个递归思路：

1. 递归，但要判断节点的上下界
2. 递归，中序遍历需递增

class Solution {
    Long last = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (isValidBST(root.left)) {
            if (last < root.val) {
                last = root.val + 0l;
                return isValidBST(root.right);
            }
        }
        return false;
    }
}

32.最长有效括号

也是一道动态规划，但是动态规划的转移方程比较难想，dp[i]代表以s.charAt(i)结尾时的最长有效括号，由于题目要求为最长且连续，那么：

• 如果dp[i] == '('，那么在当前位置一定是0
• 如果dp[i] == ')'，那么需要根据dp[i-1]来找到前一个为被匹配的 '('
• 如果存在，则dp[i] = 2 + dp[i-1] + dp[i - dp[i-1] - 2] 这里的dp[i - dp[i-1] - 2]为上一个未被匹配的'('，也就是上一个断连之前的最长连续有效括号值
• 其中还需要判断数组下标-1的情况

public int longestValidParentheses(String s) {
    int len = s.length();
    if (len <= 1) {
        return 0;
    }
    int res = 0;
    int[] dp = new int[len];
    for (int i = 1; i < len; i++) {
        if (s.charAt(i) == ')' && i - dp[i-1] > 0 && s.charAt(i - dp[i-1] -1) == '(') {
            dp[i] += (2 + dp[i-1]);
            if (i - dp[i-1]  > 1) {
                dp[i] += dp[i - dp[i-1] - 2];
            }
            res = Math.max(res, dp[i]);
        }
    }
    return res;
}

101.对称二叉树

两个指针，同步对称移动

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return dfs(root, root);
    }

    public boolean dfs(TreeNode q, TreeNode p) {
        if (q == null && p == null) {
            return true;
        }
        if (q == null || p == null) {
            return false;
        }
        return q.val == p.val && dfs(q.left, p.right) && dfs(q.right, p.left);
    }
}

322.零钱兑换

区间dp，dp数组定义不是根据硬币，而是根据金额：dp[i] 代表总金额为 i 时所需的最小硬币个数
状态转移方程也是有些难度的，将数组初始化为无穷大，代表此金额无法使用所给金币凑出，dp[0] = 0

• 如果当前金额可以被某一种硬币凑出，则：dp[i] = Math.min(dp[i - coin] + 1, dp[i]);

public int coinChange(int[] coins, int amount) {
    if (amount == 0) {
        return 0;
    }
    int[] dp = new int[amount+1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int coin : coins) {
        for (int i = coin; i <= amount ; i++) {
            if (dp[i - coin] != Integer.MAX_VALUE) {
                dp[i] = Math.min(dp[i - coin] + 1, dp[i]);
            }
        }
    }
    return dp[amount] < Integer.MAX_VALUE ? dp[amount] : -1;
}

22.括号生成

题目要求给出所有可能，暴力dfs即可

class Solution {
    List<String> res = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        dfs(n, n, "");
        return res;
    }

    public void dfs(int left, int right, String s) {
        for (int i = 0; i < 2; i++) {
            if (left == 0 && right == 0) {
                res.add(s);
                break;
            }
            if (i == 0 && left > 0) {
                dfs(left - 1, right, s + "(");
            }else if (i == 1 && right > left) {
                dfs(left, right - 1, s + ")");
            }
        }
    }
}

169.多数元素

Boyer-Moore 投票算法，时间O(n)，空间O(1)
算法过程：
我们维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0；
我们遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予candidate，随后我们判断 x：

1. 如果 x 与 candidate 相等，那么计数器 count 的值增加 1；
2. 如果 x 与 candidate 不等，那么计数器 count 的值减少 1。

在遍历完成后，candidate 即为整个数组的众数。

投票算法证明：

1. 如果候选人不是maj 则 maj,会和其他非候选人一起反对 会反对候选人,所以候选人一定会下台(maj==0时发生换届选举)
2. 如果候选人是maj , 则maj 会支持自己，其他候选人会反对，同样因为maj 票数超过一半，所以maj 一定会成功当选

public int majorityElement(int[] nums) {
    int cand = 0, count = 0;
    for (int i = 0; i < nums.length; i++) {
        if (count == 0) {
            cand = nums[i];
        }
        count += (cand == nums[i] ? 1 : -1);
    }
    return cand;
}

48.旋转图像

原地旋转：将矩形分为四块，两个for循环一块的量，但是每次swap四个块的坐标
就是四个对应坐标的转换方程有些难推

public void rotate(int[][] matrix) {
    int n = matrix.length;
    for (int i = 0; i < n/2; i++) {
        for (int j = 0; j < (n+1)/2; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[n - j - 1][i];
            matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
            matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
            matrix[j][n - i - 1] = temp;
        }
    }
}

43.字符串相乘

很恶心的题，费劲又麻烦，没啥特别简洁的套路

public String multiply(String num1, String num2) {
    if (num1.equals("0") || num2.equals("0")) {
        return "0";
    }
    int[] res = new int[num1.length() + num2.length()];
    for (int i = num1.length() - 1; i >= 0; i--) {
        int n1 = num1.charAt(i) - '0';
        for (int j = num2.length() - 1; j >= 0; j--) {
            int n2 = num2.charAt(j) - '0';
            int sum = (res[i + j + 1] + n1 * n2);
            res[i + j + 1] = sum % 10;
            res[i + j] += sum / 10;
        }
    }

    StringBuilder result = new StringBuilder();
    for (int i = 0; i < res.length; i++) {
        if (i == 0 && res[i] == 0) continue;
        result.append(res[i]);
    }
    return result.toString();
}

64.最小路径和

很简单常规的二维dp，转移方程 dp[i][j] = grid[i][j] + Math.min(dp[i][j-1], dp[i-1][j])

public int minPathSum(int[][] grid) {
    int row = grid.length;
    int col = grid[0].length;
    int[][] dp = new int[row][col];
    dp[0][0] = grid[0][0];
    for (int i = 1; i < row; i++) {
        dp[i][0] = dp[i-1][0] +  grid[i][0];
    }
    for (int i = 1; i < col; i++) {
        dp[0][i] = dp[0][i-1] +  grid[0][i];
    }
    for (int i = 1; i < row; i++) {
        for (int j = 1; j < col; j++) {
            dp[i][j] = grid[i][j] + Math.min(dp[i][j-1], dp[i-1][j]);
        }
    }
    return dp[row-1][col-1];
}

226. 翻转二叉树

典型递归

public TreeNode invertTree(TreeNode root) {
    if (root != null) {
        invertTree(root.left);
        invertTree(root.right);
        TreeNode tree = root.left;
        root.left = root.right;
        root.right = tree;
    }
    return root;
}

165.比较版本号

String.split分割，但是注意特殊字符前加\

class Solution {
    public int compareVersion(String version1, String version2) {
        String[] s1 = version1.split("\.");
        String[] s2 = version2.split("\.");
        int len1 = s1.length;
        int len2 = s2.length;
        for (int i = 0; i < len1 && i < len2; i++) {
            if (Integer.valueOf(s1[i]) > Integer.valueOf(s2[i])) {
                return 1;
            }
            if (Integer.valueOf(s1[i]) < Integer.valueOf(s2[i])) {
                return -1;
            }
        }
        if (len1 > len2 && remain(s1, len2) > 0) {
            return 1;
        }else if (len1 < len2 && remain(s2, len1) > 0) {
            return -1;
        }
        return 0;
    }

    public int remain(String[] arr, int start) {
        StringBuilder sb = new StringBuilder("");
        for (int i = start; i < arr.length; i++) {
            sb.append(arr[i]);
        }
        return Integer.valueOf(sb.toString());
    }
}

34.在排序数组中查找元素的第一个和最后一个位置

在使用二分查找第一次查找到目标值之后继续二分查找

那么第一次出现的即为一直二分后最左的位置，最后一次出现即为第一次比target大的数的下标-1

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        }
        return new int[]{-1, -1};
    }

    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right)/2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid -1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

83.删除排序链表中的重复元素

链表基操

public ListNode deleteDuplicates(ListNode head) {
    ListNode node = head;
    while (node != null) {
        ListNode cur = node.next;
        while (cur != null && node.val == cur.val) {
            cur = cur.next;
        }
        node.next = cur;
        node = node.next;
    }
    return head;
}

39.组合总和

由于题目要求所有情况，暴力dfs + 剪枝 + 回溯 即可

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    int[] arr;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        arr = candidates;
        dfs(new ArrayList<>(), target, 0);
        return res;
    }

    public void dfs(List<Integer> list, int val, int index) {
        if (val < 0) {
            return;
        }
        if (val == 0) {
            res.add(new ArrayList<>(list));
        }
        for (int i = index; i < arr.length; i++) {
            list.add(arr[i]);
            dfs(list, val - arr[i], i);
            list.remove(list.size() - 1);
        }
    }
}