算法题解-字符串-CCI

2019-10-27 本文已影响0人 Panverson

最近发现了一个在网上评价很高的面试指南《程序员面试金典》（现在好像已经出了第六版）。然后在牛客上发现了这本书中的算法题的在线练习：https://www.nowcoder.com/ta/cracking-the-coding-interview?page=1。书还没买，也没看，先做做看算法题（我一般情况下只用C++做，C++做不出来再试Python）。今天AC了5道字符串题。

1.1 确定字符互异

题目描述
请实现一个算法，确定一个字符串的所有字符是否全都不同。 $\color{red}{这里我们要求不允许使用额外的存储结构}$ 。
给定一个string iniString，请返回一个bool值,True代表所有字符全都不同，False代表存在相同的字符。保证字符串中的字符为ASCII字符。字符串的长度小于等于3000。
测试样例：
"aeiou"
返回：True

"BarackObama"
返回：False
思路：
这道题限制了不允许使用额外的存储空间，不然可以直接遍历一遍字符串，用一个hash记录遍历过的部分出现过的字符的次数。如果有一个次数大于1了，直接结束遍历，返回false，这种方法的复杂度是 $O(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 原串翻转

题目描述
请实现一个算法，在不使用额外数据结构和储存空间的情况下，翻转一个给定的字符串(可以使用单个过程变量)。
给定一个string iniString，请返回一个string，为翻转后的字符串。保证字符串的长度小于等于5000。
测试样例：
"This is nowcoder"
返回："redocwon si sihT"
思路：这题的难度也在于不允许使用额外的空间来存储数据。如果能够用额外的空间，直接将输入字符串倒序存入一个新的字符串即可。限制空间的情况下，用左右指针指向字符串的头和尾，然后交换两个指针指向的元素。

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) { //结束条件
            tmp = iniString[l];
            iniString[l] = iniString[r];
            iniString[r] = tmp;
            l++;
            r--;
        }
        return iniString;
    }
};

1.3 确定两串乱序同构

题目描述
给定两个字符串，请编写程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。这里规定大小写为不同字符，且考虑字符串中的空格。
给定一个string stringA和一个string stringB，请返回一个bool，代表两串是否重新排列后可相同。保证两串的长度都小于等于5000。
测试样例：
"This is nowcoder","is This nowcoder"
返回：true

"Here you are","Are you here"
返回：false
思路：这题没有限制使用额外存储空间。那就直接hash分别记录两个字符串中字符出现的次数，如果两个hash表完全一致，就是乱序同构的，复杂度 $O(n)$ 。

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>标准库里面的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 基本字符串压缩

题目描述
利用字符重复出现的次数，编写一个方法，实现基本的字符串压缩功能。比如，字符串“aabcccccaaa”经压缩会变成“a2b1c5a3”。若压缩后的字符串没有变短，则返回原先的字符串。
给定一个string iniString为待压缩的串(长度小于等于10000)，保证串内字符均由大小写英文字母组成，返回一个string，为所求的压缩后或未变化的串。
测试样例
"aabcccccaaa"
返回："a2b1c5a3"

"welcometonowcoderrrrr"
返回："welcometonowcoderrrrr"
思路：
思路也很清晰：遍历字符串，两个指针，一个指针p指向开始的字符，一个指针e从开始字符向后遍历。当s[p] == s[e]的时候只需要e向后继续遍历，直到遇到s[p] != s[e]时结束此次遍历，并记录e和p的差和当前s[p]的值，然后将s[p]和e-p的值拼接进压缩的字符串即可。
但是还存在一些问题。一开始我只考虑到把e-p + ‘0’转成字符型push_back进ans，没有想到 e-p > 9 的时候，e-p + ‘0’就已经不是数字了。再考虑e-p>0的情况又显得特别复杂。所以用<sstream>库直接通过流把 int 转成 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;
    }
};