程式設計師面試題精選100題-字串的組合[演算法]
題目:輸入一個字串,輸出該字串中字元的所有組合。舉個例子,如果輸入abc,它的組合有a、b、c、ab、ac、bc、abc。
分析:在本系列部落格的第28題《字串的排列》中,我們詳細討論瞭如何用遞迴的思路求字串的排列。同樣,本題也可以用遞迴的思路來求字串的組合。
假設我們想在長度為n的字串中求m個字元的組合。我們先從頭掃描字串的第一個字元。針對第一個字元,我們有兩種選擇:一是把這個字元放到組合中去,接下來我們需要在剩下的n-1個字元中選取m-1個字元;而是不把這個字元放到組合中去,接下來我們需要在剩下的.n-1個字元中選擇m個字元。這兩種選擇都很容易用遞迴實現。下面是這種思路的參考程式碼:
void Combination(char* string)
{
if(string == NULL)
return;
int length = strlen(string);
vector
for(int i = 1; i <= length; ++ i)
{
Combination(string, i, result);
}
}
void Combination(char* string, int number, vector
{
if(number == 0)
{
vector
for(; iter < (); ++ iter)
printf("%c", *iter);
printf("");
return;
}
if(*string == )
return;
_back(*string);
Combination(string + 1, number - 1, result);
_back();
Combination(string + 1, number, result);
}
由於組合可以是1個字元的組合,2個字元的字元……一直到n個字元的組合,因此在函式void Combination(char* string),我們需要一個for迴圈。另外,我們一個vector來存放選擇放進組合裡的字元。
-
面試優缺點怎麼說
面試優缺點怎麼說1回答示範1:我比較善於發現問題、解決問題。比方說,我們公司有鼓勵員工提建議的制度,在兩年的工作中我提出了60多條改善提案,80%被採用,總積分在我科533人中居第三。除了技術上的改善提議,我也提了很多管理方面的小建議,比方說工作時間播放輕音樂,廁所...
-
【熱門】外企面試的五大忌諱
遲到失約守時守約在人們的日常生活中已成為起碼的禮數,遲到、失約更是外企面試中的大忌。這不但會表現出求職者沒有時間觀念和責任感,更會讓面試官覺得你對這份工作沒有熱忱,從而對你的第一印象大打折扣。面試官提醒求職者,去面試時最好提前10至15分鐘或準時到達。...
-
面試的邀請函(優秀)
使用電子邀請函是近年來很多企業的轉變。在現在社會,邀請函應用範圍廣泛,我敢肯定,大部分人都對擬定邀請函很是頭疼的,以下是小編為大家整理的面試的邀請函,供大家參考借鑑,希望可以幫助到有需要的朋友。面試的邀請函1尊敬的_________先生/女士您好!很榮慶__將您的簡...
-
面試日語個人介紹
面試日語個人介紹1我是xx學院日語系的應屆畢業生,我叫,我是上海人。私は申します.上海に生まれて.今年x學院に卒業しました、専門は日本語です.我的興趣是上網瀏覽資訊,聽音樂。趣味はインターネット、音楽です性格樂觀開朗,誠實,有責任心,適應能力較強。性格は明る...