1. N皇后II（52）
返回N皇后的解集数量
class Solution { public int totalNQueens(int n) { int[] queeens =new int[n]; Arrays.fill(queeens,-1); Set<Integer> cols= new HashSet<>(n); Set<Integer> dia1= new HashSet<>(n); Set<Integer> dia2= new HashSet<>(n); List<Integer> list = new ArrayList<>(); List<List<Integer>> res = new ArrayList<>(); bfs(queeens,cols,dia1,dia2,0,n,list,res); return res.size(); } public void bfs(int[] queeens, Set<Integer> cols,Set<Integer> dia1 ,Set<Integer> dia2,int i,int n,List<Integer> list,List<List<Integer>> res){ if(i==n){ res.add(list); return; }else{ for(int k= 0; k<n;k++){ if(cols.contains(k)){ continue; } int id1 =i-k; if(dia1.contains(id1)){ continue; } int id2 = k+i; if(dia2.contains(id2)){continue;} queeens[i]=k; cols.add(k); dia1.add(id1); dia2.add(id2); list.add(queeens[i]); bfs(queeens,cols,dia1,dia2,i+1,n,list,res); queeens[i]=-1; cols.remove(k); dia1.remove(id1); dia2.remove(id2); list.remove(list.size()-1); } } } }
2. 最大子数组合（53）
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和
class Solution { public int maxSubArray(int[] nums) { int[] dp = new int[nums.length]; dp[0]=nums[0]; for(int i= 1;i<nums.length;i++){ if(dp[i-1]>0) dp[i] = dp[i-1]+nums[i]; else dp[i]=nums[i]; } int max= dp[0]; for(int i= 1;i<nums.length;i++){ if(dp[i]>max){ max = dp[i]; } } return max; } }
3. 螺旋矩阵（54）
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
class Solution { public List<Integer> spiralOrder(int[][] matrix) { if(matrix == null ||matrix.length ==0||matrix[0].length==0) return new ArrayList<>(); ArrayList<Integer> res = new ArrayList<>(); int l=0,r=matrix[0].length-1,u=0,d=matrix.length-1; while (true){ for (int i =l;i<=r;i++) res.add(matrix[u][i]); if(++u>d) break; for (int i =u;i<=d;i++) res.add(matrix[i][r]); if(--r<l) break; for (int i =r;i>=l;i--) res.add(matrix[d][i]); if(--d<u) break; for (int i =d;i>=u;i--) res.add(matrix[i][l]); if(++l>r) break; } return res; } }
4. 跳跃数组（55）
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
class Solution { public boolean canJump(int[] nums) { int maxjump = 0; for (int i = 0; i < nums.length; i++) { if (i <= maxjump) { maxjump = Math.max(maxjump, nums[i] + i); if (maxjump >= nums.length - 1) return true; } } return false; } }
5. 合并区间（56）
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
class Solution { public int[][] merge(int[][] intervals) { if(intervals.length<=1){ return intervals; } Arrays.sort(intervals, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { return o1[0]-o2[0]; } }); List<int[]> res= new ArrayList<>(); for (int i = 0; i <intervals.length ; i++) { if(res.size()==0||intervals[i][0]>res.get(res.size()-1)[1]){ res.add(intervals[i]); }else { res.get(res.size()-1)[1]=Math.max(intervals[i][1], res.get(res.size()-1)[1]); } } return res.toArray(new int[res.size()][2]); } }