算法思路整理3-字符串

1. 1. 字符串

?? ? a. 反轉(zhuǎn)字符串

?? ? ? ? i. 棧

?? ? ? ? ii. 時(shí)間復(fù)雜度n,空間復(fù)雜度n

?? ? b. 字符串的全排列(類似數(shù)組部分集合的子集)

?? ? ? ? i. 構(gòu)造隊(duì)列土铺,字符串首字符入隊(duì)

?? ? ? ? ii. 對(duì)字符串按位置進(jìn)行遍歷

?? ? ? ? iii. for循環(huán)內(nèi)部記下此時(shí)隊(duì)列的size萤悴,循環(huán)size次瘾腰,每次對(duì)于出隊(duì)的元素,循環(huán)在特定位置插入當(dāng)前字符后入隊(duì)

?? ? ? ? iv. 時(shí)間復(fù)雜度n!

?? ? c. 最小編輯代價(jià)

?? ? d. KMP算法

?? ? ? ? i. 構(gòu)造next函數(shù)覆履,動(dòng)態(tài)規(guī)劃思路

? ? ? ? ? ? 1. 1. a[0]=-1

? ? ? ? ? ? 2. 2. a[1]=0;

? ? ? ? ? ? 3. 3. for循環(huán)從2號(hào)位置開始蹋盆, 如果i-1號(hào)位置的next值為-1,那么a[i]=0

? ? ? ? ? ? 4. 4. 如果next[i-1]不等于-1硝全,那么說明n-1位的最長前綴后下一位是next[j-1]栖雾,那么判斷arr[j-1]是否與arr[next[j-1]]是否相等,如果相等next[j]=k+1

? ? ? ? ? ? 5. 5. 構(gòu)造while循環(huán)伟众,進(jìn)行模式識(shí)別析藕,

?? ? ? ? ? ? ? ? a. 如果當(dāng)前位置相同,i++;j++; 如果此時(shí)j=模式串的長度凳厢,匹配成功

?? ? ? ? ? ? ? ? b. 如果當(dāng)前位置不同账胧,next[j]==-1, j=0;i++;

?? ? ? ? ? ? ? ? c. 如果當(dāng)前位置不同,next【j】!=-1, j=next[j],繼續(xù)比較

?? ? e. 最長重復(fù)子串a(chǎn)bcabc

?? ? ? ? i. 滑動(dòng)窗口為長度的一半

?? ? ? ? ii. 雙層循環(huán)先紫,外層窗口--治泥,內(nèi)層起始位置—

?? ? ? ? iii. 通過charAt判斷是否相等

?? ? f. 字符串轉(zhuǎn)換成ip地址

?? ? ? ? i. 遞歸,ip地址分四部分

?? ? ? ? ii. 獲取第一部分合法的情況下泡孩,判斷剩余部分是不是可以分成3個(gè)合法的塊兒

? ? ? ? ? ? 1. 1. 第一部分1個(gè)字符车摄,2個(gè)字符,3個(gè)字符的情況

? ? ? ? ? ? 2. 2. 當(dāng)多個(gè)字符時(shí)仑鸥,首字符不為0

? ? ? ? ? ? 3. 3. 用當(dāng)前第一塊兒和后面遞歸結(jié)果進(jìn)行合并吮播,最后返回

?? ? ? ? iii. 當(dāng)剩余部分為1時(shí),判斷是否為合法數(shù)字眼俊,<256且首字符不為0意狠,添加到ret

?? ? ? ? iv. 時(shí)間復(fù)雜度n^2

?? ? g. 將字符串轉(zhuǎn)換為整數(shù)

?? ? h. 大數(shù)乘法

?? ? ? ? i. 構(gòu)造乘法,str1n 構(gòu)造進(jìn)位C,從后往前疮胖,留意c

?? ? ? ? ii. 構(gòu)造加法环戈,從后往前,留意c

?? ? ? ? iii. 注意符號(hào)澎灸,注意乘數(shù)的位數(shù)對(duì)應(yīng)補(bǔ)0

?? ? ? ? iv. 時(shí)間復(fù)雜度nm, 空間復(fù)雜度m+n

?? ? i. 驗(yàn)證IP地址

?? ? ? ? i. 分v4,v6兩種規(guī)則驗(yàn)證

?? ? ? ? ii. 注意v4中大小的判斷院塞,split后的字符串高位不能是0

?? ? ? ? iii. Split(“[.]”)

?? ? ? ? iv. 時(shí)間復(fù)雜度n

?? ? j. 字符串?dāng)?shù)組的最長公共前綴

?? ? ? ? i. 拿第一個(gè)字符串作為參照物,遍歷循環(huán)查找

?? ? ? ? ii. 兩層循環(huán)性昭,如果有一個(gè)為false就返回

?? ? ? ? iii. 時(shí)間復(fù)雜度為n字符串的最短長度

?? ? k. 正則表達(dá)式匹配

?? ? l. 判斷回文

?? ? ? ? i. 如果是奇數(shù)拦止,從n/2 +1,n/2 +1開始判斷是否回文

?? ? ? ? ii. 如果是偶數(shù),從n/2汹族,n/2 +1判斷是否回文萧求,分別往兩邊--,++

?? ? ? ? iii. 時(shí)間復(fù)雜度n

?? ? m. 最小覆蓋子串

?? ? n. 字符串變形顶瞒,字母大小寫取反夸政,空格分開的取反

?? ? ? ? i. 注意char<’A’,類似的用法簡單好用

?? ? ? ? ii. 不確定空格數(shù)量時(shí),不要用空格split,容易出問題

?? ? ? ? iii. 從頭開始遍歷字符串榴徐,找到完整的單詞后守问,大小寫取反,放到結(jié)果字符串的開頭

?? ? ? ? iv. 如果當(dāng)前是空格坑资,直接放到結(jié)果字符串的開頭

?? ? ? ? v. 時(shí)間復(fù)雜度n

?? ? o. 通配符匹配

?? ? p. 判斷是否是旋轉(zhuǎn)字符串酪碘,比如nihao,haoni這一對(duì)就是旋轉(zhuǎn)字符串

?? ? ? ? i. 同時(shí)遍歷兩個(gè)字符串,一個(gè)從前開始盐茎,一個(gè)從后開始

?? ? ? ? ii. 如果當(dāng)兩個(gè)字符串相等,判斷剩余部分是否相等徙赢,如果相等則返回true

?? ? ? ? iii. 時(shí)間復(fù)雜度n

?? ? q. 判斷括號(hào)序列的合法性

?? ? ? ? i. 用棧

?? ? ? ? ii. 時(shí)間復(fù)雜度n, 空間復(fù)雜度n

?? ? r. 大數(shù)加法

?? ? ? ? i. 從尾部開始加字柠,設(shè)計(jì)進(jìn)位c

?? ? ? ? ii. 最后別拉下c

?? ? ? ? iii. 時(shí)間復(fù)雜度max(m+n),空間復(fù)雜度m+n

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市狡赐,隨后出現(xiàn)的幾起案子窑业,更是在濱河造成了極大的恐慌,老刑警劉巖枕屉,帶你破解...
    沈念sama閱讀 216,496評(píng)論 6 501
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件常柄,死亡現(xiàn)場離奇詭異,居然都是意外死亡搀擂,警方通過查閱死者的電腦和手機(jī)西潘,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,407評(píng)論 3 392
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來哨颂,“玉大人樱衷,你說我怎么就攤上這事绍撞。” “怎么了?”我有些...
    開封第一講書人閱讀 162,632評(píng)論 0 353
  • 文/不壞的土叔 我叫張陵蕊爵,是天一觀的道長。 經(jīng)常有香客問我塑陵,道長哎迄,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,180評(píng)論 1 292
  • 正文 為了忘掉前任斤蔓,我火速辦了婚禮植酥,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘附迷。我一直安慰自己惧互,他們只是感情好哎媚,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,198評(píng)論 6 388
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著喊儡,像睡著了一般拨与。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上艾猜,一...
    開封第一講書人閱讀 51,165評(píng)論 1 299
  • 那天买喧,我揣著相機(jī)與錄音,去河邊找鬼匆赃。 笑死淤毛,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的算柳。 我是一名探鬼主播低淡,決...
    沈念sama閱讀 40,052評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼瞬项!你這毒婦竟也來了蔗蹋?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 38,910評(píng)論 0 274
  • 序言:老撾萬榮一對(duì)情侶失蹤囱淋,失蹤者是張志新(化名)和其女友劉穎猪杭,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體妥衣,經(jīng)...
    沈念sama閱讀 45,324評(píng)論 1 310
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡皂吮,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,542評(píng)論 2 332
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了税手。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片蜂筹。...
    茶點(diǎn)故事閱讀 39,711評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖冈止,靈堂內(nèi)的尸體忽然破棺而出狂票,到底是詐尸還是另有隱情,我是刑警寧澤熙暴,帶...
    沈念sama閱讀 35,424評(píng)論 5 343
  • 正文 年R本政府宣布闺属,位于F島的核電站,受9級(jí)特大地震影響周霉,放射性物質(zhì)發(fā)生泄漏掂器。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,017評(píng)論 3 326
  • 文/蒙蒙 一俱箱、第九天 我趴在偏房一處隱蔽的房頂上張望国瓮。 院中可真熱鬧,春花似錦、人聲如沸乃摹。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,668評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽孵睬。三九已至播歼,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間掰读,已是汗流浹背秘狞。 一陣腳步聲響...
    開封第一講書人閱讀 32,823評(píng)論 1 269
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留蹈集,地道東北人烁试。 一個(gè)月前我還...
    沈念sama閱讀 47,722評(píng)論 2 368
  • 正文 我出身青樓,卻偏偏與公主長得像拢肆,于是被迫代替她去往敵國和親减响。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,611評(píng)論 2 353

推薦閱讀更多精彩內(nèi)容