关于数据结构与算法:字符串

反转字符串

leetcode.344

• 链接 https://leetcode.cn/problems/…
• 解题办法：双指针
  l，r 指针别离放在字符串的首尾两端，每次替换两个字符
  每替换一次指针向两头挪动一位

• leetcode 解题代码

  class Solution {
  public:
    void reverseString(vector<char>& s) {int l = 0, r = s.size() - 1;
        while (l < r){swap(s[l], s[r]);
            l ++, r --;
        }
    }
  };

leetcode.541

• 链接 https://leetcode.cn/problems/…
• 解题办法：双指针
  定义保护的区间 [l, r]，每次保护 2k 个数

• leetcode 解题代码

  class Solution {
  public:
    string reverseStr(string s, int k) {int n = s.size();
        for (int i = 0; i < n - 1; i += k * 2){int l = i, r = min(i + k, n);
            reverse(s.begin() + l, s.begin() + r);
        }
        return s;
    }
  };

反转字符串中的单词

• 题目类型：给一个字符串组成的句子 (带空格或标点)，而后对句中单个字符串进行一系列解决
• 这类题目能够分为两类，一类是有前置或者后置空格的，另一类是没有前置和后置空格的

leetcode.58

• 链接 https://leetcode.cn/problems/…
• 解题办法：创立一个长期字符串（用来存每一个单词），和一个答案数组
  遍历原字符串，如果遍历到空格，判断长期字符串是否为空
  如果长期字符串非空则阐明曾经遍历完一个单词，将其退出答案数组中并清空长期字符串
  如果遍历到的不是空格，将其退出长期字符串中

• leetcode 解题代码

  class Solution {
  public:
    int lengthOfLastWord(string s) {
        s += " ";// 在字符串开端加上一个空格避免脱漏最初一个单词
        string temp = "";
        vector<string> res;
        for (auto c: s){if (c == ' '){if (!temp.empty()){res.push_back(temp);
                    temp.clear();}
            }
            else temp += c;
        }
        if (res.empty()) return 0;
        return res.back().size();
    }
  };

leetcode.557

• 链接 https://leetcode.cn/problems/…
• 解题办法：与上一题相似

• leetcode 解题代码

  class Solution {
  public:
    string reverseWords(string s) {
        s += " ";
        string temp = "";
        vector<string> res;
        for (auto c: s){if (c == ' '){if (!temp.empty()){res.push_back(temp);
                    temp.clear();}
            }
            else temp += c;
        }
        s.clear();
        for (auto c: res){reverse(c.begin(), c.end());
            s += c + ' ';
        }
        s.pop_back();// 一开始加了一个空格记得删掉
        return s;
    }
  };

剑指 offer.58(leetcode.151)

• 链接 https://leetcode.cn/problems/…
  https://leetcode.cn/problems/…
• 解题办法：与上一题相似

• leetcode 解题代码

  class Solution {
  public:
    string reverseWords(string s) {
        s += " ";
        string temp;
        vector<string> res;
        for (auto c: s){if (c == ' '){if (!temp.empty()){res.push_back(temp);
                    temp.clear();}
            }
            else temp += c;
        }
        s.clear();
        reverse(res.begin(), res.end());
        for (auto c: res){s += c + ' ';}
        s.pop_back();
        return s;
    }
  };

• ACM 模式调试

输出字符串 s

the sky is blue

输入

blue is sky the

调试代码

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

int main(){
    string s;
    getline(cin, s);
    
    s += ' ';
    string temp;
    vector<string> res;
    for (auto c: s){if (c == ' '){if (!temp.empty()){res.push_back(temp);
                temp.clear();}
        }
        else temp += c;
    }
    
    s.clear();
    reverse(res.begin(), res.end());
    for (auto c: res){s += c + ' ';}
    s.pop_back();
    
    cout << s << endl;
    return 0;
}

字符串中的其余操作（替换空格，旋转字符串等）

剑指 offer.05

• 链接 https://leetcode.cn/problems/…
• 解题办法：翻新新字符串，遍历原字符串找到空格替换即可

• leetcode 解题代码

  class Solution {
  public:
    string replaceSpace(string s) {
        string res;
        for (auto c: s){if (c == ' '){res += "%20";}
            else res += c;
        }
        return res;
    }
  };

leetcode.796

• 链接 https://leetcode.cn/problems/…
• 解题办法：如果字符串 goal 能通过字符串 s 旋转失去
  那么字符串 goal 肯定是字符串 s + s 的字串，工夫复杂度为 O(n^2)
  （本题能够用 KMP 和字符串哈希求解，工夫复杂度能够降到 O(n)）

• leetcode 解题代码

  class Solution {
  public:
    bool rotateString(string s, string goal) {if (s.size() != goal.size()) return false;
        s += s;
        return s.find(goal) != std::string::npos;
    }
  };

剑指 offer.58

• 链接 https://leetcode.cn/problems/…
• 解题办法：整体旋转
  别离旋转前半部分和后半局部

• leetcode 解题代码

  class Solution {
  public:
    string reverseLeftWords(string s, int n) {reverse(s.begin(), s.end());
        reverse(s.begin(), s.end() - n);
        reverse(s.end() - n, s.end());
        return s;
    }
  };

  解题参考：https://www.acwing.com/
  刷题程序参考：https://www.programmercarl.com/