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