您现在的位置是:首页 > 文章详情

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

日期:2018-05-05点击:383

一、二维数据

题目描述

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

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

原文链接:https://yq.aliyun.com/articles/590428
关注公众号

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。

持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。

文章评论

共有0条评论来说两句吧...

文章二维码

扫描即可查看该文章

点击排行

推荐阅读

最新文章