leetcode算法题解(Java版)-10-全排列(递归)
一、二维数据 题目描述 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; } } } } 这道全排列的题,还有扩展,明天接着搞~~