博客

题目描述：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述:

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。


注意这里要求字典序排列，最后要进行一次排序操作

递归，每个位置可以换或者不换，不换就是与其本身进行交换，换就是与其后面的字符进行交换，然后递归下去，一直到最后一个字符就可以打印了，判断重复的操作利用一个map，每个位置上的字符不允许重复即可，注意递归回来进行一次恢复的操作，不恢复答案也是正确的其实。注意最后要进行一次sort，使其满足字典序。

class Solution {
public:
    vector<string> Permutation(string str) {
        //对于每个字符，可以和其他字符进行交换
        vector<string> ret;
        if(str == "")
            return ret;
        PermutationCore(str,0,ret);
        sort(ret.begin(),ret.end());
        return ret;
    }
    void PermutationCore(string str,int index,vector<string> &ret){
        if(index == str.length()-1){
            ret.push_back(str);
            return;
        }
        //普遍状态是和其他字符进行交换
        //每个位置就是换或者不换两种状态
        //可能有字符重复，所以要用m让每个位置上的字符不要重复
        map<char,int> m;
        for(int i=index;i<str.length();i++){
            if(m.find(str[i]) == m.end()){
                swap(str[index],str[i]);
                m[str[i]] = 1;
                PermutationCore(str,index+1,ret);
                //swap(str[index],str[i]);
            }
        }
    }
    void swap(char &a,char &b){
        char tmp = a;
        a = b;
        b = tmp;
    }
};

字符串的组合

每个位置上可以选择当前字符加入cur或者不加入，最后判断如果是“”就不打印，其他就可以打印。例如输入a、b、c,输出a b c ab ac abc。

//字符串的组合
//采用回溯法
void strsetCore(string str,string cur,int index){
    //base case
    if(index == str.length()){
        if(cur != ""){
            cout<<cur<<endl;
        }
        return;
    }
    //不加
    strsetCore(str,cur,index+1);
    //加
    strsetCore(str,cur+str[index],index+1);
}
void strset(string str){
    if(str == "")
        return;
    strsetCore(str,"",0);
}

输入含有8个数字的数组，判断有咩有可能把这8个数字分别放到正方体的8个顶点上，使得正方体上三组相对的面上的4个顶点的和都相等

解法：首先得到这8个数字的全排列，然后找出有没有使得条件

a1 + 2 + 3 + 4 = 5 + 6 + 7 + 8 && 1 + 3 + 5 + 7 = 2 + 4 + 6 + 8 &&

1 + 2 + 5 + 6 = 3 + 4 + 7 + 8成功的组合，有则成功，没有则失败。

既然也是全排列，那就还是递归交换的思想，然后走到底就判断是否满足条件，满足就可以退出了，不满足就继续。

八皇后问题

思路：还是全排列，用一个数组表示，下标表示行，内容表示列，初始化为0-n-1，这样子行列肯定是不同的，进行全排列得到所有可能，最后只需要进行对角线判断即可。

void swap(int &a,int &b){
    int temp = a;
    a = b;
    b = temp;
}
//八皇后，也是全排列，然后判断是否合法
int nqueenCore(int n,vector<int>& location,int index){
    //全排列问题，每个位置可以和后面的其他位置交换，或者不换
    //base case就是来到了最后一个元素的位置，判断是否合法
    if(index == n-1){
        //判断对角线
        /*for(int i=0;i<n;i++)
            cout<<location[i]<<" ";
        cout<<endl;*/
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(i-j == location[i] - location[j] || i-j == location[j] - location[i])
                    return 0;
            }
        }
        return 1;
    }
    //普遍状态，换或者不换
    int ret = 0;
    for(int i=index;i<n;i++){
        //不可能存在重复的数字的
        swap(location[index],location[i]);
        ret += nqueenCore(n,location,index+1);
        swap(location[index],location[i]);
    }
    return ret;
}
int nqueen(int n){
    if(n == 0)
        return 0;
    //使用一个vector,下标代表行号，内容代表列号
    //初始化为0-n-1，因此其行号和列号是不可能重复的
    //所以只需要判断对角线是否合法即可
    vector<int> location(n,0);
    for(int i=0;i<n;i++)
        location[i] = i;
    return nqueenCore(n,location,0);
}