这是给定一个排列，找它的下一个全排列
给出一个数字排列中按字典序排列的下一个更大的排列。如果没有更大的则给出最小的，
比如1,2,3->1,3,2下一个字典序更大的排列是1,3,2，而3,2,1是最大的字典序排列，修改为最小的1,2,3。
解这道题可以通过观察，1,4,3,2 -> 2,1,3,4分为三步：
- 从右往左找到第一个非逆序的，即使得
nums[i] < nums[i+1]成立的 i - 将这个数与后面最后一个比它大的数调换（仅大于它），不能找最后一个，因为最后一个不一定大于它。
- 将这个数后面重新排序,让后面的数为从下到达的顺序，按位交换即可
public void nextPermutation(int[] nums) {
if(nums == null || nums.length <= 1) return;
int i = nums.length - 2;
for(; i >= 0 && nums[i] >= nums[i+1]; --i); //第一步
if(i >= 0){ //否则全部都是递减的，不需要调换了
int j = i+1;
for(; j < nums.length && nums[j] > nums[i]; ++j); //这里是大于，不能加等于
swap(nums, i, j - 1); //第二步
}
int j = nums.length - 1; //因为后面肯定是逆序的，所以直接两点调换即可
for(i = i + 1; i < j; i++,j--){
swap(nums, i, j);
}
}
public void swap(int[] nums, int index1, int index2){
int i = nums[index1];
nums[index1] = nums[index2];
nums[index2] = i;
}
二. 输出一组无重复数字的全排列
这个就是递归回溯求解，深度优先
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList();
helper(nums, new ArrayList<Integer>(), res);
return res;
}
public void helper(int[] nums, List<Integer> list, List<List<Integer>> res){
if(list.size() == nums.length){ // 达到长度，可以输出了
res.add(new ArrayList(list));
}else{
for(int i = 0; i < nums.length; ++i){
if(!list.contains(nums[i])){ //若这个数字已经被包含了，就跳过
list.add(nums[i]);
helper(nums, list, res);
list.remove(list.size() - 1);
}
}
}
}
}
三. 输出一组有重复数字的全排列
需在二的基础上做两点改变：
- 先要对数组排序，以让相同的数字相邻
- 对于相同数字，只考虑第一个的递归，如果前一个数字和当前数字相同且前一个数字还未被使用，则不使用当前数字
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList();
if(nums.length == 0) return res;
Arrays.sort(nums); //先排序
boolean[] used = new boolean[nums.length];
helper(nums, used, new ArrayList<Integer>(), res);
return res;
}
public void helper(int[] nums, boolean[] used, List<Integer> list, List<List<Integer>> res){
if(list.size() == nums.length){
res.add(new ArrayList(list)); //满足结束条件，添加结果
}else{
for(int i = 0; i < nums.length; ++i){
if(i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue; //与前一个相同且前一个还没有被使用时，该数字不使用
if(!used[i]){
list.add(nums[i]);
used[i] = true;
helper(nums, used, list, res);
used[i] = false;
list.remove(list.size() - 1);
}
}
}
}
}
四. 找到第k个全排列
可以直接用回溯，但是效率低
用找规律的方式：
- 先考虑第一位，每个数字后面都有 (n - 1)! 种可能， k / (n-1)! 可以得到第一位是哪个数字
- 移除第一位的数字，同时将 k 更新
- 再考虑第二位，每个数字后面都有(n-2)! 种可能，重复1 2 步骤，直到结束
public String getPermutation(int n, int k) {
List<Integer> idx = new ArrayList(); //index
StringBuilder sb = new StringBuilder();
int fact = 1;
for(int i = 1; i <= n; ++i){
fact *= i;
idx.add(i);
}
for(int i = 0, l = k-1; i < n; ++i){ //注意 k - 1
fact /= n - i;
int index = l / fact;
sb.append(idx.remove(index)); //要把已经添加后的数字删除，这里依然是从小到大的顺序
l -= index * fact; //更新
}
return sb.toString();
}
}
五. 打乱数组
打乱数组也就是相当于任意给出一个全排列中的一个
采用概率的方式：
从左往右到第i位时候，随机选取[0-i]中的一个与第i位置交换
class Solution {
private int[] ori_nums;
private int[] cur_nums;
private Random random;
public Solution(int[] nums) {
this.ori_nums = nums;
cur_nums = nums.clone();
random = new Random();
}
/** Resets the array to its original configuration and return it. */
public int[] reset() {
return ori_nums;
}
/** Returns a random shuffling of the array. */
public int[] shuffle() {
for(int i = 1; i < cur_nums.length; ++i){
int j = random.nextInt(i+1);
if(j != i){
int temp = cur_nums[i];
cur_nums[i] = cur_nums[j];
cur_nums[j] = temp;
}
}
return cur_nums;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(nums);
* int[] param_1 = obj.reset();
* int[] param_2 = obj.shuffle();
*/
六. 一个字符串中是否包含另一个字符串的某一个全排列
也算是一个全排列的问题，这一题揭示了全排列的一个特点：字符类别和每个字符的数量都是相同的，可以类比一个词袋了。
具体分析就点标题链接了，用滑动窗口做
class Solution {
public boolean checkInclusion(String s1, String s2) {
int s1_len = s1.length();
int s2_len = s2.length();
if(s1_len > s2_len) return false;
int[] chCnt = new int[26];
for(int i = 0; i < s1_len; ++i){
chCnt[s1.charAt(i) - 'a'] ++;
chCnt[s2.charAt(i) - 'a'] --;
}
if(isAllZero(chCnt)) return true;
for(int i = s1_len; i < s2_len; ++i){
chCnt[s2.charAt(i) - 'a'] --;
chCnt[s2.charAt(i-s1_len) - 'a'] ++;
if(isAllZero(chCnt)) return true;
}
return false;
}
private boolean isAllZero(int[] chCnt){
for(int i = 0; i < chCnt.length; ++i){
if(chCnt[i] != 0) return false;
}
return true;
}
}
网友评论