糖逗 发表于 2020-4-1 14:28:25

C++刷剑指offer(面试题38. 字符串的排列)【高频】

本帖最后由 糖逗 于 2020-4-12 17:46 编辑

题目描述:
输入一个字符串,打印出该字符串中字符的所有排列。

 

你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。

 

示例:

输入:s = "abc"
输出:["abc","acb","bac","bca","cab","cba"]
 

限制:

1 <= s 的长度 <= 8

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


#include <iostream>
#include <string>
#include <vector>
#include <set>

using namespace std;

void solution(string& input, vector<bool>& visit, set<string>& res, string& temp, int index){
        if(index == input.size()) res.insert(temp);
        for(int i = 0; i < input.size(); i++){
                if(!visit){
                        temp.push_back(input);
                        visit = true;
                        solution(input, visit, res, temp, index+1);
                        temp.erase(temp.end()-1);
                        visit = false;
                }               
        }
}


vector<string> permutation(string input) {
    set<string> res;
        string temp;
        int index = 0;
        vector<bool> visit;
        visit.resize(input.size(), false);
       
        solution(input, visit, res, temp, index);
    return vector<string>(res.begin(), res.end());
}


int main(void){
        string input;
        cin >> input;
       
        vector<string> result = permutation(input);
       
        for(int i= 0; i < result.size(); i++){
                cout << "------------" << endl;
                cout << result << endl;
        }

       
        return 0;
}

注意事项:
1.回溯思想,一般能把问题化成树分支的问题可以试试回溯,回溯涉及到剪枝。
2.参考链接:https://blog.csdn.net/qq_43152052/article/details/104464542
3.参考视频链接:https://www.bilibili.com/video/BV1j7411n7cq?from=search&seid=6093610650574172674
4.代码的思路图如图1

糖逗 发表于 2020-4-1 15:13:08

本帖最后由 糖逗 于 2020-4-12 17:48 编辑

{:10_298:}

糖逗 发表于 2020-4-13 18:31:21

本帖最后由 糖逗 于 2020-4-14 15:39 编辑

相似题型:面试题 08.12. 八皇后
设计一种算法,打印 N 皇后在 N × N 棋盘上的各种摆法,其中每个皇后都不同行、不同列,也不在对角线上。这里的“对角线”指的是所有的对角线,不只是平分整个棋盘的那两条对角线。

注意:本题相对原题做了扩展

示例:

输入:4
输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释: 4 皇后问题存在如下两个不同的解法。
[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/eight-queens-lcci
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。




#include<string>
#include<vector>
#include<iostream>

using namespace std;

bool valid(vector<int>& pos, int x, int y){
        for(int i = 0; i < pos.size(); i++){
                if(i == x || y == pos || x + y == i + pos || x + pos == y + i)return false;
               
        }
        return true;
}



void dfs(int n, int x, vector<int>& pos, vector<string>& temp, vector<vector<string> >& res){
        if(x == n) res.push_back(temp);
        for(int y= 0 ; y < n; y ++){
                if(valid(pos, x, y)){
                        temp = 'Q';
                        pos.push_back(y);
                        dfs(n, x+1, pos, temp, res);
                        pos.pop_back();
                        temp = '.';
                }       
        }
}



vector<vector<string> > solution(int n){
        vector<vector<string> > res;
        vector<string>temp (n, string(n, '.'));
        vector<int> pos;
        dfs(n, 0, pos, temp, res);
        return res;
}




int main(void){
        int n;
        cin >> n;
        vector<vector<string> > res = solution(n);
        for(int i = 0; i < res.size(); i++){
                for(int j = 0; j < res.size(); j++){
                        cout << res <<endl;
                }
                cout << endl;
                cout << "------------------" << endl;
        }
        return 0;
}


参考链接:
1.x + y == i + pos || x + pos == y + i可参见链接:https://leetcode-cn.com/problems/eight-queens-lcci/solution/java-hui-su-fa-shuang-100-san-shu-zu-ji-lu-dui-jia/
页: [1]
查看完整版本: C++刷剑指offer(面试题38. 字符串的排列)【高频】