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

解法二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. 跳跃游戏给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
【技术干货（四）「LeetCode」51 - 60题详解】示例 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日更改。请重置默认代码定义以获取新方法签名。
提示：

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 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 -> arrayreturn 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 res = new LinkedList<>();// 将左端点小于newNums左端点的加入reswhile(idx < nint[] 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 >= 0int i = j;while(i >= 0return j - i;}

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