[数据结构与算法]必刷算法题之字符串（题目及代码）---C++

第1题： 执行操作后的变量值

题目描述：

解题思路：
这题比较简单，由于给出的是字符串数组，因此依次比较每个字符串的内容即可。注意字符串用的是双引号。

解题代码如下：

class Solution {
public:
    int finalValueAfterOperations(vector<string>& operations) {
        int x = 0;
        for(int i = 0;i < operations.size();i++){
            if("X++"==operations[i]||"X++"==operations[i]){
                x+=1;
            }else{
                x-=1;
            }
        }
        return x;
    }
};

第2题：罗马数字转整数

题目描述：

解题思路：

解题代码如下：

class Solution {
private:
    unordered_map<char,int> roman = {    //定义哈希表，用于字符匹配
        {'I',1},
        {'V',5},
        {'X', 10},
        {'L', 50},
        {'C', 100},
        {'D', 500},
        {'M', 1000},
    };
public:
    int romanToInt(string s) {
        int res=0;
        for(int i = 0;i < s.length();i++){
            int value = roman[s[i]];
            if(i < s.length()-1 && value < roman[s[i+1]]){
                res-=value;   //如果后面的数更大，说明要减去当前的数
            }else{
                res+=value;
            }
        }
        return res;
    }
};

第3题：句子中的最多单词数

题目描述：

解题思路：
计算空格数量
由于一个句子开头结尾均不含空格，且单词之间均只含一个空格，因此一个句子中的单词数一定等于空格数加上 1。
下面我们给出两种解法：
解题代码如下：

class Solution {
public:
    int mostWordsFound(vector<string>& sentences) {
        int res = 0;
        for(int i = 0;i < sentences.size();i++){
            int temp = 0;  //每个句子中的单词数
            for(int j = 0;j < sentences[i].size();j++){
                if(' '==sentences[i][j]){
                    temp++;
                } 
            }
            res=max(res,temp+1);
        }
        return res;
    }
};

------------这种方法用到了count()函数，用于计算字符串中某成员出现的次数-------
class Solution {
public:
    int mostWordsFound(vector<string>& sentences) {
        int res = 0;
        for (const string& sentence: sentences) {
            // 单词数 = 空格数 + 1
            int cnt = count(sentence.begin(), sentence.end(), ' ') + 1;
            res = max(res, cnt);
        }
        return res;
    }
};

第4题：左旋转字符串

题目描述：

解题思路：
把原始数组下标为n到最后一位的元素赋给目标数组从第0位到第s.length()-n位的元素。
然后在把原始数组从第0位到第n-1位置元素赋给目标数组下标为n到最后一位的元素。

注意
一开始的时候为什么要让res=s;，是因为如果不给res分配长度空间的话，会出问题。

解题代码如下：

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        string res=s;
        for(int i = 0;i < s.length()-n;i++){   //目标字符串数组的前s.length()-n个元素是原来数组的后s.length()-n个元素
            res[i]=s[i+n];
        }
        for(int j = 0;j < n;j++){
            res[s.length()-n+j]=s[j];
        }
        return res;
    }
};

第5题：宝石与石头

题目描述：

解题思路：
关于这道题我们给出三种解法，其中解法三是对解法二的优化。
解法一：暴力搜索法
这种方法不用多说，时间复杂度是O(mn)，其中m和n分别是石头和宝石的规模。
解题代码如下：

------------------解法一--------------------
class Solution {
public:
    int numJewelsInStones(string jewels, string stones) {
        int res = 0;
        for(int i = 0;i < stones.length();i++){
            for(int j = 0;j < jewels.length();j++){
                if(stones[i]==jewels[j]){
                    res++;
                }
            }
        }
        return res;
    }
};

解法二：利用哈希表
我们首先可以把宝石存在哈希表中，然后遍历我们手中的石头，如果这个石头在哈希表中出现过，那么宝石的数量+1。
这里我们用到了map结构
解题代码如下：

------------------解法二--------------------
class Solution {
public:
    int numJewelsInStones(string jewels, string stones) {
        unordered_map<char,int> jew;  
        int res = 0;
        for(int i = 0;i < jewels.length();i++){
            jew[jewels[i]]=i+1;    //为什么要+1，不需要解释了
        }
        for(int i = 0;i < stones.length();i++){
            if(jew[stones[i]]>0){
                res++;
            }
        }
        return res;
    }
};

优化
很容易的可以发现，我们压根没必要用到键值对，其实用集合set就行。
map和set都是stl中的关联容器，map以键值对的形式存储，key=value组成pair，是一组映射关系。set只有值，可以认为只有一个数据，并且set中元素不可以重复且自动排序。
解题代码如下：

-------------------解法三--------------------------------------
class Solution {
public:
    int numJewelsInStones(string jewels, string stones) {
        unordered_set<char> jew;
        int res = 0;
        for(int i = 0;i < jewels.length();i++){
            char a = jewels[i];
            jew.insert(a);
        }
        for(int i = 0;i < stones.length();i++){
            char b = stones[i];
            if(jew.count(b)){   //使用count()判断元素是否在set容器中。若在:返回1,若不在,返回0。 
                res++;
            }
        }
        return res;
    }
};

第6题： Excel 表中某个范围内的单元格

题目描述：

解题思路：
首先要注意提示中给出的范围信息。
然后通过观察例1中的返回值我们可以发现字母是在前的，数字是在后的，这确定了循环的次序。
小提示： for循环不仅仅可用于数字从1-10或者从1到100的循环，还可以用于char型数组的循环。
解题代码如下：

class Solution {
public:
    vector<string> cellsInRange(string s) {
        vector<string> res;
        for(char i = s[0];i <= s[3];i++){      // for循环不只是用于int型的数据
            for(char j = s[1];j <= s[4];j++){
                string l;
                l=i;
                l+=j;
                res.push_back(l);
            }
        }
        return res;
    }
};

第7题：括号的最大嵌套深度

题目描述：

解题思路：
首先虽然这道题看上去很复杂的样子，但实际上通过看示例我们就能发现其实这道题很简单

• 遍历字符串 s，定义Size用于记录左括号的数量，res记录出现过的最大深度。
• 假设从左往右开始遍历，遇到左括号1，同时更新当前的深度，遇到右括号则-1
• 直到遍历结束为止

小提示： for循环不仅仅可用于数字从1-10或者从1到100的循环，还可以用于char型数组的循环。
解题代码如下：

class Solution {
public:
    int maxDepth(string s) {
        int Size = 0,res = 0;
        for(int i = 0;i < s.length();i++){
            if(s[i] == '('){
                ++Size;
                res = max(res,Size);
            }
            if(s[i] == ')'){
                --Size;
            }            
        }
        return res;
    }
};

第8题：分割平衡字符串

题目描述：

解题思路：
首先注意观察最后一个示例，当然其实也没啥好注意的。

• 记录R和L出现的次数
• 如果两者相等，就将他们分割，分割的次数加1。（注意要大于0才行，因为一开始赋值时0，两者相等）
• 将R和L中的数进行重置，直到遍历结束为止

解题代码如下：

class Solution {
public:
    int balancedStringSplit(string s) {
        int R = 0,L = 0,res = 0;
        for(char a:s){
            if(a == 'R'){
                ++R;
            }else{
                ++L;
            }
            if(R == L && R > 0){
                ++res;     //说明R和L的数量相等了
                R = 0;     //重置R和L的数量
                L = 0;
            }
        }
        return res;
    }
};

第9题：最长公共前缀

题目描述：

解题思路：

• 将数组中第一个字符串与其它位置的进行比较
• 从第一个字符开始比较，如果和后续位置的字符都一样，那么保存这个字符到公共前缀中。如果遇到不一样的，则终止，返回先前保存的公共前缀。

解题代码如下：

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
    	if (!strs.size()) {
            return "";
        }
        string temp,res;        //temp用于保存临时比较的字符，
        for(int a = 0;a < strs[0].size();a++){
            temp += strs[0][a];    //如果不用temp,那么后面的字符如果不相同，就会多出这个数
            for(int i = 1;i < strs.size();i++){
                if(temp[a] != strs[i][a] && a==0){
                    return "";
                }
                if(temp[a] != strs[i][a]){
                    return res;
                }
            }
            res = temp;        //将比较完毕后的temp返回
        }
        return res;
    }
};

优化
我们可以找到最短的字符串数组，这样再与其它数组进行比较就会快很多
解题代码如下：

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (!strs.size()) {
            return "";
        }
        string temp,res;        //temp用于保存临时比较的字符，
        int min_number=INT_MAX,min=0;        //寻找下标最小的字符串
        for(int i=0;i<strs.size();i++){      
            if(min_number <= strs[i].size()){
                min_number = strs[i].size();
                min = i;                 //更新下标
            }
        }
        for(int a = 0;a < strs[min].size();a++){
            temp += strs[0][a];    //如果不用temp,那么后面的字符如果不相同，就会多出这个数
            for(int i = 1;i < strs.size();i++){
                if(temp[a] != strs[i][a] && a==0){
                    return "";
                }
                if(temp[a] != strs[i][a]){
                    return res;
                }
            }
            res = temp;        //将比较完毕后的temp返回
        }
        return res;
    }
};

第10题：IP 地址无效化

题目描述：

解题思路：
这题很简单，直接替换即可，然后返回替换后的字符串
还有一种方法使用到了replace()函数的，这里不展示了。
解题代码如下：

class Solution {
public:
    string defangIPaddr(string address) {
        //可以把address中的值赋给a，然后判断是否为.，如果为.那么将[.]赋给a
        string a,res;
        for(char s:address){
            a = s;
            if(a == "."){
                a = "[.]";
            }
            res += a;
        }
        return res;
    }
};

第11题：反转字符串 II

题目描述：

解题思路：
这题采用模拟法进行求解。每隔2k个字符就对前k个字符进行反转。

解题代码如下：

class Solution {
public:
    string reverseStr(string s, int k) {
        // 1. 每隔 2k 个字符的前 k 个字符进行反转
        for (int i = 0; i < s.size(); i += (2 * k)) {
            if (s.size() >= i + k) {  //2.如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
                reverse(s.begin() + i, s.begin() + i + k );
                continue;
            }
            if(s.size() < i + k){   //3.如果剩余字符少于k个，则将剩余字符全部反转。
                reverse(s.begin() + i, s.begin() + s.size());
            }  
        }
        return s;
    }
};

补充，这里可以自己定义一个reverse（）函数，就当作是复习了。

class Solution {
public:
    void reverse(string& s, int start, int end) {  //左闭右闭区间
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += (2 * k)) {
            if (s.size() >= i + k) { 
                reverse(s, i, i + k -1);    // 左闭右闭区间，所以要-1
                continue;
            }
            if(s.size() < i + k){ 
                reverse(s, i, s.size() -1);;
            }  
        }
        return s;
    }
};

第12题：替换空格

题目描述：

解题思路：
不推荐的方法，使用s.replace(" “,”%20");
原本是想对string s，进行遍历然后直接替换的，
即判断s[i]是否等于’ '，如果是，则s[i] = ‘%20’ 。但是这样是不行的，只能插入一个%，如果用s[i] = “%20” ，则又会说报错，说不允许string赋值给char。
正解

• 定义一个string res，用于接收s中的值，
• 遇到s中的值为’ '，则直接+=“%20”。

解题代码如下：

class Solution {
public:
    string replaceSpace(string s) {
        string res;
        for(int i = 0; i < s.length(); i++){
            if(s[i] != ' '){
                res+=s[i];
            }else res += "%20";
        }
        return res;
    }
};

上述方法的时间和空间复杂度都为O(N),由于C++可以对字符串进行拓展，因此还有更节省空间的方法。感兴趣的小伙伴可以点击这里方法二：原地修改

第13题：颠倒字符串中的单词

题目描述：

解题思路：
本题有三种解法，个人最喜欢解法3，也好理解。
解法1，不推荐
使用split库函数，分隔单词，然后定义一个新的string字符串，最后再把单词倒序相加，不过这样做的话，这道题就失去了它的意义。
解法2，推荐
将整个字符串都反转过来，那么单词的顺序指定是倒序了，只不过单词本身也倒序了，那么再把单词反转一下，单词不就正过来了。

• 移除多余空格
• 将整个字符串反转
• 将每个单词反转

移除多余空格
用erase库函数移除空格的话，时间复杂度为O(n2)，因为erase的时间复杂度为O(n)。

void removeExtraSpaces(string& s) {
	// 删除相邻都为空格的前一个元素
    for (int i = s.size() - 1; i > 0; i--) {
        if (s[i] == s[i - 1] && s[i] == ' ') {
            s.erase(s.begin() + i);
        }
    }
    // 删除字符串最后面的空格
    if (s.size() > 0 && s[s.size() - 1] == ' ') {
        s.erase(s.begin() + s.size() - 1);
    }
    // 删除字符串最前面的空格
    if (s.size() > 0 && s[0] == ' ') {
        s.erase(s.begin());
    }
}

因此 建议使用双指针法来去移除空格，最后resize（重新设置）一下字符串的大小，就可以做到O(n)的时间复杂度。
双指针法（快慢指针法） 在数组和链表的操作中是非常常见的，很多考察数组、链表、字符串等操作的面试题，都使用双指针法。
以下面这张图为例：这题为leetcode中的27题. 移除元素 。可以看到，fastIndex走的快，slowIndex走的慢，最后slowIndex就标记了新字符串的长度。

针对本题，双指针的解题代码如下：

void removeExtraSpaces(string& s) {
    int slowIndex = 0, fastIndex = 0; // 定义快指针，慢指针
    // 去掉字符串前面的空格
    while (s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ') {
        fastIndex++;
    }
    for (; fastIndex < s.size(); fastIndex++) {
        // 去掉字符串中间部分的冗余空格
        if (fastIndex - 1 > 0
                && s[fastIndex - 1] == s[fastIndex]
                && s[fastIndex] == ' ') {
            continue;
        } else {
            s[slowIndex++] = s[fastIndex];
        }
    }
    if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') { // 去掉字符串末尾的空格
        s.resize(slowIndex - 1);
    } else {
        s.resize(slowIndex); // 重新设置字符串大小
    }
}

总的代码如下：

class Solution {
public:
    // 反转字符串s中左闭又闭的区间[start, end]
    void reverse(string& s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }

    // 移除冗余空格：使用双指针（快慢指针法）O(n)的算法
    void removeExtraSpaces(string& s) {
        int slowIndex = 0, fastIndex = 0; // 定义快指针，慢指针
        // 去掉字符串前面的空格
        while (s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ') {
            fastIndex++;
        }
        for (; fastIndex < s.size(); fastIndex++) {
            // 去掉字符串中间部分的冗余空格
            if (fastIndex - 1 > 0
                    && s[fastIndex - 1] == s[fastIndex]
                    && s[fastIndex] == ' ') {
                continue;
            } else {
                s[slowIndex++] = s[fastIndex];
            }
        }
        if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') { // 去掉字符串末尾的空格
            s.resize(slowIndex - 1);
        } else {
            s.resize(slowIndex); // 重新设置字符串大小
        }
    }

    string reverseWords(string s) {
        removeExtraSpaces(s); // 去掉冗余空格
        reverse(s, 0, s.size() - 1); // 将字符串全部反转
        int j = 0; //单词的起始位置
        for (int i = 1; i < s.size(); ++i) {
            if (s[i] == ' ') {         //i == ''说明已经匹配到单词的结束位置了
                reverse(s, j, i - 1);  //反转单词
                j = i + 1;             //下一个单词的起始位置
            }
        }
        reverse(s, j, s.size() - 1);  //反转最后一个单词
        return s;
    }
};

解法3，牛掰

涉及到反转的问题，通常都可以用到栈结构进行巧妙的求解。

• 定义一个string类型的栈结构，以及一个string word。word用于插入栈结构
• 从头开始遍历s，从不为’ ‘的元素开始，将当前字符拼接到word中，判断i+1是否为’ '，如果是，说明这个单词结束了，然后将word插入到栈中，再将word清零
• 待s遍历完毕之后，将栈空间的所有元素弹出，记住，每弹出一个，要加上一个’ '（末尾单词除外）

解题代码如下：

class Solution {
public:
    string reverseWords(string s) {
        stack <string> stk;  //定义一个string栈，栈中的每个元素就是一个单词
        int n = s.size();
        string word;
        for (int i = 0; i < n; ++i){//先遍历字符串，提前单词，word入栈
            if (s[i] != ' '){      //利用这个可以找到每个单词的开头
                word += s[i];
                if (i ==  n-1 || s[i+1] == ' '){//关键判断条件：什么时候入栈，当字母后有空格或已是最后一个则判断为word，入栈
                    stk.push(word);
                    word = "";     //重置word，以便下次使用
                }
            }
        }
        string ans;
        while (!stk.empty()){//释放栈中元素，加入空格组成反转后结果
            ans += stk.top();
            stk.pop();
            if (!stk.empty()){
                ans += ' ';  
            }  
        }
         return ans;
    }
};

导航链接：必刷算法题—二分查找篇（C++）
导航链接：必刷算法题—排序篇（C++）
导航链接：必刷算法题—哈希篇(C++)
导航链接：剑指—动态规划篇（C++）
导航链接：剑指—链表篇（C++）
导航链接：剑指—队列&栈篇（C++）
导航链接：剑指—树篇（C++）

注： 以上题目都是在牛客网或是leetcode中刷的，有自己做的，也有不会做看别人精华解题思路，然后总结的。如果侵犯了您的权益，请私聊我。
最后，觉得本文内容对你有所帮助的话，感谢您能点赞收藏，在我的剑指offer专栏还有相关的算法刷题文章，等待您的阅读！

阅读世界，共赴山海

423全民读书节，邀你共读