11.7打卡

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]);
    }
}