背景
對(duì)算法一直應(yīng)用的比較少，最近看到一些典型的算法想練練手，想看看到底有多么讓人討厭。其實(shí)發(fā)現(xiàn)算法都有一定的套路，一般并不是臨時(shí)憑空想出來(lái)的，大都建立在一些已經(jīng)存在的經(jīng)典算法知識(shí)以及數(shù)據(jù)結(jié)構(gòu)上。換句話來(lái)說(shuō)，如果某些玩法之前未接觸過(guò)，那么讓你在短時(shí)間內(nèi)臨時(shí)想出來(lái)還是有一定難度的。這有點(diǎn)類似項(xiàng)目經(jīng)驗(yàn)，如果曾經(jīng)做過(guò)一個(gè)crm系統(tǒng)，下次再碰到它時(shí)你就輕松很多，如果你挑戰(zhàn)的是一個(gè)你從未遇到過(guò)的系統(tǒng)，你只能憑已有知識(shí)去強(qiáng)吃。
這個(gè)也是經(jīng)常遇到到，給出兩個(gè)任意長(zhǎng)度的字符串，輸出最大公有字符串，比如輸入abcdef，cdef，則輸出cdef。
解決方案
采用雙層循環(huán)，指針移動(dòng)來(lái)記錄所有子串，最后取最大長(zhǎng)度子串。利用臨時(shí)隊(duì)列來(lái)存儲(chǔ)循環(huán)過(guò)程中匹配成功的字符元素，從兩個(gè)字符串首個(gè)元素開(kāi)始匹配。
- 如果a.charat(i)=b.charat(j)，標(biāo)記開(kāi)始匹配，同時(shí)移動(dòng)兩者指針，并將相同字符串壓入臨時(shí)隊(duì)列中
- 如果a.charat(i)!=b.charat(j)，只移動(dòng)b的指針。如果處于匹配中，則將臨時(shí)隊(duì)列存儲(chǔ)到結(jié)果集中，并清空臨時(shí)隊(duì)列。
- 如果a,b任意一個(gè)到了最后一個(gè)元素，將臨時(shí)隊(duì)列中的值存儲(chǔ)到結(jié)果集中，并清空臨時(shí)隊(duì)列
示意圖
從元素0開(kāi)始比較
字符串a(chǎn)指針不動(dòng)，b依次向后找至少找到相同的，將相同字符壓入臨時(shí)隊(duì)列中。
出現(xiàn)第一個(gè)匹配元素
當(dāng)出現(xiàn)匹配元素后，兩個(gè)字符串均向后移動(dòng)一個(gè)元素再做比較。
匹配出現(xiàn)中斷
如果前面已經(jīng)開(kāi)始匹配成功，向后出現(xiàn)字符不相同時(shí)，終止。
重置索引，循環(huán)匹配
字符串b指針向后移動(dòng)，字符串a(chǎn)的指針重置，遞歸上面的步驟。
示例代碼
下面的示例將所有子串均記錄下來(lái)，如果只想輸出最大子串需要改下邏輯，定義一個(gè)最大子串，然后與循環(huán)計(jì)算的子串相比較，取兩者長(zhǎng)度最大值即可。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
string b="abcdeqwe";string a="cdeabrwqedeqwe";int lengtha=a.length();int lengthb=b.length();//標(biāo)識(shí)是否開(kāi)始匹配boolean match=false;//循環(huán)中用于存儲(chǔ)相同字符的臨時(shí)隊(duì)列queue tmpresult=new arrayqueue();//存儲(chǔ)所有子串list<queue> result=new arraylist<>();for(int i=0;i<lengtha;i++){ int indexa=i; for(int j=0;j<lengthb;j++){ if(a.charat(indexa)==b.charat(j)){ if(!match) { match = true; } tmpresult.add(a.charat(indexa)); if(indexa<lengtha-1) { indexa++; } } else { if(match) { result.add(tmpresult); //重置條件 tmpresult=new arrayqueue(); indexa=i; } } if(j==lengthb-1||i==lengtha-1){ if(!tmpresult.isempty()){ result.add(tmpresult); //重置條件 tmpresult=new arrayqueue(); } } }}//取最大的子串queue stringresult= collections.max(result, new ordering<queue>() { @override public int compare(queue left, queue right) { return integer.compare(left.size(),right.size()); }}); |
優(yōu)點(diǎn)
指針移動(dòng)在循環(huán)過(guò)程中不會(huì)產(chǎn)生多余的臨時(shí)字符串，如果是substring方案就需要考慮效率了。
以上就是本文的全部?jī)?nèi)容，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來(lái)一定的幫助，同時(shí)也希望多多支持服務(wù)器之家！
原文鏈接：http://www.cnblogs.com/ASPNET2008/p/6343852.html
