51. N 皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

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

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

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

示例：

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

提示：

• 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

class Solution {
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        // 初始化board        for(char[] chs : board) Arrays.fill(chs, '.');
        // 从第一行开始        dfs(board, 0);        return res;    }    void dfs(char[][] board, int row){
        if(row == board.length){            List<String> result = new LinkedList<>();
            for(char[] r: board) result.add(String.valueOf(r));
            res.add(result);            return;        }        int n = board[0].length;
        // 尝试遍历一行的位置放上Q        for(int col = 0; col < n; col ++){
            // 排除无效情况
            if(!valid(board, row , col)) continue;
            // 尝试放皇后
            board[row][col] = 'Q';
            dfs(board, row + 1);
            // 重置
            board[row][col] = '.';
        }
    }
    boolean valid(char[][] board, int row , int col){
        int rows = board.length;
        // 判断列
        for (char[] chars : board) if (chars[col] == 'Q') return false;
        // 判断右对角
        for (int i = row - 1, j = col + 1; i >= 0 && j < rows; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        // 判断左对角
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }        return true;    }}

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 {    int res = 0;    public int totalNQueens(int n) {        char[][] board = new char[n][n];
        // 初始化board        for(char[] chs : board) Arrays.fill(chs, '.');
        // 从第一行开始        dfs(board, 0);        return res;    }    void dfs(char[][] board, int row){
        if(row == board.length){            res ++;            return;        }        int n = board[0].length;
        // 尝试遍历一行的位置放上Q        for(int col = 0; col < n; col ++){
            // 排除无效情况
            if(!valid(board, row , col)) continue;
            // 尝试放皇后
            board[row][col] = 'Q';
            dfs(board, row + 1);
            // 重置
            board[row][col] = '.';
        }
    }
    boolean valid(char[][] board, int row , int col){
        int rows = board.length;
        // 判断列
        for (char[] chars : board) if (chars[col] == 'Q') return false;
        // 判断右对角
        for (int i = row - 1, j = col + 1; i >= 0 && j < rows; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        // 判断左对角
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }        return true;    }}

53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

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

进阶:

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

public int maxSubArray(int[] nums) {
        int res = Integer.MIN_VALUE, prev = 0;
        for(int i = 0; i < nums.length; i++){
            int now = Math.max(prev, 0) + nums[i];
            res = Math.max(now, res);            prev = now;        }        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]

解法一

public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if(matrix == null || matrix.length == 0) return res;        int n = matrix.length, m = matrix[0].length;
        boolean[][] st = new boolean[n][m];
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};
        int x = 0, y = 0, d = 0;        for(int i = 0;i < m * n; i ++){
            res.add(matrix[x][y]);
            st[x][y] = true;
            int a = x + dx[d], b = y + dy[d];
            // 转向的条件 1. 越界 2. 走过
            if( a < 0 || b < 0|| a>= n || b >= m || st[a][b]) {
                d = (d + 1) % 4;                a = x + dx[d]; b = y + dy[d];            }            // 更新下一个点的位置            x = a; y = b;        }        return res;    }

解法二

public List<Integer> spiralOrder(int[][] mat) {
        List<Integer> res = new LinkedList<>();
        if(mat == null || mat.length == 0) return res;                int m = mat.length, n = mat[0].length;
        int l = 0, r = n - 1, t = 0, b = m - 1;        while(l <= r && b >= t){
            for(int i = l; i <= r; i ++) res.add(mat[t][i]);
            t ++;
            for(int i = t; i <= b; i ++) res.add(mat[i][r]);
            r --;
            for(int i = r; i >= l && t <= b; i --) res.add(mat[b][i]);
            b --;
            for(int i = b; i >= t && l <= r; i --) res.add(mat[i][l]);
            l ++;  
        }
        return res;
    }

55. 跳跃游戏

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

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。public boolean canJump(int[] nums) {
        // 能达到的最大下标
        int dist = 0; 
        // 越界或超过能够达到的最大距离跳出循环
        for(int i = 0 ; i< nums.length && i <= dist; i++){
            dist = Math.max(dist,nums[i]+ i);
        }
        // 看看是因为什么原因跳出的循环
        return dist>= nums.length -1;
    }

56. 合并区间

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

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

示例 2:

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

注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。

提示：

• intervals[i][0] <= intervals[i][1]

public int[][] merge(int[][] nums) {
        int len = nums.length;        if(len < 2) return nums;
        // 按照左端点排序
        Arrays.sort(nums, (o1, o2)->(o1[0] - o2[0]));
        // 结果集，每次比较之后，加入一个进结果集        List<int[]> res = new ArrayList<>();
        // 初始化先加入第一个        res.add(nums[0]);
        for(int i = 1; i < len; i ++){
            // 后一个
            int[] curr = nums[i];
            // 前一个
            int[] peek = res.get(res.size() - 1);
            // 前一个的右端点 > 后一个的左端点 -> 没有交叉 直接加入
            if(curr[0] > peek[1]) res.add(curr);
            else{                // 否则直接改变前一个的右端点为两者的最大值即可                peek[1] = Math.max(curr[1], peek[1]);
            }        }        // list -> array        return res.toArray(new int[res.size()][]);
    }

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] 重叠。

注意：输入类型已在 2019 年 4 月 15 日更改。请重置为默认代码定义以获取新的方法签名。

public int[][] insert(int[][] nums, int[] newNum) {
        int newStart = newNum[0], newEnd = newNum[1];
        int idx = 0, n = nums.length;        LinkedList<int[]> res = new LinkedList<>();
        // 将左端点小于newNums左端点的加入res        while(idx < n && newStart > nums[idx][0]) res.add(nums[idx ++]);
        int[] temp = new int[2];
        // res为空或者 没有交点[最后一个右端点 < newNum的左端点]
        if (res.isEmpty() || res.getLast()[1] < newStart) res.add(newNum);
        // 更新res最后一个的右断点 
        else res.getLast()[1] = Math.max(res.getLast()[1], newEnd);
        // 处理剩余的
        while(idx < n){
            // temp就是之后遍历的区间
            temp = nums[idx ++];
            int start = temp[0], end = temp[1];
            // 上一个的右端点小于 下一个的左端点， 没有交集
            if (res.getLast()[1] < start) res.add(temp);
            else res.getLast()[1] = Math.max(res.getLast()[1], end);
        }
        return res.toArray(new int[res.size()][]);
    }

58. 最后一个单词的长度

给定一个仅包含大小写字母和空格 ' ' 的字符串 s，返回其最后一个单词的长度。如果字符串从左向右滚动显示，那么最后一个单词就是最后出现的单词。

如果不存在最后一个单词，请返回 0 。

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

示例:

输入: "Hello World"
输出: 5public int lengthOfLastWord(String s) {
        // s (i,j]  仅包含大小写字母和空格
        int j = s.length() - 1;
        while(j >= 0 && s.charAt(j) == ' ') j --;
        int i = j;
        while(i >= 0 && s.charAt(i) != ' ') i --;
        return j - i; 
    }

59. 螺旋矩阵 II

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

示例:

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

向量位移

public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};
        int x = 0, y = 0, d = 0;        for(int i = 1; i <= n * n; i ++){
            res[x][y] = i;
            int a = x + dx[d], b = y + dy[d];
            // 转向的条件 1. 越界 2. 走过
            if(a < 0 || b < 0 || a >= n || b >= n || res[a][b] != 0){
                d = (d + 1) % 4;                a = x + dx[d]; b = y + dy[d];            }            // 更新下一个点的位置            x = a; y = b;        }        return res;    }

普通模拟

public int[][] generateMatrix(int n) {
        // 设定左、右、上、下边界        int l = 0, r = n - 1, t = 0, b = n - 1;        int[][] res = new int[n][n];
        int num = 1;        while(num <= n * n){
            for(int i = l; i <= r; i++) res[t][i] = num++;
            t++;
            for(int i = t; i <= b; i++) res[i][r] = num++;
            r--;
            for(int i = r; i >= l; i--) res[b][i] = num++;
            b--;            for(int i = b; i >= t; i--) res[i][l] = num++;
            l++;        }        return res;    }

60. 第k个排列

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

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

给定 n 和 k，返回第 k 个排列。

说明：

• 给定 n 的范围是 [1, 9]。
• 给定 k 的范围是[1, n!]。

示例 1:

输入: n = 3, k = 3
输出: "213"

示例 2:

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

回溯法

class Solution {
    boolean[] used; // 记录数字是否用过
    int[] factorial; //阶乘数组
    int n , k;
    public String getPermutation(int n, int k) {
        // 初始化操作
        this.n = n;        this.k = k;        calculateFactorial(n);        used = new boolean[n + 1];
        StringBuilder path = new StringBuilder();        dfs(path, 0);
        return path.toString();
    }    void dfs(StringBuilder path, int u){
        if(u == n) return;
        // 还未确定的数字的全排列个数
        int cnt = factorial[n - 1 - u];
        for(int i = 1; i <= n; i ++){
            if(used[i]) continue;
            if(cnt < k){
                k -= cnt;                continue;
            }            path.append(i);            used[i] = true;            dfs(path , u + 1);
            // return 后续没有必要再遍历了
            return;
        }    }    // 计算阶乘数组    void calculateFactorial(int n){
        factorial = new int[n + 1];
        factorial[0] = 1;
        for(int i = 1; i <= n; i++) factorial[i] = factorial[i - 1] * i;
    }}

数学模拟

public class Solution {
    public String getPermutation(int n, int k) {
        // 注意：相当于在 n 个数字的全排列中找到下标为 k - 1 的那个数，因此 k 先减 1
        k --;        int[] factorial = new int[n];
        factorial[0] = 1;
        // 先算出所有的阶乘值
        for (int i = 1; i < n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }        // 这里使用数组或者链表都行        List<Integer> nums = new LinkedList<>();        for (int i = 1; i <= n; i++) {
            nums.add(i);        }        StringBuilder stringBuilder = new StringBuilder();        // i 表示剩余的数字个数，初始化为 n - 1
        for (int i = n - 1; i >= 0; i--) {
            int index = k / factorial[i] ;
            stringBuilder.append(nums.remove(index));
            k -= index * factorial[i];
        }        return stringBuilder.toString();
    }}

原文链接：https://www.cnblogs.com/summerday152/p/13789588.html

如果觉得本文对你有帮助，可以点赞关注支持一下，也可以关注我公众号，上面有更多技术干货文章以及相关资料共享，大家一起学习进步！