面試算法代碼知識梳理系列
面試算法知識梳理(1) - 排序算法
面試算法知識梳理(2) - 字符串算法第一部分
面試算法知識梳理(3) - 字符串算法第二部分
面試算法知識梳理(4) - 數(shù)組第一部分
面試算法知識梳理(5) - 數(shù)組第二部分
面試算法知識梳理(6) - 數(shù)組第三部分
面試算法知識梳理(7) - 數(shù)組第四部分
面試算法知識梳理(8) - 二分查找算法及其變型
面試算法知識梳理(9) - 鏈表算法第一部分
面試算法知識梳理(10) - 二叉查找樹
面試算法知識梳理(11) - 二叉樹算法第一部分
面試算法知識梳理(12) - 二叉樹算法第二部分
面試算法知識梳理(13) - 二叉樹算法第三部分
一、概要
本文介紹了有關(guān)字符串的算法第一部分的Java代碼實(shí)現(xiàn)萝衩，所有代碼均可通過 在線編譯器 直接運(yùn)行喉誊，算法目錄：
- 替換字符串中的空格
- 輸入一個(gè)字符串贵扰，打印出該字符串的所有排列
- 第一個(gè)只出現(xiàn)一次的字符
- 翻轉(zhuǎn)句子
- 計(jì)算字符串之間的最短距離
二止吁、代碼實(shí)現(xiàn)
2.1 替換字符串中的空格
問題描述
實(shí)現(xiàn)一個(gè)函數(shù)初澎，將字符串p中的所有空格都替換成為指定的字符串r帜平。
解決思路
- 遍歷原始的字符串
p匀钧，統(tǒng)計(jì)原先字符串中空格的個(gè)數(shù)spaceNum侦啸。 - 創(chuàng)建一個(gè)新的數(shù)組
n槽唾，用于存放替換后的字符串。由于原先字符串中空格也占了一個(gè)位置光涂，因此新數(shù)組n的長度為p.len + (r.len - 1) * spaceNum庞萍。 - 對于
p從后往前遍歷，如果 遇到了空格忘闻，那么就將需要替換的字符串r中的字符 從后往前 填入n數(shù)組中钝计；如果 遇到了非空格，那么就將p中的字符填入n數(shù)組中。
實(shí)現(xiàn)代碼
class Untitled {
static char[] replaceSpace(char p[], char r[], int pLen, int rLen){
int spaceNum = 0;
int i;
for(i = 0; i < pLen; i++){
if(p[i] == ' ')
spaceNum += (rLen-1);
}
int nLen = pLen+spaceNum;
char n[] = new char[nLen+1];
i = nLen-1;
int j = pLen-1;
while(i >= 0 && j >= 0){
if (p[j] == ' ') {
for (int k = rLen-1; k >= 0; k--)
n[i--] = r[k];
} else {
n[i--] = p[j];
}
j--;
}
n[nLen] = 0;
return n;
}
public static void main(String[] args) {
char[] source = "I am sentence with space".toCharArray();
char[] replace = "%20".toCharArray();
char[] result = replaceSpace(source, replace, source.length, replace.length);
System.out.println(result);
}
}
運(yùn)行結(jié)果
>> I%20am%20sentence%20with%20space
2.2 輸入一個(gè)字符串私恬，打印出該字符串的所有排列
問題描述
輸入一個(gè)字符串交播，打印出該字符串中字符的所有排列。例如輸入字符串abc践付，則輸出由字符a秦士、b、c所能排列出來的所有字符串abc永高、acb隧土、bac、bca命爬、cab和cba曹傀。
解決思路
這是一個(gè) 遞歸問題，求一個(gè)長度為n的字符串的全排列的方法為：
-
n[0..n.len-1]全排列的計(jì)算方法為：將n[0]位置的字符分別和n[1..n.len-1]的每一個(gè)字符串交換饲宛，n[0]和交換后的n[1..n.len - 1]的全排列進(jìn)行組合皆愉。我們將字符串{s}的全排列表示為{s}，那么對于abc來說艇抠，其全排列{abc}幕庐，就等于是a + {bc}、b + {ac}家淤，c + {ba}异剥。 - 以此類推，
n[1..n.len - 1]的全排列絮重，則是將n[1]分別和n[2..n.len - 1]的每一個(gè)字符串交換冤寿，再求出交換后的n[2..len - 1]的全排列，遞歸結(jié)束的條件為n[i..n.len - 1]只有一個(gè)字符青伤，例如督怜，bc的全排列為b + {c}、c + 狠角号杠，而{c}和的全排列只有一種擎厢，因此遞歸結(jié)束究流，這時(shí)候就可以打印出結(jié)果辣吃。
實(shí)現(xiàn)代碼
class Untitled {
static void permutationStr(char p[], int depth, int length){
if (depth == length) {
System.out.println(p);
return;
}
char c;
for (int i = depth; i < length; i++){
c = p[depth]; p[depth] = p[i]; p[i] = c;
permutationStr(p, depth+1, length);
c = p[depth]; p[depth] = p[i]; p[i] = c;
}
}
public static void main(String[] args) {
char[] source = "abc".toCharArray();
permutationStr(source, 0, source.length);
}
}
運(yùn)行結(jié)果
>> abc
>> acb
>> bac
>> bca
>> cba
>> cab
2.3 第一個(gè)只出現(xiàn)一次的字符
問題描述
在字符串中找出第一個(gè)只出現(xiàn)一次的字符动遭。如輸入abaccdeff，則輸出b神得，要求時(shí)間復(fù)雜度為O(n)厘惦。
解決思路
這里需要采用 以空間換時(shí)間 的思想，也就是創(chuàng)建一個(gè)足夠大的數(shù)組c，這里為256宵蕉，然后對原始的數(shù)組p進(jìn)行兩次遍歷：
- 第一次 從頭開始 遍歷
p酝静，以p的值作為數(shù)組c的下標(biāo)，并將c中對應(yīng)位置的值加1羡玛，也就是說c[Integer.valueOf(i)]的值表示的是字符i在p中出現(xiàn)的次數(shù)别智。這和HashMap的原理有些類似，只不過是將查找的key值直接簡化成為了value的整型值稼稿。 - 第二次 從頭開始 遍歷
p薄榛，查找數(shù)組c對應(yīng)位置該值是否為1，如果為1让歼，那么就表示它是第一次只出現(xiàn)一次的字符敞恋。
實(shí)現(xiàn)代碼
class Untitled {
static char firstNotRepeat(char p[], int len){
if (len == 1)
return p[0];
int c[] = new int[256];
int i;
char r = p[0];
for (i = 0; i < 256; i++)
c[i] = 0;
for (i = 0; i < len; i++)
c[p[i]] += 1;
for (i = 0; i < len; i++) {
if (c[p[i]] == 1) {
r = p[i];
break;
}
}
return r;
}
public static void main(String[] args) {
char[] source = "abaccdeff".toCharArray();
char c = firstNotRepeat(source, source.length);
System.out.println(c);
}
}
運(yùn)行結(jié)果
>> b
2.4 翻轉(zhuǎn)句子
問題描述
翻轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字符的順序不變谋右，句子中單詞以空格符隔開硬猫。例如I am a original string翻轉(zhuǎn)后的結(jié)果為string original a am I。
解決思路
實(shí)現(xiàn)過程分為兩步：
- 第一步改执，將整個(gè)句子中的所有字符都翻轉(zhuǎn)
- 第二步啸蜜，遍歷翻轉(zhuǎn)后的句子，對于句子內(nèi)的每一個(gè)單詞辈挂，將其字符再翻轉(zhuǎn)一次盔性，就能保證單詞內(nèi)字符的順序不變。翻轉(zhuǎn)單詞的時(shí)候呢岗，通過
pStart和pEnd記錄每次遇到單詞的起止下標(biāo)冕香，并使用子方法reverseSub對單詞中的字符進(jìn)行翻轉(zhuǎn)。
實(shí)現(xiàn)代碼
class Untitled {
static void reverseSub(char p[], int start, int end){
char c;
int i = start;
int j = end;
while(i < j){
c = p[i]; p[i] = p[j]; p[j] = c;
i++; j--;
}
}
static void reverseSentence(char p[], int length){
//首先翻轉(zhuǎn)整個(gè)具體的所有字符后豫。
reverseSub(p, 0, length-1);
int pStart = 0;
int pEnd = 0;
//從頭開始遍歷悉尾，尋找句子中的單詞，pStart和pEnd分別表示單詞的起止下標(biāo)挫酿。
while(pStart < length && pEnd < length){
if(p[pStart] == ' '){
pStart++;
pEnd++;
} else if (p[pEnd] == ' ' || p[pEnd] == '\0') {
//翻轉(zhuǎn)單詞中的字符构眯。
reverseSub(p, pStart, --pEnd);
pStart = ++pEnd;
} else {
pEnd++;
}
}
}
public static void main(String[] args) {
char[] source = "I am a original string".toCharArray();
System.out.println(source);
reverseSentence(source, source.length);
System.out.println(source);
}
}
運(yùn)行結(jié)果為：
>> string original a am I
2.5 計(jì)算字符串之間的最短距離
問題描述
假設(shè)我們有兩個(gè)字符串A和B，那么如果想要將字符串A通過以下三種操作變換成B：刪除早龟、新增和修改惫霸，操作步驟的次數(shù)就稱為 字符串 A 和 B 之間的距離。
現(xiàn)在給定兩個(gè)字符串葱弟，求這兩個(gè)字符串之間的最短距離壹店。
解決思路
首先，我們需要先明確一個(gè)前提條件：如果A的長度為0芝加，那么A和B之間的距離就為B的長度硅卢，反之對于B也如此。
下面，我們在來看普通的情況将塑，假如A[0]和B[0]相同脉顿，那么A和B之間的距離就為A[1..A.len-1]和B[1..B.len-1]之間的距離；假如A[0]和B[0]不相同点寥，那么想要讓A和B相同艾疟，執(zhí)行的操作有以下幾種：
- 刪除
A的第一個(gè)字符，然后計(jì)算A[1..A.len-1]和B[0..B.len-1]的距離 - 刪除
B的第一個(gè)字符敢辩，然后計(jì)算A[0..A.len-1]和B[1..B.len-1]的距離 - 修改
A的第一個(gè)字符為B的第一個(gè)字符汉柒，然后計(jì)算A[1..A.len-1]和B[1..B.len-1]的距離 - 修改
B的第一個(gè)字符為A的第一個(gè)字符，然后計(jì)算A[1..A.len-1]和B[1..B.len-1]的距離 - 增加
A的第一個(gè)字符到B第一個(gè)字符之前责鳍，然后計(jì)算A[1..A.len-1]和B[0...B.len-1]的距離 - 增加
B的第一個(gè)字符到A第一個(gè)字符之前碾褂，然后計(jì)算A[0...A,len-1]和B[1..B.len-1]的距離
對于以上這六種情況，其實(shí)最終都可以歸納為 經(jīng)過一次操作历葛，再加上剩下部分的操作次數(shù)正塌，那么我們的接下來的工作就是 求出剩下部分的操作部分的最小值。對于上面的任意一種情況恤溶，經(jīng)過劃分后A和B的長度都會減少乓诽，那么最終必然會達(dá)到我們在一開始談到的 前提條件：如果A的長度為0，那么A和B之間的距離就為B的長度咒程，反之對于B也如此鸠天。
實(shí)現(xiàn)代碼
class Untitled {
static int minValue(int t1, int t2, int t3){
if (t1 < t2) {
return t1 < t3 ? t1 : t3;
} else {
return t2 < t3 ? t2 : t3;
}
}
static int calStringDis(char p1[], char p2[], int p1Start, int p2Start, int p1Len, int p2Len){
if (p1Len == 0) {
if (p2Len == 0)
return 0;
else
return p2Len;
}
if (p2Len == 0) {
if (p1Len == 0)
return 0;
else
return p1Len;
}
if (p1[p1Start] == p2[p2Start])
//A和B的第一個(gè)字符相同。
return calStringDis(p1, p2, p1Start+1, p2Start+1, p1Len-1, p2Len-1);
else {
//(1) 刪除B的第一個(gè)字符帐姻，或者將B的第一個(gè)字符放到A之前稠集。
int t1 = calStringDis(p1, p2, p1Start, p2Start+1, p1Len, p2Len-1);
//(2) 刪除A的第一個(gè)字符，或者將A的第一個(gè)字符放到B之前饥瓷。
int t2 = calStringDis(p1, p2, p1Start+1, p2Start, p1Len-1, p2Len);
//(3) 修改A的第一個(gè)字符為B的第一個(gè)字符剥纷，或者修改B的第一個(gè)字符為A的第一個(gè)字符。
int t3 = calStringDis(p1, p2, p1Start+1, p2Start+1, p1Len-1, p2Len-1);
//計(jì)算以上三種情況的最小值呢铆，再加上這次操作的次數(shù)晦鞋。
return minValue(t1, t2, t3) + 1;
}
}
public static void main(String[] args) {
char[] source = "abcde".toCharArray();
char[] other = "bcd".toCharArray();
System.out.println("" + calStringDis(source, other, 0, 0, source.length, other.length));
}
}
運(yùn)行結(jié)果
>> 2
更多文章，歡迎訪問我的 Android 知識梳理系列：
- Android 知識梳理目錄：http://www.reibang.com/p/fd82d18994ce
- 個(gè)人主頁：http://lizejun.cn
- 個(gè)人知識總結(jié)目錄：http://lizejun.cn/categories/
