比起http://blog.csdn.net/fightforyourdream/article/details/14217105
多加了一个while来去重,发现这个去重方法在另一道题也用过,同样也是DFS里面去重,很好用!
另外就是在最前面加了一个sort,因为如果没加,当输入乱序时就会Output Limit Exceed!
package Level4;
import java.util.ArrayList;
import java.util.Collections;
/**
* Permutations II
*
* Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].
*
*/
public class S47 {
public static void main(String[] args) {
int[] num = {1,2,1};
System.out.println(permuteUnique(num));
}
public static ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> done = new ArrayList<Integer>();
ArrayList<Integer> rest = new ArrayList<Integer>();
for(int val : num){
rest.add(val);
}
Collections.sort(rest); // 这里要先排序一下。。否则遇到非递增排序的输入就会Output Limit Exceed!
rec2(done, rest, ret);
return ret;
}
public static void rec2(ArrayList<Integer> done, ArrayList<Integer> rest, ArrayList<ArrayList<Integer>> ret){
if(rest.size() == 0){
ret.add(new ArrayList<Integer>(done));
return;
}
for(int i=0; i<rest.size(); i++){
done.add(rest.get(i));
ArrayList<Integer> newRest = new ArrayList<Integer>(rest);
newRest.remove(i);
rec2(done, newRest, ret);
done.remove(done.size()-1);
while(i<rest.size()-1 && rest.get(i)==rest.get(i+1)){
i++;
}
}
}
}
过滤重复元素方法同http://blog.csdn.net/fightforyourdream/article/details/16859111
public class Solution {
public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> done = new ArrayList<Integer>();
ArrayList<Integer> rest = new ArrayList<Integer>();
Arrays.sort(num);
for(int val : num){
rest.add(val);
}
rec(done, rest, ret);
return ret;
}
public void rec(ArrayList<Integer> done, ArrayList<Integer> rest, ArrayList<ArrayList<Integer>> ret){
if(rest.size()==0){
ret.add(new ArrayList<Integer>(done));
return;
}
for(int i=0; i<rest.size(); i++){
int first = rest.remove(i);
done.add(first);
rec(done, rest, ret);
done.remove(done.size()-1);
rest.add(i, first); // insert to its original position
while(i+1<rest.size() && rest.get(i)==rest.get(i+1)){
i++;
}
}
}
}
分享到:
相关推荐
Source file for LeetCode Permutations Problem
数字排列重复数排列Расчётколичествастроквфайлепроизвёлкомандой:.. \ permutations.txt“ |测量对象-线ВWindouse 标题:行字字符属性30240
Given a collection of distinct integers, return all possible permutations. Example: Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 二.解题思路 主要是有两种...
leetcode怎么销号 LeetCode-Solutions :green_heart:My own LeetCode solutions No. Problem LeetCode 力扣 Python Go Solution Difficulty Tag 0017 Letter Combinations of a Phone Number Medium 回溯、暴力 0034...
题型一:经典暴力递归:(里面涉及到重复不重复的时候,需要注意该如何处理!) 模板都是一样的 039:Combination Sum 040:Combination Sum II 046:Permutations 047:Permutations II 051:N-Queens 052:N-...
leetcode 最大连通域leetcode zigzag.py - 字符串“PAYPALISHIRING”在给定的行数上以锯齿形图案书写 delete_dup_nodes.py - 删除所有具有重复编号的节点 topn_toy.py - 来自推文的 Yopn 玩具 僵尸人类.py - 2D 网格...
leetcode题库 Little Algorithm 从 2020 年初开始,我在公众号《面向大象编程》上发表面试算法、LeetCode 题解相关文章,至今收获不少好评。此仓库是公众号内容的补充,包括公众号文章涉及到的题目的参考代码,以及 ...
leetcode 2 LeetCode - 30 Days 前言 相信所有写程式的人在面试前,总是在揣测在白板题会被问到什么问题,而我们最常听到的准备方式就是“刷”。上有数百个可能是面试官问你的题目,我把它想像成考学测或指考前的...
leetcode 轮廓 1_count_and_say.cpp - super_ugly_number.cpp - Detect_Pattern.cpp - degree_of_array.cpp - 键盘.cpp - 2Sum_Data_Structure_Design.cpp - shuffle_array.cpp - permutations.cpp - kth_missing_...
leetcode 分类 LeetCode 152/152 ToDoList -1。 delete int,double最大值 throw error N-queuens ZigZag Conversion SingleNumber 其他算法 各种SingleNumber变种 LinkListCycle I II 其他变种 编程之美 Preorder ...
Richard P. Stanley的经典文章A Survey of Alternating Permutations,供有需要者下载
leetcode双人赛力码 你可以在leetcode中找到一些问题的答案,你可以在leetcode中搜索问题名称,然后就会找到解决方案的代码 leetcode 链接 如果你对我的 leetcode 个人资料感兴趣,你可以去 from math import log ...
题目来源:https://leetcode-cn.com/problems/permutations/ 题目 给定一个 没有重复 数字的序列,返回其所有可能的全排列。 示例: 输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,...
Permutations are ubiquitous in many real-world problems, such as voting, ranking, and data association. Representing uncertainty over permutations is challenging, since there are n! possibilities, and...
leetcode Java 246 題目及解答 (英文) Contents 1 Rotate Array in Java 15 2 Reverse Words in a String II 19 3 Evaluate Reverse Polish Notation 21 4 Isomorphic Strings 25 5 Word Ladder 27 6 Word Ladder ...
给定一个1~N的排列a[i],每次将相邻两个数相加,得到新序列,再对新序列重复这样的操作,显然每次得到的序列都比上一次的序列长度少1,最终只剩一个数字。 例如: 3 1 2 4 4 3 6 7 9 16 现在如果知道N...
AlgoHub囊括了 POJ, ZOJ, leetcode, HackerRank 等网站的经典题目(一些质量不高的题目则忽略),且 AlgoHub有非常简单的加题系统,用户不需要写一行代码即可自己添加题目,所以AlgoHub的题库还在飞速增长中。...
排列数给定集合的大小和有序子集的大小(排列),计算可能的排列数目。安装$ npm install --save permutations-count 用法 var permutationsCount = require ( 'permutations-count' ) ;var numPermutations = ...
2. combinations获取所有的组合情况,permutations可以获取所有的排列情况 3. 限制时间范围 4. 转化为字符型
Leetcode实践在我通过Leetcode工作时记录所有问题和解决方案一些推荐的问题可以在找到目前,问题将按照难度在不同文件夹下进行排序2021-03-20 雅思考试完成。 是时候回到Leetcode了2021-03-23 一些常用的内置函数: ...