3/12

46 全排列

ps:
new ArrayList<>()时可以传入的参数类型为：
1、int整型。规定arraylist的初始长度。
2、构造一个包含指定Collection的元素的集合，这些元素时按照collection的迭代器返回他们的顺序排列的。

用res.add(new linkedList(path))而不是res.add(path)。因为path指向的对象在不断地增加和删除元素，最后会变成空。得到的结果会变成[[][][][][]]所以要用new linkedList(path)拷贝一个对象加入res
new ArrayList(你的一维数组)相当于给你的一维数组取了个快照。
我们需要的是其中的在某个特定时期的内容，所以一定要进行拷贝。

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res=new ArrayList<>();
        List<Integer> path=new ArrayList<>();
        boolean[] visited=new boolean[nums.length];
        dfs(res,path,visited,nums,0);
        return res;
    }
    void dfs(List<List<Integer>> res,List<Integer> path,boolean[] visited,int[] nums,int index){
        if(index==nums.length){
            // for(Integer i:path){
            //     System.out.println(i);
            // }
            //为什么res.add(path)
            //用了之后是[][][][][][]
            res.add(new ArrayList<>(path));
        
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(!visited[i]){
                path.add(nums[i]);
                visited[i]=true;
                dfs(res,path,visited,nums,index+1);
                visited[i]=false;
                path.remove(index);
            }
            
        }
        return;
    }
}

48 旋转图像

不会

56 合并区间

查了一堆资料才勉勉强强写出来写得很慢本质等于不会而且bug是参考别人才找出来的

class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals==null || intervals.length<=1) return intervals;
        List<int[]> ans=new ArrayList<>();
        Arrays.sort(intervals, new Comparator<int[]>() {//!
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        }); 
        for(int i=0;i<intervals.length;){//i<intervals.length才对!不是小于len-1
            int r=intervals[i][1],l=intervals[i][0];
            while(i<intervals.length-1 && r>=intervals[i+1][0]){//是r>= 不是<
                r=Math.max(intervals[i+1][1],r);//!!!一定要取max
                i++;
            }
            ans.add(new int[]{l,r});
            i++;//!!!勿忘
        }
        // int[][] res=new int[ans.size()][2];
        // for(int i=0;i<ans.size();i++){
        //     res[i]=ans.get(i);
        // }
        // return res;
        return ans.toArray(new int[ans.size()][2]);
//两种方法都可以
    }
}

62

思路1:dfs
超时

class Solution {
    int ans=0;
    public int uniquePaths(int m, int n) {
        dfs(0,0,m,n);
        return ans;
    }
    void dfs(int x,int y,int m,int n){
        if(x==m-1&&y==n-1){
            ans++;
            return;
        }
        if(x<m-1){
            dfs(x+1,y,m,n);
        }
        if(y<n-1){
            dfs(x,y+1,m,n);
        }
    }
}

不要动不动就想着dfs暴力，就算暴力，想一想可否剪枝。或者这是dp么？

思路2:dp

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp=new int[m][n];
        for(int i=0;i<n;i++){
            dp[0][i]=1;
        }
        for(int i=0;i<m;i++){
            dp[i][0]=1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

64 最小路径和