最近發(fā)現(xiàn)了一個在網(wǎng)上評價很高的面試指南《程序員面試金典》（現(xiàn)在好像已經(jīng)出了第六版）。然后在?？蜕习l(fā)現(xiàn)了這本書中的算法題的在線練習(xí)：https://www.nowcoder.com/ta/cracking-the-coding-interview?page=1。書還沒買，也沒看，先做做看算法題（我一般情況下只用C++做，C++做不出來再試Python）。今天AC了5道字符串題。

1.1 確定字符互異

題目描述
請實現(xiàn)一個算法，確定一個字符串的所有字符是否全都不同。。
給定一個string iniString，請返回一個bool值,True代表所有字符全都不同，F(xiàn)alse代表存在相同的字符。保證字符串中的字符為ASCII字符。字符串的長度小于等于3000。
測試樣例：
"aeiou"
返回：True

"BarackObama"
返回：False
思路：
這道題限制了不允許使用額外的存儲空間，不然可以直接遍歷一遍字符串，用一個hash記錄遍歷過的部分出現(xiàn)過的字符的次數(shù)。如果有一個次數(shù)大于1了，直接結(jié)束遍歷，返回false，這種方法的復(fù)雜度是。但是不能使用額外的空間就只能暴力求解了。用兩層循環(huán)：

class Different {
public:
    bool checkDifferent(string iniString) {
        // write code here
        int len = iniString.size();
        bool flag = true;
        for(int i=0; i<len; i++)
            for(int j=i+1; j<len; j++)
                if(iniString[i] == iniString[j]) {
                    flag = false;
                }
        return flag;
    }
};

1.2 原串翻轉(zhuǎn)

題目描述
請實現(xiàn)一個算法，在不使用額外數(shù)據(jù)結(jié)構(gòu)和儲存空間的情況下，翻轉(zhuǎn)一個給定的字符串(可以使用單個過程變量)。
給定一個string iniString，請返回一個string，為翻轉(zhuǎn)后的字符串。保證字符串的長度小于等于5000。
測試樣例：
"This is nowcoder"
返回："redocwon si sihT"
思路：這題的難度也在于不允許使用額外的空間來存儲數(shù)據(jù)。如果能夠用額外的空間，直接將輸入字符串倒序存入一個新的字符串即可。限制空間的情況下，用左右指針指向字符串的頭和尾，然后交換兩個指針指向的元素。

class Reverse {
public:
    string reverseString(string iniString) {
        // write code here
        int len = iniString.size();
        char tmp;
        int l = 0, r = len-1;
        while(l < r) { //結(jié)束條件
            tmp = iniString[l];
            iniString[l] = iniString[r];
            iniString[r] = tmp;
            l++;
            r--;
        }
        return iniString;
    }
};

1.3 確定兩串亂序同構(gòu)

題目描述
給定兩個字符串，請編寫程序，確定其中一個字符串的字符重新排列后，能否變成另一個字符串。這里規(guī)定大小寫為不同字符，且考慮字符串中的空格。
給定一個string stringA和一個string stringB，請返回一個bool，代表兩串是否重新排列后可相同。保證兩串的長度都小于等于5000。
測試樣例：
"This is nowcoder","is This nowcoder"
返回：true

"Here you are","Are you here"
返回：false
思路：這題沒有限制使用額外存儲空間。那就直接hash分別記錄兩個字符串中字符出現(xiàn)的次數(shù)，如果兩個hash表完全一致，就是亂序同構(gòu)的，復(fù)雜度。

class Same {
public:
    bool checkSam(string stringA, string stringB) {
        // write code here
        int A[1000], B[1000];
        for(int i=0; i<1000; i++) {
            A[i] = 0;
            B[i] = 0;
        }
        int la = stringA.size(), lb = stringB.size();
        for(int i=0; i<la; i++) {
            A[stringA[i]]++;
        }
        for(int i=0; i<lb; i++) {
            B[stringB[i]]++;
        }
        for(int i=0; i<1000; i++) {
            if(A[i] != B[i])
                return false;
        }
        return true;
    }
};

1.4 空格替換

題目描述
請編寫一個方法，將字符串中的空格全部替換為“%20”。假定該字符串有足夠的空間存放新增的字符，并且知道字符串的真實長度(小于等于1000)，同時保證字符串由大小寫的英文字母組成。
給定一個string iniString 為原始的串，以及串的長度 int len, 返回替換后的string。
測試樣例：
"Mr John Smith”,13
返回："Mr%20John%20Smith"

”Hello World”,12
返回：”Hello%20%20World”
思路：
這題只要用<string>標(biāo)準(zhǔn)庫里面的find()和replace()輕松秒殺，不用多說。

class Replacement {
public:
    string replaceSpace(string iniString, int length) {
        // write code here
        while(iniString.find(' ') != iniString.npos) {
            iniString.replace(iniString.find(' '), 1, "%20");
        }
        return iniString;
    }
};

1.5 基本字符串壓縮

題目描述
利用字符重復(fù)出現(xiàn)的次數(shù)，編寫一個方法，實現(xiàn)基本的字符串壓縮功能。比如，字符串“aabcccccaaa”經(jīng)壓縮會變成“a2b1c5a3”。若壓縮后的字符串沒有變短，則返回原先的字符串。
給定一個string iniString為待壓縮的串(長度小于等于10000)，保證串內(nèi)字符均由大小寫英文字母組成，返回一個string，為所求的壓縮后或未變化的串。
測試樣例
"aabcccccaaa"
返回："a2b1c5a3"

"welcometonowcoderrrrr"
返回："welcometonowcoderrrrr"
思路：
思路也很清晰：遍歷字符串，兩個指針，一個指針p指向開始的字符，一個指針e從開始字符向后遍歷。當(dāng)s[p] == s[e]的時候只需要e向后繼續(xù)遍歷，直到遇到s[p] != s[e]時結(jié)束此次遍歷，并記錄e和p的差和當(dāng)前s[p]的值，然后將s[p]和e-p的值拼接進壓縮的字符串即可。
但是還存在一些問題。一開始我只考慮到把e-p + ‘0’轉(zhuǎn)成字符型push_back進ans，沒有想到 e-p > 9 的時候，e-p + ‘0’就已經(jīng)不是數(shù)字了。再考慮e-p>0的情況又顯得特別復(fù)雜。所以用<sstream>庫直接通過流把 int 轉(zhuǎn)成 str，很方便。最后比較一下長度，完成。

class Zipper {
public:
    string zipString(string iniString) {
        // write code here
        int ls = iniString.size();
        stringstream ss;
        char flag;
        int p = 0, e = p + 1;
        while(p < ls) {
            flag = iniString[p];
            if(iniString[e] == iniString[p]) {
                e++;
            }
            else {
                ss << flag << e - p;
                p = e;
                e = p + 1;
            }
        }
        string ans = ss.str();
        int la = ans.size();
        if(la < ls)
            return ans;
        else
            return iniString;
    }
};