题目出处
- Leetcode 46. 全排列（没有重复）
- Leetcode 47. 全排列 II（包含重复）
- 剑指 Offer - 38 - 字符串的排列
- 面试实际遇到过 - Shopee
字符串的排列
1 题目描述
输入一个字符串，按字典序打印出该字符串中字符的所有排列。例如输入字符串 abc，则打印出由字符 a, b, c 所能排列出来的所有字符串 abc, acb, bac, bca, cab 和 cba。结果请按字母顺序输出。
2 解题思路
2.1 递归算法 DFS
递归法，问题转换为先固定第一个字符，求剩余字符的排列；求剩余字符排列时跟原问题一样。
- 遍历出所有可能出现在第一个位置的字符（即：依次将第一个字符同后面所有字符交换）；
- 固定第一个字符，求后面字符的排列（即：在第1步的遍历过程中，插入递归进行实现）。
需要注意的几点：
- 确定递归结束的条件
- 考虑重复情况
- 考虑输出顺序
import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
public class Solution {
public static void main(String[] args) {
Solution p = new Solution();
System.out.println(p.Permutation("abc").toString());
}
public ArrayList<String> Permutation(String str) {
ArrayList<String> resultList = new ArrayList<>();
if(null != str && str.length() > 0){
backtrack(str.toCharArray(), resultList, 0);
Collections.sort(resultList);
}
return resultList;
}
private void backtrack(char[] ch, List<String> list, int i){
//下标 i 移到 char 数组末尾时，添加这一组字符串进入结果集中，递归终止
if(i == ch.length - 1){
//判断一下是否重复
if(!list.contains(String.valueOf(ch))){
list.add(String.valueOf(ch));
}
}else{
for(int j = i; j < ch.length; j++){
swap(ch, i, j);
backtrack(ch, list, i + 1);
swap(ch, i, j);
}
}
}
private void swap(char[] str, int i, int j) {
if (i != j) {
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}
}
}
复杂性分析
- 时间复杂度：O(N!)<= O(∑{k=1,N},N!/(N−k)!) <=O(N*N!)
- 空间复杂度：O(N!)
2.2 迭代算法：字典生成算法
一个全排列可看做一个字符串，字符串可有前缀、后缀。
生成给定全排列的下一个排列.所谓一个的下一个就是这一个与下一个之间没有其他的。
这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。
例
839647521 是 1—9 的排列。1—9 的排列最前面的是 123456789，最后面的 987654321，从右向左扫描若都是增的，就到了 987654321，也就没有下一个了。否则找出第一次出现下降的位置。
如何得到 346987521 的下一个
- 从尾部往前找第一个 P(i-1) < P(i) 的位置
3 4 6 <- 9 <- 8 <- 7 <- 5 <- 2 <- 1
最终找到 6 是第一个变小的数字，记录下 6 的位置 i-1 - 从 i 位置往后找到最后一个大于 6 的数
3 4 6 -> 9 -> 8 -> 7 5 2 1
最终找到 7 的位置，记录位置为 m - 交换位置 i-1 和 m 的值
3 4 7 9 8 6 5 2 1
- 倒序 i 位置后的所有数据
3 4 7 1 2 5 6 8 9
则 347125689 为 346987521 的下一个排列
public class Solution {
public ArrayList<String> Permutation(String str) {
ArrayList<String> res = new ArrayList<>();
if (str != null && str.length() > 0) {
char[] seq = str.toCharArray();
Arrays.sort(seq); //排列
res.add(String.valueOf(seq)); //先输出一个解
int len = seq.length;
while (true) {
int p = len - 1, q;
//从后向前找一个seq[p - 1] < seq[p]
while (p >= 1 && seq[p - 1] >= seq[p]) --p;
if (p == 0) break; //已经是“最小”的排列，退出
//从p向后找最后一个比seq[p]大的数
q = p; --p;
while (q < len && seq[q] > seq[p]) q++;
--q;
//交换这两个位置上的值
swap(seq, q, p);
//将p之后的序列倒序排列
reverse(seq, p + 1);
res.add(String.valueOf(seq));
}
}
return res;
}
public static void reverse(char[] seq, int start) {
int len;
if(seq == null || (len = seq.length) <= start)
return;
for (int i = 0; i < ((len - start) >> 1); i++) {
int p = start + i, q = len - 1 - i;
if (p != q)
swap(seq, p, q);
}
}
public static void swap(char[] cs, int i, int j) {
char temp = cs[i];
cs[i] = cs[j];
cs[j] = temp;
}
}
全排列
1 题目描述
给定一个没有重复数字的序列，返回其所有可能的全排列。
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
2 解题思路
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> output = new ArrayList<>();
if(nums.length > 0){
// convert nums into list since the output is a list of lists
List<Integer> input = new ArrayList<>();
for(int num : nums){
input.add(num);
}
backtrack(input, 0, output);
}
return output;
}
public void backtrack(List<Integer> input, int first, List<List<Integer>> output){
// if all integers are used up
if(first == input.size()){
output.add(new ArrayList<>(input));
}else{
for(int i = first; i < input.size(); i++){
// place i-th integer first
// in the current permutation
Collections.swap(input, first, i);
// use next integers to complete the permutations
backtrack(input, first + 1, output);
// backtrack
Collections.swap(input, i, first);
}
}
}
}
全排列 II
1 题目描述
给定一个可包含重复数字的序列，返回所有不重复的全排列。
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
2 解题思路
和 46.全排列 的区别是考虑重复，但这是数字不是字符串，比较数字数组的重复比较麻烦，所以考虑在生成过程中就避免重复——在一定会产生重复结果集的地方剪枝。
- 给定数组先排序处理
- 递归中，给 curList 添加元素时，看当前元素是否等于前一元素，如果相等且前一元素还没有被访问过，则跳过当前元素
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;
public class Solution {
public List<List<Integer>> permuteUnique (int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
ArrayList<Integer> curList = new ArrayList<>();
boolean[] visited = new boolean[nums.length];
Arrays.sort(nums);
backtrack(curList, ans, visited, nums);
return ans;
}
/**
* 回溯法
* @param curList 当前正在处理的字符串
* @param permutations 排列组合结果集合
* @param visited 标记当前递归链已经访问过的元素
* @param nums 给定数组
*/
private void backtrack (List<Integer> curList,
List<List<Integer>> permutations,
boolean[] visited,
int[] nums) {
if (curList.size() == nums.length) {
permutations.add(new ArrayList<>(curList));
} else {
for (int i = 0; i < nums.length; i++) {
if (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1]){
continue;
}
if (visited[i]) {
continue;
}
visited[i] = true;
curList.add(nums[i]);
backtrack(curList, permutations, visited, nums);
curList.remove(curList.size() - 1);
visited[i] = false;
}
}
}
}
全排列进阶
1 题目描述
给出从 1 开始递增的整数数组长度 n，求数组的全排列第 k 行的值
2 解题思路
由 k 取余，得到第 k 行应该是在哪个数开头的那几行中，再递归计算