CVTE笔试题---字符串的全排列

爱被打了一巴掌 2022-09-30 06:18 175阅读 0赞

今天笔了cvte的实习生在线笔试题，一个感觉，基础很重要，如果没有扎实的基础，全是不定项的选择题，真的都是致命伤；

下面我就编程题–字符串的全排列进行总结；

当然，这道题在剑指offer上就有，面试经常出，我以前也做过，但是时间长了，不太熟了，做的时候挺吃力，就在这里总结一下吧！

--------------------

题目： 输入一个字符串，打印该字符串中字符的所有排列，例如输入abc，则打印出abc,acb,bac,bca,cab,cba。

解法一：递归

就是常见的递归的解法，先固定第一个位置的字符，然后排列后面的字符，然后和第二个字符交换，将第二个字符固定在第一个位置，排列后面的字符，依次类推，就排列出了所有组合，其实就是个递归的问题，大问题不停的划分为子问题；

abc为例：

1> 固定a，对bc进行排列，我们又可以把bc当做一个子问题，固定b，对c进行排列，c已经不能再分了，那就打印出abc；

2>又回到了b，b和下一个位置进行交换，即变为cb，在bc这个子问题中，该让c变为第一个字符了，递归得到acb；  
2>又回到了b，但是此时是c为第一个，所以我们需要，将b和c的位置换回去，因为当退回到a的时候，或者c后面还有d的时候，我们需要d固定到b的位置,bc进行排列，如果不换回bc的位置，那么不会得到预期的结果，返回a时也一样，如果不把bc换回bc那么回到a之后，替换第一个位置的字符就变为了 c，此时字符串是cab, 那么又对ab进行排列，最后变为ba, 如果不换回位置的话，等返回到c的时候就变为了 cba, 那么此时该把第三个字符串固定到第一个位置了，岂不是又变成了abc?  
所以，每次交换位置进行递归之后，需要还原位置；  
文字描述比较抽象一点，需要自己进行在本子上一步步的推理，才能理解；

主要代码逻辑如下：

void printR(char*　str,int start, int len)
    {
        if(start == len - 1)
        {
            //到达字符串最后
            printf("%s , " ,str);
        }
    
        else
        {
            for(int i = start; i < len - 1; i++)
            {
                //让后面的字符依次固定在第一个位置
                swap(str[start],str[i]);
                printfR(str,start+1,len);
                swap(str[start],str[i]);
                //最后恢复str的原样；
            }
        }
    }
    
    void Print(char* str)
    {
        if(str == NULL)
            return;
        printfR(str,0,strlen(str)); //递归函数
    }

–解法二：  
熟悉STL的话，你可以在STL里找到一个next\_permutation 函数；  
如果你输入一段字符串（注意，参数其实是迭代器），那么它会按返回这个字符串的下一个组合，但是必须是有序的，所以使用之前我们得排一次序，也就说明了使用的限制。具体解释看STL源码剖析P380；

使用如下：

void Print(char *str)
    {
        int len = strlen(str);
        sort(str,str+len);
        do{
            printf("%s ,",str);
        }while(next_permutation(str,str+len));
    }