问题描述:
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]
, and [3,2,1]
.
原问题链接:https://leetcode.com/problems/permutations/
问题分析
这个问题可以归结为典型的排列问题。在之前的一篇文章里有过详细的讨论。 在前面的文章里,我们提到的字典序排列的方法就可以很好的解决这个问题。在每次生成字典序的排列最后我们将这个序列加入到List里面,这样就可以得到所有的排列生成列表。
而字典序排列的过程概括起来就是如下这么个步骤:
- 找最后面的连续递增点。
- 根据找到的点后面找最接近的大于它的元素。
- 倒置后面序列里的元素。
详细实现见如下代码:
public class Solution { public List<List<Integer>> permute(int[] num) { Arrays.sort(num); List<List<Integer>> lists = new ArrayList<List<Integer>>(); lists.add(appendList(num)); while(true) { int start = findStart(num); if(start == -1) break; int end = findEnd(num, start); if(end == -1) break; swap(num, start, end); reverse(num, start + 1, num.length - 1); lists.add(appendList(num)); } return lists; } private List<Integer> appendList(int[] num) { List<Integer> list = new ArrayList<Integer>(); for(int i = 0; i < num.length; i++) list.add(num[i]); return list; } private int findStart(int[] num) { for(int i = num.length - 2; i >= 0; i--) if(num[i] < num[i + 1]) return i; return -1; } private int findEnd(int[] num, int l) { for(int i = num.length - 1; i > l; i--) if(num[i] > num[l]) return i; return -1; } private void reverse(int[] num, int l, int r) { while(l < r) { swap(num, l, r); l++; r--; } } private void swap(int[] num, int i, int j) { int temp = num[i]; num[i] = num[j]; num[j] = temp; } }
相关推荐
permutations2.py - 返回所有可能的唯一排列 3sum_2.py - 查找数组中所有唯一的三元组,其总和为零。 3sum.py - 查找数组中所有唯一的三元组,其总和为零。 first_last_pos_array.py - 找到给定目标值的开始和结束...
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_...
permutations import random import itertools import collections from fractions import Fraction from collections import Counter import operator import re from functools import reduce from collections ...
Permutations (交换 取子集两种方式) Trie树 11 中序遍历 无堆栈 (前序 后序) 12 map边删除 边输出 不太建议这么用。。。 以及其他基本用法 iterate 红黑树 13.set 16.unordered_map 与 map 17.最大m字段和 (动态...
leetcode怎么计算空间复杂度是指 LeetCode-Solution my first solution of LeetCode 2015-5-7 Problem 95,98(80 already!) 我经常在递归的结束地方忘记return!!! 题型一:经典暴力递归:(里面涉及到重复不重复的...
Source file for LeetCode Permutations Problem
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] ] 二.解题思路 主要是有两种...
permutations (normal and better), sum_3.py, unique_paths.py + unique_paths2.py, nQueens.py 很少包含外部库,所以下面的就可以了。 编译任何 C 程序: gcc -o X Xc 执行 python 脚本: chmod 755 X.py --> ....
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...
leetcode 2 LeetCode - 30 Days 前言 相信所有写程式的人在面试前,总是在揣测在白板题会被问到什么问题,而我们最常听到的准备方式就是“刷”。上有数百个可能是面试官问你的题目,我把它...Permutations 目录 ref:
是时候回到Leetcode了2021-03-23 一些常用的内置函数: bin() :信息在collections.Counter :信息在itertools.permutations() :信息在记住,因为它在处理问题时确实可以提供帮助2021-03-24 开始处理HackerRank...
leetcode题库 Little Algorithm 从 2020 年初开始,我在公众号《面向大象编程》上发表面试算法、LeetCode 题解相关文章,至今收获不少好评。此仓库是公众号内容的补充,包括公众号文章涉及到的题目的参考代码,以及 ...
All_Unique_Permutations Best_Time_To_Buy_And_Sell_Stocks_1 Best_Time_To_Buy_And_Sell_Stocks_2 Best_Time_To_Buy_And_Sell_Stocks_3 bst_Iterator 糖果 Character_Precedence Clone_Graph 组合_总和 Counting_...
题目来源: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,...
2. combinations获取所有的组合情况,permutations可以获取所有的排列情况 3. 限制时间范围 4. 转化为字符型
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 ...
AlgoHub囊括了 POJ, ZOJ, leetcode, HackerRank 等网站的经典题目(一些质量不高的题目则忽略),且 AlgoHub有非常简单的加题系统,用户不需要写一行代码即可自己添加题目,所以AlgoHub的题库还在飞速增长中。...