注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

微软、Google等面试题

剑指Offer:名企面试官精讲典型编程题

 
 
 

日志

 
 

程序员面试题精选100题(28)-字符串的排列[算法]  

2007-05-09 09:36:03|  分类: 杂题 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目:输入一个字符串,打印出该字符串中字符的所有排列。例如输入字符串abc,则输出由字符abc所能排列出来的所有字符串abcacbbacbcacabcba

分析:这是一道很好的考查对递归理解的编程题,因此在过去一年中频繁出现在各大公司的面试、笔试题中。

我们以三个字符abc为例来分析一下求字符串排列的过程。首先我们固定第一个字符a,求后面两个字符bc的排列。当两个字符bc的排列求好之后,我们把第一个字符a和后面的b交换,得到bac,接着我们固定第一个字符b,求后面两个字符ac的排列。现在是把c放到第一位置的时候了。记住前面我们已经把原先的第一个字符a和后面的b做了交换,为了保证这次c仍然是和原先处在第一位置的a交换,我们在拿c和第一个字符交换之前,先要把ba交换回来。在交换ba之后,再拿c和处在第一位置的a进行交换,得到cba。我们再次固定第一个字符c,求后面两个字符ba的排列。

既然我们已经知道怎么求三个字符的排列,那么固定第一个字符之后求后面两个字符的排列,就是典型的递归思路了。

基于前面的分析,我们可以得到如下的参考代码:

void Permutation(char* pStr, char* pBegin);

/////////////////////////////////////////////////////////////////////////
// Get the permutation of a string,
// for example, input string abc, its permutation is
// abc acb bac bca cba cab
/////////////////////////////////////////////////////////////////////////
void Permutation(char* pStr)
{
      Permutation(pStr, pStr);
}

/////////////////////////////////////////////////////////////////////////
// Print the permutation of a string,
// Input: pStr   - input string
//        pBegin - points to the begin char of string
//                 which we want to permutate in this recursion
/////////////////////////////////////////////////////////////////////////
void Permutation(char* pStr, char* pBegin)
{
      if(!pStr || !pBegin)
            return;

      // if pBegin points to the end of string,
      // this round of permutation is finished, 
      // print the permuted string
      if(*pBegin == '\0')
      {
            printf("%s\n", pStr);
      }
      // otherwise, permute string
      else
      {
            for(char* pCh = pBegin; *pCh != '\0'; ++ pCh)
            {
                  // swap pCh and pBegin
                  char temp = *pCh;
                  *pCh = *pBegin;
                  *pBegin = temp;

                  Permutation(pStr, pBegin + 1);

                  // restore pCh and pBegin
                  temp = *pCh;
                  *pCh = *pBegin;
                  *pBegin = temp;
            }
      }
}

扩展1:如果不是求字符的所有排列,而是求字符的所有组合,应该怎么办呢?当输入的字符串中含有相同的字符串时,相同的字符交换位置是不同的排列,但是同一个组合。举个例子,如果输入abc,它的组合有a、b、c、ab、ac、bc、abc

扩展2:输入一个含有8个数字的数组,判断有没有可能把这8个数字分别放到正方体的8个顶点上,使得正方体上三组相对的面上的4个顶点的和相等。

本文已经收录到《剑指Offer——名企面试官精讲典型编程题》一书中,有改动,书中的分析讲解更加详细。欢迎关注。

本题已被九度Online Judge系统收录,欢迎读者移步到http://ac.jobdu.com/hhtproblems.php在线测试自己的代码。

博主何海涛对本博客文章享有版权。网络转载请注明出处http://zhedahht.blog.163.com/。整理出版物请和作者联系。对解题思路有任何建议,欢迎在评论中告知,或者加我微博http://weibo.com/zhedahht或者http://t.163.com/zhedahht与我讨论。谢谢。

  评论这张
 
阅读(40201)| 评论(50)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017