今天的算法學(xué)習(xí)還是和字符串有關(guān)，這個(gè)題目據(jù)說(shuō)是以前的某公司面試的筆試題目。題目意思就是說(shuō)，在一個(gè)字符串中找到只出現(xiàn)了一次的那些字符，并且輸出來(lái)。

作為非IT的我，平時(shí)使用Matlab比較多。不是科班出身，對(duì)于這個(gè)題目的理解可能也比較簡(jiǎn)單。但是也算是一個(gè)算法的鍛煉吧，每天進(jìn)步一點(diǎn)。一個(gè)更主要目的就是養(yǎng)成記錄的習(xí)慣，積少成多。

不多說(shuō)直接上我寫的matlab代碼吧

常規(guī)算法 Matlab：常規(guī)遍歷

clc clear close all strInput='abaccdeeff'; strLength=size(strInput,2); if strLength==0disp('this string is null !') end marker=ones(1,strLength); count=0; letterAppearedOnce=[]; for i=1:strLengthflag=1;if marker(i)for j=i+1:strLengthif strInput(j)==strInput(i)flag=0;marker(j)=0;%break;endendelseflag=0;continue;endif flagcount=count+1;letterAppearedOnce=[letterAppearedOnce,strInput(i)];end end if count==0disp('there is not letter appearing once ') elseif count==1disp(['these is only ',num2str(count),' letter appearing once !','this letter is ',letterAppearedOnce]); elsedisp(['these are ',num2str(count),' letters appearing once !','there letters are ',letterAppearedOnce]); end

這個(gè)寫的比較繁瑣，我的思想就是主要遍歷去比較吧，這里marker數(shù)組和flag變量比較重要。marker數(shù)初始時(shí)里面全是1，如果遍歷比較的時(shí)候，出現(xiàn)了相同的，那么那個(gè)相同的字符的索引對(duì)應(yīng)的marker數(shù)組的值為0，例如，
i=1時(shí)，遍歷比較剩余的字符
j=3時(shí)，發(fā)現(xiàn)相同的字符，這marker（3）=0
這樣的話第一層循環(huán)到i=3時(shí)，判斷一下marker（3）是否為真，不是則停止此次循環(huán)，進(jìn)行下一次循環(huán)。

flag變量確定了是否存在出現(xiàn)一次的字符。flag=1，存在，flag=0，不存在。

輸出結(jié)果為：

These are 2 letters appearing once !there letters are: bd

可以看出來(lái)，結(jié)果沒(méi)有問(wèn)題！把marker數(shù)組的結(jié)果貼出來(lái)

1 1 0 1 0 1 1 0 1 0

再換一個(gè)輸入：

strInput='abaccddeeff';

得到的結(jié)果為：

There is only 1 letter appearing once !this letter is: b

同樣還是貼出marker數(shù)組：

1 1 0 1 0 1 0 1 0 1 0

再換一個(gè)輸入，重復(fù)的字符在2個(gè)以上：

strInput='abacacddeccefeeff';

此時(shí)的結(jié)果為：

these is only 1 letter appearing once !this letter is:b

marker數(shù)組為：

1 1 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0

這種算法比較的簡(jiǎn)單，而且比較的復(fù)雜，下面是一種簡(jiǎn)單的方法，思想比較好。

一種好的算法：利用字符ASCII碼實(shí)現(xiàn)

因?yàn)槊總€(gè)字符都有一個(gè)ASCII碼，所以可以定義一個(gè)用于記錄字符出現(xiàn)次數(shù)的數(shù)組，用字符的ASCII碼做為數(shù)組的下標(biāo)，當(dāng)遍歷字符

串時(shí)，就給相應(yīng)下標(biāo)對(duì)應(yīng)的字符次數(shù)加1。這樣對(duì)字符串的一次遍歷就能記錄每個(gè)字符出現(xiàn)的次數(shù)。再找到次數(shù)為的1的索引，即

字符出現(xiàn)一次的字符的 ASCII

clc clear close all strInput='abaccdeeff'; strLength=size(strInput,2); if strLength==0disp('this string is null !') end strAscll=zeros(1,256); for i=1:strLength strAscll(abs(strInput(i)))=strAscll(abs(strInput(i)))+1; end char(find(strAscll==1))

輸出結(jié)果為

ans =bd

這種算法十分的簡(jiǎn)單明了！幾乎就是一個(gè)遍歷，其他的判斷全部都沒(méi)有。最后得到的結(jié)果就是這么的完美！

Python 3 實(shí)現(xiàn)：字典數(shù)據(jù)結(jié)構(gòu)的利用

Python3 的字典這種數(shù)據(jù)結(jié)構(gòu)還是比較好的，原理就不多說(shuō)了，直接看代碼就能體會(huì)到這個(gè)得妙處：

def find_once_appear_letter(string):d={}onceAppearLetter=''for i in string:d[i]=d.get(i,0)+1for item in d.items():if item[1]==1:onceAppearLetter+=item[0]return onceAppearLetterif __name__ == "__main__":str='abaccdeeff'print('The string is :\n')print(str)print()print('the letters appearing only once are:\n') print(find_once_appear_letter(str))

結(jié)果為：

---

完美，學(xué)無(wú)止境！

---

艾勇 上海交通大學(xué)
2017/7/27

總結(jié)

以上是生活随笔為你收集整理的算法题：在一个字符串中找到只出现一次的字符。如输入abaccdeeff，则输出bd。的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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