#yyds干货盘点# LeetCode刷题集:41-50

2021年11月24日 阅读数:5
这篇文章主要向大家介绍#yyds干货盘点# LeetCode刷题集:41-50,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

博主私藏的LeetCode刷题集合
有些较难的问题都有思路和注释c++

51. N皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,而且使皇后彼此之间不能相互吵架。数组

在这里插入图片描述

上图为 8 皇后问题的一种解法。markdown

给定一个整数 n,返回全部不一样的 n 皇后问题的解决方案。app

每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 'Q' 和 '.' 分别表明了皇后和空位。ide

示例:ui

输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],code

["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不一样的解法。blog

class Solution {
     public static List<List<String>> output;
    public List<List<String>> solveNQueens(int n) {
        output = new ArrayList<>();
        // 声明一个长度为n的数组用来表明 第n行棋子是在第result[n]列
        int[] result = new int [n];
        calnQueens(0, n, result);
        return output;
    }

    // n 皇后问题 row表明计算到了到第row行
    private static void calnQueens(int row, int n, int[] result){
        if (row == n){
            // 到达第n行表明已经获得一个将解决方案 直接返回便可
            // 根据result数组将结果加入到output列表中
            getPrint(result);
            return;
        }
        // 若不是第n行 则说明须要继续判断该行棋子应该在那一列
        for (int column = 0; column < n; column++){
            // 判断第row行 放置在column列的棋子是否知足要求
            if (isOK(row, column, result)){
                result[row] = column;
                // 递归判断下一行的状况
                calnQueens(row + 1, n, result);
            }
            // 不知足要求 回溯下一列 对应操做column++
        }
    }

    // row表明行数 column表明列数 result表明知足规则的棋子在第n行中的位置
    private static boolean isOK(int row, int column, int[] result){
        // 判断棋子的位置是否正确 不正确返回false
        for (int i = 0; i < row; i++){
            // 第一个条件排除的是相同列的问题
            // 第二个条件排除的是对角线列的左下角
            // 第三个条件排除的是对角线列的右下角
            if (column == result[i] || column == result[i] - row + i || column == result[i] + row - i){
                return false;
            }
        }
        return true;
    }

    private static void getPrint(int[] result){
        List<String> one = new ArrayList<>();
        for (int row = 0; row < result.length; row++){
            // 一行一个StringBuilder
            StringBuilder str = new StringBuilder();
            for (int column = 0; column < result.length; column++){
                if (column == result[row]){
                    str.append("Q");
                }else{
                    str.append(".");
                }
            }
            one.add(str.toString()); 
        }
        output.add(one);
    }
}

52. N皇后 II

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,而且使皇后彼此之间不能相互攻击。
在这里插入图片描述排序

上图为 8 皇后问题的一种解法。递归

给定一个整数 n,返回 n 皇后不一样的解决方案的数量。

示例:

输入: 4
输出: 2
解释: 4 皇后问题存在以下两个不一样的解法。
[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],

["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]

class Solution {

    /**
     * 记录某列是否已有皇后摆放
     */
    private boolean col[];

    /**
     * 记录某条正对角线(左上右下)是否已有皇后摆放(某条对角线对应的摆放位置为 x - y + n - 1)
     */
    private boolean dia1[];

    /**
     * 记录某条斜对角线(左下右上)是否已有皇后摆放(某条对角线对应的摆放位置为 x + y)
     */
    private boolean dia2[];

    public int totalNQueens(int n) {
        // 依然可使用 51 号问题的解决思路,但问题是有没有更好的方法
        col = new boolean[n];
        dia1 = new boolean[2 * n - 1];
        dia2 = new boolean[2 * n - 1];
        return putQueen(n, 0);
    }

    /**
     * 递归回溯方式摆放皇后
     *
     * @param n     待摆放皇后个数
     * @param index 已摆放皇后个数
     */
    private int putQueen(int n, int index) {
        int res = 0;
        if (index == n) {
            return 1;
        }
        // 表示在 index 行的第 i 列尝试摆放皇后
        for (int i = 0; i < n; i++) {
            if (!col[i] && !dia1[i - index + n - 1] && !dia2[i + index]) {
                // 递归
                col[i] = true;
                dia1[i - index + n - 1] = true;
                dia2[i + index] = true;
                res += putQueen(n, index + 1);
                // 回溯
                col[i] = false;
                dia1[i - index + n - 1] = false;
                dia2[i + index] = false;
            }
        }
        return res;
    }

}

53. 最大子序和

给定一个整数数组 nums ,找到一个具备最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
进阶:

若是你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        int sum = 0;
        for (int num : nums) {
            if (sum > 0)
                sum += num;
            else
                sum = num;
            res = Math.max(res, sum);
        }
        return res;
    }
}

54. 螺旋矩阵

给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的全部元素。

示例 1:

输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
示例 2:

输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new LinkedList<>();
        if(matrix.length==0)    return result;
        int upBound = 0;
        int rightBound = matrix[0].length-1;
        int leftBound = 0;
        int downBound = matrix.length-1;
        while(true){
            for(int i=leftBound; i<=rightBound; ++i)    
                result.add(matrix[upBound][i]);
            if(++upBound>downBound) break;
            for(int i=upBound; i<=downBound; ++i)   
                result.add(matrix[i][rightBound]);
            if(--rightBound<leftBound)  break;
            for(int i=rightBound; i>=leftBound; --i)   
                result.add(matrix[downBound][i]);
            if(--downBound<upBound) break;
            for(int i=downBound; i>=upBound; --i)   
                result.add(matrix[i][leftBound]);
            if(++leftBound>rightBound)  break;
        }
        return result;
    }
}

55. 跳跃游戏

给定一个非负整数数组,你最初位于数组的第一个位置。

数组中的每一个元素表明你在该位置能够跳跃的最大长度。

判断你是否可以到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 咱们能够先跳 1 步,从位置 0 到达 位置 1, 而后再从位置 1 跳 3 步到达最后一个位置。
示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 不管怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 因此你永远不可能到达最后一个位置。

PS:
从后往前遍历数组,若是遇到的元素能够到达最后一行,则截断后边的元素。不然继续往前,弱最后剩下的元素大于1个,则能够判断为假。不然就是真

class Solution {
   public boolean canJump(int[] nums) {
        int n=1;
        for(int i=nums.length-2;i>=0;i--){
            if(nums[i]>=n)
            {
                n=1;
            }
            else
            {
                n++;
            }
            if(i==0&&n>1)
            {
                return false;
            }
        }
        return true;

    }
}

56. 合并区间

给出一个区间的集合,请合并全部重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

class Solution {
     public int[][] merge(int[][] arr) {
        if(arr == null || arr.length<=1)
            return arr;
        List<int[]> list = new ArrayList<>();
        //Arrays.sort(arr,(a,b)->a[0]-b[0]);
        //按照两个组的左面的数进行比较
        //[1,3]   [2,4]  比较1和2     小的排前面,大的排后面   
        Arrays.sort(arr,new Comparator<int[]>(){
            @Override
            public int compare(int[] a,int[] b){
                return a[0]-b[0];
            }
        });
        int i=0;
        int n = arr.length;
        while(i<n){
            int left = arr[i][0];
            int right = arr[i][1];
            while(i<n-1 && right>=arr[i+1][0]){
                right = Math.max(right,arr[i+1][1]);
                i++;
            }
            list.add(new int[] {left,right});
            i++;
        }
        return list.toArray(new int[list.size()][2]);
    }
}

57. 插入区间

给出一个无重叠的 ,按照区间起始端点排序的区间列表。

在列表中插入一个新的区间,你须要确保列表中的区间仍然有序且不重叠(若是有必要的话,能够合并区间)。

示例 1:

输入: intervals = [[1,3],[6,9]], newInterval = [2,5]
输出: [[1,5],[6,9]]
示例 2:

输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出: [[1,2],[3,10],[12,16]]
解释: 这是由于新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int[][] newIntervals = new int[intervals.length + 1][];
        System.arraycopy(intervals, 0, newIntervals, 0, intervals.length);
        newIntervals[intervals.length] = newInterval;

        Arrays.sort(newIntervals, (a, b) -> a[0] - b[0]);
        Stack<int[]> stack = new Stack<>();
        for (int[] num : newIntervals) {
            if (stack.isEmpty()) {
                stack.push(num);
                continue;
            }
            int[] arr = stack.peek();
            if (arr[1] >= num[0]) {
                int[] combine = {arr[0], Math.max(arr[1], num[1])};
                stack.pop();
                stack.push(combine);
            } else {
                stack.push(num);
            }
        }
        return stack.toArray(new int[0][]);
    }
}

58. 最后一个单词的长度

给定一个仅包含大小写字母和空格 ' ' 的字符串 s,返回其最后一个单词的长度。

若是字符串从左向右滚动显示,那么最后一个单词就是最后出现的单词。

若是不存在最后一个单词,请返回 0 。

说明:一个单词是指仅由字母组成、不包含任何空格的 最大子字符串。

示例:

输入: "Hello World"
输出: 5

class Solution {
     public int lengthOfLastWord(String s) {
       int count=0;
        for(int i=s.length()-1;i>=0;i--) {
            if(s.charAt(i)!=' ') {
                count++;                
            }else if(count>0){
                return count;
            }
        }
            return count;
    }
}

59. 螺旋矩阵 II

给定一个正整数 n,生成一个包含 1 到 n2 全部元素,且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 3
输出:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] arr = new int[n][n];
        int c = 1, j = 0;
        while (c <= n * n) {

            for (int i = j; i < n - j; i++)
                arr[j][i] = c++;
            for (int i = j + 1; i < n - j; i++)
                arr[i][n - j - 1] = c++;
            for (int i = n - j - 2; i >= j; i--)
                arr[n - j - 1][i] = c++;
            for (int i = n -j - 2; i > j; i--)
                arr[i][j] = c++;

            j++;
        }

        return arr;
    }

}

60. 第k个排列

给出集合 [1,2,3,…,n],其全部元素共有 n! 种排列。

按大小顺序列出全部排列状况,并一一标记,当 n = 3 时, 全部排列以下:

"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k,返回第 k 个排列。

说明:

给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。
示例 1:

输入: n = 3, k = 3
输出: "213"
示例 2:

输入: n = 4, k = 9
输出: "2314"

PS:
直接用回溯法作的话须要在回溯到第k个排列时终止就不会超时了, 可是效率依旧感人
能够用数学的方法来解, 由于数字都是从1开始的连续天然数, 排列出现的次序能够推
算出来, 对于n=4, k=15 找到k=15排列的过程:

    1 + 对2,3,4的全排列 (3!个)         
    2 + 对1,3,4的全排列 (3!个)         3, 1 + 对2,4的全排列(2!个)
    3 + 对1,2,4的全排列 (3!个)-------> 3, 2 + 对1,4的全排列(2!个)-------> 3, 2, 1 + 对4的全排列(1!个)-------> 3214
    4 + 对1,2,3的全排列 (3!个)         3, 4 + 对1,2的全排列(2!个)         3, 2, 4 + 对1的全排列(1!个)

    肯定第一位:
        k = 14(从0开始计数)
        index = k / (n-1)! = 2, 说明第15个数的第一位是3 
        更新k
        k = k - index*(n-1)! = 2
    肯定第二位:
        k = 2
        index = k / (n-2)! = 1, 说明第15个数的第二位是2
        更新k
        k = k - index*(n-2)! = 0
    肯定第三位:
        k = 0
        index = k / (n-3)! = 0, 说明第15个数的第三位是1
        更新k
        k = k - index*(n-3)! = 0
    肯定第四位:
        k = 0
        index = k / (n-4)! = 0, 说明第15个数的第四位是4
    最终肯定n=4时第15个数为3214 
class Solution {
    public String getPermutation(int n, int k) {

        StringBuilder sb = new StringBuilder();
        // 候选数字
        List<Integer> candidates = new ArrayList<>();
        // 分母的阶乘数
        int[] factorials = new int[n+1];
        factorials[0] = 1;
        int fact = 1;
        for(int i = 1; i <= n; ++i) {
            candidates.add(i);
            fact *= i;
            factorials[i] = fact;
        }
        k -= 1;
        for(int i = n-1; i >= 0; --i) {
            // 计算候选数字的index
            int index = k / factorials[i];
            sb.append(candidates.remove(index));
            k -= index*factorials[i];
        }
        return sb.toString();
    }
}