技术干货（四）「LeetCode」51 - 60题详解( 二 ) 51.N皇后n皇后问题研究的是如何将n个皇

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 spiralOrder(int[][] matrix) {List 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 spiralOrder(int[][] mat) {List 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 <= ri <= 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 >= li --) res.add(mat[b][i]);b --;for(int i = b; i >= ti --) 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.lengthi++){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日更改。请重置默认代码定义以获取新方法签名。