LeetCode笔记:46. Permutations
2023-03-15 23:22:16 时间
问题:
Given a collection of distinct 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], [3,2,1] ]
大意:
给出一个不同数字的集合,返回所有可能的排列。 比如: [1,2,3] 有下面这些排列: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
思路:
这就是中学时排列组合的题目,要极尽所有排列,我们就要从第一个位置开始所有的元素都有可能放一遍,第二个位置在放了第一个位置的数字后剩下的数字又都可能放一遍,第三个位置也是类似,一直到最后一个位置。
对于这种操作用递归最合适,在我们创建的函数中对于第i个位置,每个当前还剩下的数字都去尝试放一次,并且继续往下递归,最后就会得到所有可能的排列。
要注意的一点就是在递归中我们的List和数组都要进行深拷贝然后添加元素,否则不同的放置方式操作的都是同一个List或者数组,没有意义。
代码(Java):
public class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> resList = new ArrayList<List<Integer>>();
for (int i = 0; i < nums.length; i++) {
List<Integer> list = new ArrayList<Integer>();
list.add(nums[i]);
int[] hasUsed = new int[nums.length];
hasUsed[i] = 1;
doPermute(nums, resList, list, hasUsed);
}
return resList;
}
public void doPermute(int[] nums, List<List<Integer>> resList, List<Integer> list, int[] hasUsed) {
if (list.size() == nums.length) {
resList.add(list);
return;
}
for (int i = 0; i < nums.length; i++) {
if (hasUsed[i] == 0) {
List<Integer> newList = new ArrayList<Integer>();
newList.addAll(list);
newList.add(nums[i]);
int[] newUsed = hasUsed.clone();
newUsed[i] = 1;
doPermute(nums, resList, newList, newUsed);
}
}
}
}
相关文章
- 阿里面试经历及总结(数据研发、Java研发方向)
- 大数据时代,这些专业人才最吃香
- 程序员:增加编程经验的3种途径
- 四项更佳实践让您的云部署准备好迎接GDPR
- Java Socket编程----通信是这样炼成的
- 改善企业业务的6个数据管理技巧
- 从我一年编程生涯中得到的经验教训
- Accordion:HBase的 “呼吸式”内存压缩算法
- 野生程序员的故事
- PHP 不如 C++ 吗?
- PHP 程序员解决问题能力的八个级别
- 什么情况让程序员处于水深火热中
- 华尔街日报畅销书《感知型企业》中文版正式出版
- 浅谈C++设计模式之单例模式
- 对数据科学家来说最重要的算法和统计模型
- 构建自己的PHP框架--搭建基本结构
- 数据可视化项目失败的六大缘由
- 欧盟开枪,谁会成为GDPR的枪下鬼?
- 数据分析驱动企业数字转型 感知型企业催生决策新时代
- 爱上谷歌文档Docs的十大理由