? ? ?Alibaba筆試題：給定一段產(chǎn)品的英文描述，包含M個(gè)英文字母，每個(gè)英文單詞以空格分隔，無(wú)其他標(biāo)點(diǎn)符號(hào)；再給定N個(gè)英文單詞關(guān)鍵字，請(qǐng)說(shuō)明思路并編程實(shí)現(xiàn)方法String extractSummary(String description,String[] key words)目標(biāo)是找出此產(chǎn)品描述中包含N個(gè)關(guān)鍵字（每個(gè)關(guān)鍵詞至少出現(xiàn)一次）的長(zhǎng)度最短的子串，作為產(chǎn)品簡(jiǎn)介輸出。（不限編程語(yǔ)言）20分。

　　解：簡(jiǎn)化題目：從一個(gè)字符串A中找出包含另一個(gè)字符串B所有字母的最小字串。（比A短，并每個(gè)字母只出現(xiàn)一次；這里先排除了關(guān)鍵詞多次出現(xiàn)的情況，這種情況只需稍微改動(dòng)即可），考慮使用兩個(gè)指針p、q指向A起始位置，遍歷指針p，

1、使得q到p之間包含了B中的所有字母。這時(shí)可以是使用一個(gè)數(shù)組來(lái)記錄p中走過(guò)A中遇到B中字母出現(xiàn)的次數(shù)。這樣當(dāng)所有字母全非0的時(shí)候，即可。這時(shí)未能保證q到p是以*p結(jié)尾子句中包含所有字母的最短的一個(gè)。

2、此時(shí)走動(dòng)q指針，另q走到恰好q到p是以*p結(jié)尾子句中包含所有字母的最短的一個(gè)。

如A=dccdaadc B=cda

經(jīng)過(guò)第一步，q指向A[0]，p指向A[4] 計(jì)數(shù)數(shù)組 221 字串dccda并不是以A[4]結(jié)尾子句中最短的包含B的子串

然后，走q指針。走過(guò)A[1]時(shí)，計(jì)數(shù)數(shù)組121，即此時(shí)還是包含了B（ccda），所有繼續(xù)再走；直到A[2]時(shí)，計(jì)數(shù)數(shù)組為111，下一個(gè)將出現(xiàn)不能包含B的全部字母所以此時(shí)A[2]~A[4]為以A[4]結(jié)尾子句中包含所有字母的最短的一個(gè)。

3、然后記錄相應(yīng)信息。q走過(guò)一個(gè)，使得q~p未能包含全部的B，這時(shí)又回到了第一步，直至整個(gè)字符串檢測(cè)完畢。

這里的代碼并未考慮關(guān)鍵字出現(xiàn)多次的情況。這種情況只需要稍做改動(dòng)即可；

1 #include <iostream> 2 3 using namespace std; 4 5 6 //p指向的單詞（空格結(jié)尾或'\0'），在關(guān)鍵詞組中是否存在，存在則相應(yīng)計(jì)數(shù)；當(dāng)所有關(guān)鍵字計(jì)數(shù) 7 //不為0,即包含了所有的關(guān)鍵字了,以*flag回傳1 8 //返回單詞的后一個(gè)位置(若為'\0'則返回'\0') 9 char* countkw_add(int cnt[], char *p, char * kw[], int n, int *falg) // 10 { 11 char *q; 12 char tmp[50]={0}; 13 q = tmp; 14 while(*p && *p!=' ')*q++ = *p++; 15 16 *q = '\0'; 17 18 for (int i=0; i<n; i++) 19 { 20 if (strcmp(tmp, kw[i])==0) 21 { 22 cnt[i]++; 23 for(int j=0; j<n; ++j) 24 { 25 if (!cnt[j]) 26 { 27 break; 28 } 29 } 30 if (j==n) 31 { 32 *falg = 1; //包含了所有的關(guān)鍵字 33 } 34 break; //找到 35 } 36 } 37 while(*p && *p++!=' '); // 38 39 return p; 40 } 41 //由于只有計(jì)數(shù)數(shù)組cnt的數(shù)據(jù)全非零時(shí)才調(diào)用此函數(shù) 42 //p指向的單詞（空格結(jié)尾或'\0'），在關(guān)鍵詞組中是否存在，存在則減去相應(yīng)計(jì)數(shù)；當(dāng)存在關(guān)鍵字計(jì)數(shù) 43 //不為0,即未包含所有的關(guān)鍵字了,以*flag回傳0 44 //返回單詞的后一個(gè)位置(若為'\0'則返回'\0') 45 char* countkw_sub(int cnt[], char *p, char * kw[], int n, int *falg) 46 { 47 char *q; 48 char tmp[50]={0}; 49 q = tmp; 50 while(*p && *p!=' ')*q++ = *p++; 51 52 *q = '\0'; 53 54 for (int i=0; i<n; i++) 55 { 56 57 if (strcmp(tmp, kw[i])==0) 58 { 59 cnt[i]--; 60 61 if (cnt[i]==0) 62 { 63 *falg = 0; //缺關(guān)鍵字kw[i] 64 } 65 break; //找到 66 } 67 } 68 while(*p && *p++!=' '); // 69 70 return p; 71 } 72 73 void extractSummery(char *des, char * keywords[], int n, char **beg, char **end) 74 { 75 char *p,*q; 76 77 int *cnt; 78 int minlen=strlen(des); // 79 *beg = NULL; 80 *end = NULL; 81 82 cnt = (int *)malloc(sizeof(int)*n); 83 memset(cnt, 0, sizeof(int)*n); 84 85 86 q= des; 87 while(*q!='\0' && *q==' ')q++; 88 89 p = q; 90 int fulled=0; 91 92 while(*p!='\0') 93 { 94 95 p = countkw_add(cnt,p,keywords,n, &fulled); 96 97 while(*p && *p==' ')p++; 98 99 if (fulled) //包含了所有的關(guān)鍵字 100 { 101 char *tmp; 102 tmp = q; 103 while(fulled) 104 { 105 q = tmp; //記錄上一次 106 tmp= countkw_sub(cnt,tmp,keywords,n, &fulled); 107 } 108 109 if (p-q<minlen) //發(fā)現(xiàn)更小的，則更新 110 { 111 minlen = p-q; 112 *beg = q; 113 *end = p; 114 } 115 //while(*q && *q!=' ')q++; 116 q = tmp; 117 while(*q && *q==' ')q++; //指向下一個(gè)詞 118 } 119 120 121 122 } 123 } 124 125 126 127 128 int main() 129 { 130 char des[] = "aefo aec egne a se a fe a aec ve fjfj as lel"; 131 132 char *kw[] = {"aec" ,"a", "fjfj"}; 133 char *b,*e; 134 135 extractSummery(des,kw,3,&b,&e); 136 137 for(char *p=b; p<e; p++) 138 { 139 cout<<*p; 140 } 141 142 cout<<endl; 143 144 return 0; 145 }

?

---恢復(fù)內(nèi)容結(jié)束---

轉(zhuǎn)載于:https://www.cnblogs.com/legendmaner/archive/2013/03/17/2965030.html

總結(jié)

以上是生活随笔為你收集整理的Alibaba笔试题：根据关键字求最短摘要字串的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。