LeetCode 剑指Offer38 字符串的排列

题目链接:LeetCode 剑指Offer38 字符串的排列

题目大意:
输入一个字符串,打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。

题解:

回溯

通过搜索和回溯枚举所有的排列情况,但会有重复的情况。
只要在递归函数中设定一个规则,保证在填每一个空位的时候重复字符只会被填入一次。具体地,我们首先对原字符串排序,保证相同的字符都相邻,在递归函数中,我们限制每次填入的字符一定是这个字符所在重复字符集合中“从左往右第一个未被填入的字符”,即如下的判断条件:

if (vis[j] || (j > 0 && !vis[j - 1] && s[j - 1] == s[j])) {
    continue;
}

这个限制条件保证了对于重复的字符,我们一定是从左往右依次填入的空位中的。

class Solution {
private:
    vector<string> ans;
    vector<int> vis;

public:
    void backtrack(const string& s, int i, int n, string& now) {
        if (i == n) {
            ans.push_back(now);
            return;
        }
        for (int j = 0; j < n; j++) {
            if (vis[j] || (j > 0 && !vis[j - 1] && s[j - 1] == s[j])) {
                continue;
            }
            vis[j] = true;
            now.push_back(s[j]);
            backtrack(s, i + 1, n, now);
            now.pop_back();
            vis[j] = false;
        }
    }

    vector<string> permutation(string s) {
        int n = s.size();
        vis.resize(n);
        sort(s.begin(), s.end());
        string now;
        backtrack(s, 0, n, now);
        return ans;
    }
};

尺取法

按字典序从小到大寻找字符排列,注意到下一个排列总是比当前排列要大,除非该排列已经是最大的排列。我们希望找到一种方法,能够找到一个大于当前序列的新序列,且变大的幅度尽可能小。具体地:

  1. 我们需要将一个左边的“较小数”与一个右边的“较大数”交换,以能够让当前排列变大,从而得到下一个排列。
  2. 同时我们要让这个“较小数”尽量靠右,而“较大数”尽可能小。当交换完成后,“较大数”右边的数需要按照升序重新排列。这样可以在保证新排列大于原来排列的情况下,使变大的幅度尽可能小。

具体地,我们这样描述该算法,对于长度为\(n\)的排列\(a\)

  1. 首先从后向前查找第一个顺序对\((i,i+1)\),满足\(a[i]<a[i+1]\)。这样“较小数”即为\(a[i]\)。此时\([i+1,n)\)必然是下降序列。
  2. 如果找到了顺序对,那么在区间\([i+1,n)\)中从后向前查找第一个元素\(j\)满足\(a[i]<a[j]\)。这样“较大数”即为\(a[j]\)
  3. 交换\(a[i]\)\(a[j]\),此时可以证明区间\([i+1,n)\)必为降序。我们可以直接使用双指针反转区间\([i+1,n)\)使其变为升序,而无需对该区间进行排序。
class Solution {
public:
    bool nextPermutation(string& s) {
        int i = s.length() - 2;
        while (i >= 0 && s[i] >= s[i + 1]) {
            i--;
        }
        if (i < 0) {
            return false;
        }
        int j = s.length() - 1;
        while (s[i] >= s[j]) {
            j--;
        }
        swap(s[i], s[j]);
        reverse(s.begin() + i + 1, s.end());
        return true;
    }

    vector<string> permutation(string s) {
        vector<string> ans;
        sort(s.begin(), s.end());
        do {
            ans.push_back(s);
        } while (nextPermutation(s));
        return ans;
    }
};

推荐这些文章:

46.全排列

1.Go
方法1: dfs

func permute(nums []int) [][]int {
vis:=make([]int,len(nums))
ans:=[][]int{}
v:=[]int{}
var dfs func(int)
dfs=func(idx int){
if idx==len(nums){
ans = append(ans, append([]int(nil), v...))
return
}

for i:=0;i<len...

树的问题(二)

https://iai.sh.cn/problem/608

#include<stdio.h>
#include<iostream>
#include<cmath>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

const int N = 1e6+10;
typedef long long lld;

vector<vector<int>> links;

int per[N];
int l=0...

生成一组数的子集的组合数和排列数

#include <iostream>
#include <vector>
using namespace std;
int length,n;
vector<vector<int>> ans;

void find(vector<int> &a,vector<int> &t,int index){
if(t.size() == length){ //长度为指定长度时,保存到ans后,返回,结束这一次递归
ans.push_back(t);
return;
...

88.合并两个有序数组

1.Go   2.C++ 方法1:借助新的容器 class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { vector<int>ans; for(int i=0;i<m;i++){ ans.push_back(nums1[i]); } for(int i=0;i<n;i++){ ...

leetcode784. 字母大小写全排列

 
 好久没写了,随便写写吧。
长度不超过12,就可以直接暴力了。

class Solution {
public:
vector<string> ans;
vector<int> ind;
string p;
int dfs(int a){
if (a==ind.size()){
ans.push_back(p);
return 0;
}
string temp=p;
dfs(a+1);
...

vector<vector<int>>初始化

class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

int n=mat.size();
int m=mat[0].size();
vector<vector<int>> ans(n, vector<int>...

2022CCCC天梯赛代码

#include <bits/stdc++.h>
using namespace std;

int main() {
int l, h, a, b;
cin >> l >> h >> a >> b;
if(a >= l && b >= l) {
cout << a << "-Y " << b << "-Y\n";
cout << "huan ying ru guan";
} else if(min(a, b) &...

使用类做为Dictionary<T,K>的key需什么要求?

问题
<P>&nbsp;</P>

最佳回答
没有要求

...

【LeetCode】剑指 Offer II 006. 排序数组中两个数字之和

class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int length=numbers.size();
int left,right,cpl=length-1,m;
int flag=0;
vector<int> ans;
for(int i=0;i<=length/2;++i)
{
left=i+1;
right=cpl;
wh...

<2022年4月13号>

浮动
竖着排列的项目想横排列
float:left
float:right
浮动作用
1.将块元素变成行内块,将行元素变成行内块
标准文档流:在不使用其他与排列和定位相关的css规则时,各个元素排列方式
脱离(标准)文档流
1.浮动
2.定位
3.弹性盒子
预防浮动带来的问题
1.设置父级,设置好宽高
清除浮动
1.clear:both;在被影响的元素上加
2.给父级设置宽高加display:block
3.给父级设置宽高加overflow:hidden;
4.伪类{宽高,display:block; clear:both; overflow:hidden}

...

文章标题:LeetCode 剑指Offer38 字符串的排列
文章链接:https://www.dianjilingqu.com/51469.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>