leetcode刷题(51-60)

算法是码农的基本功，也是各个大厂必考察的重点，让我们一起坚持写题吧。

遇事不决，可问春风，春风不语，即是本心。

我们在我们能力范围内，做好我们该做的事，然后相信一切都事最好的安排就可以啦，慢慢来，会很快，向前走，别回头。

目录

1、N皇后

2、N皇后II

3、最大子数组和

4、螺旋矩阵

5、跳跃游戏

6、合并区间

7、插入区间

8、最后一个单词的长度

9、螺旋矩阵II

10、排列序列

1、N皇后

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/n-queens/description/思路：回溯标记法，用三个集合标记在列、主对角线、副对角线是否出现过，标记数组标记每行皇后所在的列，递归生成N皇后即可。

class Solution { public List<List> solveNQueens(int n) { // 三个集合，用于标记每一列、主对角线、副对角线有没有放置皇后 Set column = new HashSet() ; Set left = new HashSet() ; Set right = new HashSet() ; List<List> ans = new ArrayList() ; // 标记数组，用于标记每一行皇后所在的列 int [] queues = new int [n] ; Arrays.fill(queues, -1) ; dfs(0,n,queues,column,left,right,ans) ; return ans ; } public void dfs(int row, int n, int [] queues, Set column, Set left, Set right, List<List> ans){ if(row == n){ List list = new ArrayList() ; list = genList(queues,n) ; ans.add(new ArrayList(list)) ; }else{ for(int i=0; i<n; i++){ if(column.contains(i)){  continue ; } if(left.contains(row-i)){  continue ; } if(right.contains(row+i)){  continue ; } queues[row] = i ; column.add(i) ; left.add(row - i) ; right.add(row + i) ; dfs(row+1,n,queues, column, left, right, ans) ; queues[row] = -1 ; column.remove(i) ; left.remove(row - i) ; right.remove(row + i) ; } } } public List genList(int [] queues, int n){ List list = new ArrayList() ; for(int i=0; i<n; i++){ char [] c = new char [n] ; Arrays.fill(c,\'.\') ; c[queues[i]] = \'Q\' ; String str = new String(c) ; list.add(str) ; } return list ; }}

2、N皇后II

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/n-queens-ii/description/

思路：这题的解题思路和上一题类似，回溯标记法，每次找出一个方案，就累计一次即可。

class Solution { public int totalNQueens(int n) { Set coulumn = new HashSet() ; Set left = new HashSet() ; Set right = new HashSet() ; return dfs(0,n,coulumn,left,right) ; } public int dfs(int row, int n, Set coulumn, Set left, Set right){ if(row == n){ return 1 ; } int cnt = 0 ; for(int i=0; i<n; i++){ if(coulumn.contains(i)){  continue ; } if(left.contains(row - i)){  continue ; } if(right.contains(row + i)){  continue ; } coulumn.add(i) ; left.add(row - i) ; right.add(row + i) ; cnt += dfs(row + 1, n, coulumn, left, right) ; coulumn.remove(i) ; left.remove(row - i) ; right.remove(row + i) ; } return cnt ; }}

3、最大子数组和

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/maximum-subarray/

思路：本质上是一种贪心策略，当前累加的和大于0，就继续累加，否则不累加，整个过程中计算最大值即可。

class Solution { public int maxSubArray(int[] nums) { int max = Integer.MIN_VALUE ; int sum = 0 ; for(int i=0; i= 0 ? sum + nums[i] : nums[i]) ; max = Math.max(max, sum) ; } return max ; }}

4、螺旋矩阵

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/spiral-matrix/

思路：top和bottom模拟上下的位置，left和right模拟左右的位置，在while循环里面，使用for循环模拟顺时针打印矩阵元素。

class Solution { public List spiralOrder(int[][] matrix) { List ans = new ArrayList() ; // 模拟旋转过程 int top = 0, bottom = matrix.length-1, left = 0, right = matrix[0].length-1; while(true){ for(int i=left; i bottom){ break ; } for(int i=top; i right){ break ; } for(int i=right; i>=left; i--){ ans.add(matrix[bottom][i]) ; } bottom -- ; if(top > bottom){ break ; } for(int i=bottom; i>=top; i--){ ans.add(matrix[i][left]) ; } left ++ ; if(left > right){ break ; } } return ans ; } }

5、跳跃游戏

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/jump-game/description/

思路：从后向前反退，用step进行标记，step初始化为1，不能跳到当前步，则step+1，否则step更新为1，最后step为1，则表示可以由最初位置跳到最后。

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

6、合并区间

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/merge-intervals/

思路：首先需要进行排序，区间的最左侧元素进行排序，然后以此对比当前区间的右侧和下一个区间的左侧元素，决定是否进行合并区间。

当前区间右侧元素 < 下一区间左侧元素。无重叠，直接加入集合

反之，合并区间：注意合并区间，是选择右侧元素的最大值。

class Solution { public int[][] merge(int[][] intervals) { List list = new ArrayList() ; Arrays.sort(intervals, new Comparator(){ public int compare(int [] o1, int [] o2){ return o1[0] - o2[0] ; } }) ; for(int i=0; i<intervals.length; i++){ int left = intervals[i][0], right = intervals[i][1] ; if(list.size() == 0 || list.get(list.size()-1)[1] < left){ list.add(new int []{left, right}) ; }else{ // 合并区间 list.get(list.size()-1)[1] = Math.max(list.get(list.size()-1)[1], right) ; } } int [][] res = new int [list.size()][2] ; for(int i=0; i<list.size(); i++){ res[i][0] = list.get(i)[0] ; res[i][1] = list.get(i)[1] ; } return res ; }}

7、插入区间

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/insert-interval/description/

思路：和上面一题的思路一致，唯一的区别就是开辟一个新数组，将两个数组合并到新数组，然后在进行合并合并区间。

class Solution { public int[][] insert(int[][] intervals, int[] newInterval) { int [][] tmp = new int [intervals.length+1][2] ; for(int i=0; i<intervals.length; i++){ tmp[i][0] = intervals[i][0] ; tmp[i][1] = intervals[i][1] ; } tmp[tmp.length-1][0] = newInterval[0] ; tmp[tmp.length-1][1] = newInterval[1] ; List list = new ArrayList() ; Arrays.sort(tmp, new Comparator(){ public int compare(int [] o1, int [] o2){ return o1[0] - o2[0] ; } }) ; for(int i=0; i<tmp.length; i++){ int left = tmp[i][0], right = tmp[i][1] ; if(list.size()==0 || list.get(list.size()-1)[1] < left){ list.add(new int []{left, right}) ; }else{ list.get(list.size()-1)[1] = Math.max(list.get(list.size()-1)[1], right) ; } } int [][] res = new int [list.size()][2] ; for(int i=0; i<res.length; i++){ res[i][0] = list.get(i)[0] ; res[i][1] = list.get(i)[1] ; } return res ; }}

8、最后一个单词的长度

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/length-of-last-word/

思路：先删除前后的空格，然后从后向前判断，不等于空格，计数器加1，等于空格结束。

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

9、螺旋矩阵II

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/spiral-matrix-ii/description/

思路：和螺旋矩阵I的思路一样，只不是这是新建一个数组进行模拟而已，本质上都是定义上下左右四个边界，模拟顺时针旋转并更新四个边界值。

class Solution { public int[][] generateMatrix(int n) { int [][] res = new int [n][n] ; int left = 0, right = n-1, top = 0, bottom = n-1 ; int v = 1 ; while(true){ for(int i=left; ibottom){ break ; } for(int i=top; i right){ break ; } for(int i=right; i>=left; i--){ res[bottom][i] = v ++ ; } bottom -- ; if(top > bottom){ break ; } for(int i=bottom; i>=top; i--){ res[i][left] = v ++ ; } left ++ ; if(left > right){ break ; } } return res ; }}

10、排列序列

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/permutation-sequence/description/

思路：全排列+根据字符串进行排序即可。

class Solution { public String getPermutation(int n, int k) { String s = \"\" ; for(int i=1; i<=n; i++){ s+= i ; } List list = new ArrayList() ; boolean [] vis = new boolean[n] ; dfs(list,s,n, new StringBuilder(\"\"), vis) ; Collections.sort(list) ; return list.get(k-1) ; } public void dfs(List list, String s, int n, StringBuilder sb, boolean [] vis){ if(sb.length() == n){ list.add(sb.toString()) ; } for(int i=0; i<n; i++){ if(vis[i]){ continue ; } vis[i] = true ; sb.append(s.charAt(i)) ; dfs(list, s, n, sb, vis) ; sb.deleteCharAt(sb.length()-1) ; vis[i] = false ; } }}