leetcode算法题解(Java版)-10-全排列(递归)

  1. 云栖社区>
  2. 博客>
  3. 正文

leetcode算法题解(Java版)-10-全排列(递归)

kissjz 2018-05-06 21:28:18 浏览2893
展开阅读全文

一、二维数据

题目描述

You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up:
Could you do this in-place?
思路

  • 最简单的方法就是在开一个新二维数组tem,然后实行“旋转操作”
  • 这样,不符合题意!要在同一个数组中进行!

代码

public class Solution {
    public void rotate(int[][] matrix) {
        int [][] tem=new int [matrix.length][matrix.length];
        for(int i=0;i<tem.length;i++){
            for(int j=0;j<tem.length;j++){
                tem[j][tem.length-1-i]=matrix[i][j];
            }
        }
        for(int i=0;i<tem.length;i++){
            for(int j=0;j<tem.length;j++){
                matrix[i][j]=tem[i][j];
            }
        }
    }
}

思路二

  • 画一条从左上角到右下角的对角线,这时候矩阵被分成了两份,然后将左下角那部分和右上角那部分的处于对称位置的对调。
  • 然后将列水平对称位置对调,即为所求!
  • 听着有点懵的话,不妨在纸上试试。

代码

public class Solution {
    public void rotate(int[][] matrix) {
        int len=matrix.length;
        int tem;
        for(int i=0;i<len;i++){
            for(int j=0;j<i;j++){
                tem=matrix[i][j];
                matrix[i][j]=matrix[j][i];
                matrix[j][i]=tem;
            }
        }
        for(int i=0;i<len;i++){
            for(int j=0;j<len/2;j++){
                tem=matrix[i][j];
                matrix[i][j]=matrix[i][len-1-j];
                matrix[i][len-1-j]=tem;
            }
        }
    }
}

二、全排列(深搜)

题目描述

Given a collection of numbers, return all possible permutations.
For example,
[1,2,3]have the following permutations:
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], and[3,2,1].

思路

  • 找全排列,典型的深搜题。
  • 语法点:res.add(new ArrayList<Integer>(list));不要忘了加new ArrayList<Integer>不加就通过不了,虽然不明白为什么要加上。

代码


import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
        int len=num.length;
        if(num==null||len==0){
            return res;
        }
        boolean [] visit=new boolean [len];
        ArrayList<Integer> list=new ArrayList<>();
        dfs(num,list,visit,res);
        return res;
    }
    public void dfs(int [] num,ArrayList<Integer> list,boolean [] visit,ArrayList<ArrayList<Integer>> res){
        if(list.size()==num.length){
            res.add(new ArrayList<Integer>(list));
            return ;
        }
        for(int i=0;i<num.length;i++){
            if(!visit[i]){
                visit[i]=true;
                list.add(num[i]);
                dfs(num,list,visit,res);
                list.remove(list.size()-1);
                visit[i]=false;
            }
        }
    }
}

这道全排列的题,还有扩展,明天接着搞~~

网友评论

登录后评论
0/500
评论
kissjz
+ 关注