文档章节

Leetcode 46 全排列 简单思路以及解法

 孤独的岛_Bin
发布于 2018/08/07 15:30
字数 697
阅读 891
收藏 0

Leetcode 46 全排列 简单思路以及解法

题目如下:

给定一个没有重复数字的序列,返回其所有可能的全排列。

示例:

输入: [1,2,3]

输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

思路:

    拿到题目的时候,看到示例输出,就想着试下回溯解法,采用一个全局的 boolean 数组标识数组中哪些元素被访问过了,递归地产生解集。代码如下:

class Solution {
    List<List<Integer>> res;// 存放结果的对象
    public List<List<Integer>> permute(int[] nums) {
        res = new ArrayList<List<Integer>>();
        DFS(nums,initializeBooleanArray(nums.length),new ArrayList<Integer>());// 收集全排列的所有排列结果
        return res;
    }
    
    // 循环选择固定哪一个数字(选择哪一个作为起始数字)
    public void DFS(int[] nums,boolean[] visited,List<Integer> tmp){
        // 如果tmp中存放的数字已经将所有nums中的数字都放入了,那么就将其输入到res中
        if(tmp.size()==nums.length)
            res.add(new ArrayList<Integer>(tmp));
        else{
            // 否则,开始循环遍历,按照0,1,2..的顺序依次选择起点,然后遍历
            for(int i=0;i<nums.length;i++){
                if(visited[i])// 若该点已经被访问过了,则跳过访问下一个点
                    continue;
                else{// 若没被访问过,那么先标记为访问了,然后将其加入tmp中,等待tmp长度足够时写入res中
                    visited[i] = true;
                    tmp.add(nums[i]);
                    DFS(nums,visited,tmp);// 递归调用,通过形参维护的 逻辑栈的变量有:tmp,visited
                    tmp.remove(tmp.size()-1);// 递归结束,还原该点的状态,使得获取下一个组合的遍历还能再经过此点
                    visited[i]=false;// 访问标记还原
                }
            }
        }
    }
    
    // 获取一个与num相等大小的boolean数组
    public boolean[] initializeBooleanArray(int num){
        boolean[] res = new boolean[num];
        for(int i=0;i<num;i++){
            res[i] = false;
        }
        return res;
    }
}

    顺便看了下网上的dalao们的解法,发现有个比较热的解法是交换解法,每次将数与后面的一位进行交换。当交换到最后一位的时候,就将此时的解算入解集中。

    代码如下:

public class Solution {
    
    List<List<Integer>> res;
    
    public List<List<Integer>> permute(int[] nums) {
        res = new LinkedList<List<Integer>>();
        helper(nums, 0);
        return res;
    }
    
    public void helper(int[] nums, int i){
        // 找到转置完成后的解,将其存入列表中
        if(i == nums.length - 1){
            List<Integer> list = new LinkedList<Integer>();
            for(int j = 0; j < nums.length; j++){
                list.add(nums[j]);
            }
            res.add(list);
        }
        // 将当前位置的数跟后面的数交换,并搜索解
        for(int j = i; j < nums.length; j++){
            swap(nums, i , j);
            helper(nums, i + 1);
            swap(nums, i, j);
        }
    }
    
    private void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

© 著作权归作者所有

粉丝 2
博文 37
码字总数 26227
作品 0
开封
私信 提问
LeetCode - 027 - 移除元素(remove-element)

Create by jsliang on 2019-06-06 15:56:49 Recently revised in 2019-06-10 07:42:46 为方便小伙伴们的查看,欢迎切换到不同地址~ 文档库 LeetCode 系列 GitHub 地址 文档库 LeetCode 系列 ...

jsliang
06/10
0
0
Leetcode日记7

(2015/1/2) LeetCode 318 Maximum Product of Word Lengths 题目: 1)求一个字符串数组中,两个不同的字符串的长度乘积的最大值。 2)这两个字符串不能共同拥有同一个字符。(两个字符串的...

fxdhdu
2016/01/03
50
0
LeetCode - 026 - 删除排序数组中的重复项(remove-duplicates-from-sorted-array)

Create by jsliang on 2019-06-06 11:11:26 Recently revised in 2019-06-06 14:30:57 为方便小伙伴们的查看,欢迎切换到不同地址~ 文档库 LeetCode 系列 GitHub 地址 文档库 LeetCode 系列 ...

jsliang
06/07
0
0
LeetCode - 001 - 两数之和(two-sum)

Create by jsliang on 2019-05-16 22:19:13 Recently revised in 2019-05-17 14:22:40 Hello 小伙伴们,如果觉得本文还不错,记得给个 star , 小伙伴们的 star 是我持续更新的动力!GitHub ...

jsliang
05/17
0
0
LeetCode.1051-身高检查器(Height Checker)

这是小川的第390次更新,第420篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第252题(顺位题号是1051)。要求学生按身高递增的顺序站列来拍年度照片。 返回没有站在正确位置...

程序员小川
07/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

golang-字符串-地址分析

demo package mainimport "fmt"func main() {str := "map.baidu.com"fmt.Println(&str, str)str = str[0:5]fmt.Println(&str, str)str = "abc"fmt.Println(&s......

李琼涛
今天
4
0
Spring Boot WebFlux 增删改查完整实战 demo

03:WebFlux Web CRUD 实践 前言 上一篇基于功能性端点去创建一个简单服务,实现了 Hello 。这一篇用 Spring Boot WebFlux 的注解控制层技术创建一个 CRUD WebFlux 应用,让开发更方便。这里...

泥瓦匠BYSocket
今天
6
0
从0开始学FreeRTOS-(列表与列表项)-3

FreeRTOS列表&列表项的源码解读 第一次看列表与列表项的时候,感觉很像是链表,虽然我自己的链表也不太会,但是就是感觉很像。 在FreeRTOS中,列表与列表项使用得非常多,是FreeRTOS的一个数...

杰杰1号
今天
8
0
Java反射

Java 反射 反射是框架设计的灵魂(使用的前提条件:必须先得到代表的字节码的 Class,Class 类 用于表示.class 文件(字节码)) 一、反射的概述 定义:JAVA 反射机制是在运行状态中,对于任...

zzz1122334
今天
6
0
聊聊nacos的LocalConfigInfoProcessor

序 本文主要研究一下nacos的LocalConfigInfoProcessor LocalConfigInfoProcessor nacos-1.1.3/client/src/main/java/com/alibaba/nacos/client/config/impl/LocalConfigInfoProcessor.java p......

go4it
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部