LeetCode46. 全排列

 标准dfs问题,只不过这道题有点麻烦在于返回的是一个List嵌套List  声明一些变量,首先是ans保存最终结果,其次是path[],存储当前选取的元素的下标,然后是boolean v[],保存元素中某个下标的值是否用过,默认值是false,用过就置为true  dfs函数中首先进行边界条件判断,如果到了边界,就将所有保存在path中的下标对应的nums[]的值赋给一个List,然后return。其次i从0到nums.length枚举每一个下标,先进行判断,没有选过才选,将i的值给到path[idx],然后将当前的v[i]置为ture,在进行下一层的dfs(idx + 1,nums),最后是回溯,将v[i]变为false

class Solution {
    public static List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public static int[] path = new int[100];
    public static boolean[] v = new boolean[100];
    public static void dfs(int idx,int[] nums) {
        if(idx >= nums.length) {
            List<Integer> tmp = new ArrayList<Integer>();
            for(int i = 0;i < nums.length;i++)
                tmp.add(nums[path[i]]);
            ans.add(tmp);
            return;
        }
        for(int i = 0;i < nums.length;i++) {
            if(!v[i]) {
                path[idx] = i;
                v[i] = true;
                dfs(idx + 1,nums);
                v[i] = false;
            }
        }
    }
    public List<List<Integer>> permute(int[] nums) {
        ans.clear();
        dfs(0,nums);
        return ans;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏决胜机器学习

PHP数据结构(二十四) ——堆排序

PHP数据结构(二十四)——堆排序 (原创内容,转载请注明来源,谢谢) 一、定义 堆排序也属于一种选择排序,效率较高且空间占用相对较少。 堆的定义:n个元...

39390
来自专栏Java架构

面试必备:30 个 Java 集合面试问题及答案

Java集合框架为Java编程语言的基础,也是Java面试中很重要的一个知识点。这里,我列出了一些关于Java集合的重要问题和答案。

8220
来自专栏书山有路勤为径

插入位置

给定一个排序数组nums(无重复元素)与目标值target,如果target在nums里 出现,则返回target所在下标,如果target在nums里未出现,...

9530
来自专栏Java后端技术

Java Collection、Map集合总结

      依赖hashCode()和equals()两个方法进行保证元素唯一性,开发中使用开发工具自动生成就好。

9520
来自专栏用户3030674的专栏

java 集合框架(List操作)

/*list 基本操作 * * List a=new List(); * 增 * a.add(index,element);按指定位置添加,其余元素...

13710
来自专栏数说戏聊

SUBSTRING() 与 CONV() 函数1.substring()函数2.conv()函数

MySQL 字符串截取函数:left(), right(), substring(), substring_index()。

9020
来自专栏测试开发架构之路

总结了一些指针易出错的常见问题(四)

指针与结构体 简介:我们可以使用C的结构体来表示数据结构元素,比如链表或树的节点,指针是把这些元素联系到一起的纽带。 typedef struct _pers...

29970
来自专栏顶级程序员

说出来你们可能不信,但是数组名确实不是指针常量

这篇是一篇C语言劝退流教学文,看不懂的同学应该是劝退教学流的目标对象 (写完了才想起来注一下,本文提到的“数组”和“数组名”字样,指的是数组左值表达式(arr...

40160
来自专栏SpringBoot

java遍历List的三种方法

13010
来自专栏Java帮帮-微信公众号-技术文章全总结

Java面试系列7

Java面试系列7 1.HashMap和Hashtable的区别。 HashMap是Hashtable的轻量级实现(非线程安全的实现),二者都实现了Map 接...

31740

扫码关注云+社区

领取腾讯云代金券