[知识总结] 【CodeTop x LeetCode】Page 5 ： 81-100面试高频算法题题解

更多答案也可以关注我的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;
       }
    }

153.寻找旋转排序数组中的最小值

二分查找的变种，想这些二分查找变种相关的题目我掌握的实际并不好，需多次练习理解

public int findMin(int[] nums) {
    int l = 0;
    int h = nums.length - 1;
    while (l < h) {
        int mid = (l + h)/2;
        if (nums[mid] < nums[h]) {
            h = mid;
        }else {
            l = mid + 1;
        }
    }
    return nums[l];
}

排序

（纯排序题目，这里就不放代码了，之前有）

128. 最长连续序列

题目要求O(n)的时间复杂度，这里先使用Set把元素放入并去重，开始遍历，遍历数为x

• 如果存在x-1，跳过此次（因为要避免重复计算，要每次从连续数列的第一个开始计算）
• 存在x+1，继续查找更大的
• 更新结果

public int longestConsecutive(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i < nums.length; i++) {
        set.add(nums[i]);
    }
    int res = 0;
    for (int i = 0; i < nums.length; i++) {
        int x = nums[i];
        if (!set.contains(x-1)) {
            int cur = 0;
            while (set.contains(x)) {
                cur++;
                x++;
            }
            res = Math.max(res, cur);
        }
    }
    return res;
}

62.不同路径

经典动规，不多说了

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    for (int i = 0; i < n; i++) {
        dp[0][i] = 1;
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}

136.只出现一次的数字

要求时间O(n)，空间O(1)，则使用异或！

• 因为0^a=a，a^a=0，所以一个数字连续两次和0异或之后为0
• 又因为异或操作满足分配律，所以一个数组里的数字连续异或之后，剩余的结果即为只出现一次的数字！

public int singleNumber(int[] nums) {
    int res = 0;
    for (int num : nums) {
        res ^= num;
    }
    return res;
}

240.搜索二维矩阵 II

从右上角开始，向左下开始寻找

public boolean searchMatrix(int[][] matrix, int target) {
    int row = 0;
    int col = matrix[0].length - 1;
    while (col >= 0 && row < matrix.length) {
        if (matrix[row][col] == target) {
            return true;
        }
        if (target < matrix[row][col]) {
            col--;
        }else {
            row++;
        }
    }
    return false;
}

221.最大正方形

动规，状态转移方程为dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j],dp[i][j-1])) + 1，同时更新最优解

public int maximalSquare(char[][] matrix) {
    int[][] dp = new int[matrix.length][matrix[0].length];
    int res = 0;
    for (int i = 0; i < matrix.length; i++) {
        dp[i][0] = matrix[i][0] - '0';
        res = Math.max(res, dp[i][0]);
    }
    for (int i = 0; i < matrix[0].length; i++) {
        dp[0][i] = matrix[0][i] - '0';
        res = Math.max(res, dp[0][i]);
    }
    for (int i = 1; i < dp.length; i++) {
        for (int j = 1; j < dp[0].length; j++) {
            if (matrix[i][j] == '0') {
                continue;
            }
            dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j],dp[i][j-1])) + 1;
            res = Math.max(res, dp[i][j]);
        }
    }
    return res*res;
}

162.寻找峰值

二分变体

public int findPeakElement(int[] nums) {
    int l = 0, r = nums.length - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (nums[mid] < nums[mid + 1]) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return l;
}