騰訊的一道筆試算法題解答
假設有這樣一種字符串，它們的長度不大于 26 ，而且若一個這樣的字符串其長度為 m ，則這個字符串必定由 a, b, c ... z 中的前 m 個字母構成，同時我們保證每個字母出現且僅出現一次。比方說某個字符串長度為 5 ，那么它一定是由 a, b, c, d, e 這 5 個字母構成，不會多一個也不會少一個。嗯嗯，這樣一來，一旦長度確定，這個字符串中有哪些字母也就確定了，唯一的區別就是這些字母的前后順序而已。
現在我們用一個由大寫字母 A 和 B 構成的序列來描述這類字符串里各個字母的前后順序：
如果字母 b 在字母 a 的后面，那么序列的第一個字母就是 A （After），否則序列的第一個字母就是 B （Before）；
如果字母 c 在字母 b 的后面，那么序列的第二個字母就是 A ，否則就是 B；
如果字母 d 在字母 c 的后面，那么 …… 不用多說了吧？直到這個字符串的結束。
這規則甚是簡單，不過有個問題就是同一個 AB 序列，可能有多個字符串都與之相符，比方說序列“ABA”，就有“acdb”、“cadb”等等好幾種可能性。說的`專業一點，這一個序列實際上對應了一個字符串集合。那么現在問題來了：給你一個這樣的 AB 序列，問你究竟有多少個不同的字符串能夠與之相符？或者說這個序列對應的字符串集合有多大？注意，只要求個數，不要求枚舉所有的字符串。
#include <iostream>
using namespace std;
int main()
{
char *ch=”ABAB“;
cout<<Count(1,1,ch)<<endl;
return 0;
}
int Count(int left,int right,char *p)
{
if(*(p+1)=='\0')
return *p=='A'?right:left;
int Sum=0;
if(*p=='A')
{
p++;
for(int j=0;j<right;j++)
Sum=Count(++left,right-j,p);
}
else
{
p++;
while(int j=0;j<left;j++)
Sum=Count(left-j,right++,p);
}
return Sum;
}
【騰訊的一道筆試算法題解答】相關文章：
騰訊技術筆試題12-20
騰訊運營筆試題12-20
2017騰訊筆試題07-21
騰訊運營的筆試題目01-16
騰訊前端筆試題目01-15
騰訊商業分析筆試題06-28
騰訊校招筆試題01-16
騰訊技術筆試題目01-16
騰訊技術綜合筆試題01-15
騰訊筆試題目初試11-13