【算法】字符串问题

⭐️个人主页：@小羊 ⭐️所属专栏：基础算法 很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~

目录

• • 1、字符串
  • • 字符串相加
    • 验证回文字符串
    • 反转字符串
    • 字符串最后一个单词的长度
    • 字符串中的第一个唯一字符
    • 反转字符串中的单词
    • 最长公共前缀
    • 最长回文子串
    • 二进制求和
    • 字符串相乘
    • 回文字符串
  • 2、字符串哈希
  • • 两个数组的交集
    • 删除公共字符

1、字符串

字符串相加

• Leetcode——字符串相加

有时候我们需要非常大的数据相加时，整型的范围不够，就可以将数据转换为字符串的形式运算，再将结果转回为整型。
整型相加时是从后往前加的，这里的字符串相加我们也从后往前加。不断取出两个字符串的末尾字符，转换为整形后相加，再用+=追加到字符串末尾，其中还要考虑进位的情况。
因为string类支持operator[]，所以我们可以通过下标的方式遍历字符串。
其中两个字符串的第一位相加也可能有进位，所以循环结束后还需要判断进位是否为1。
因为我们是从后往前加的，所以最后还需要用reverse将字符串翻转过来。

class Solution {public: string addStrings(string num1, string num2) { string s; int n = 0; int end1 = num1.size() - 1; int end2 = num2.size() - 1; while (end1>=0 || end2>=0) { int n1 = end1>=0 ? num1[end1--] - \'0\' : 0; int n2 = end2>=0 ? num2[end2--] - \'0\' : 0; int ret = n1 + n2 + n; n = ret / 10; ret %= 10; s += ret + \'0\'; } if (n == 1) { s += \'1\'; } reverse(s.begin(), s.end()); return s; }};

用下标的方式从后往前遍历字符串，相加得到的值追加到字符串，最后再反转字符串。

验证回文字符串

• Leetcode——验证回文串

将字符串存到一个stack和一个queue中，循环比较top()，当栈和队列为空时则字符串回文，当某次top()不相等时则不回文。
用范围for遍历字符串，如果是符合我们要求的字符就插入栈和队列中。

class Solution {public: bool isPalindrome(string s) { for (auto e : s) { if ((e >= \'a\' && e <= \'z\') || (e >= \'0\' && e <= \'9\')) { _st.push(e); _qu.push(e); } if (e >= \'A\' && e <= \'Z\') { e += 32; _st.push(e); _qu.push(e); } } while (!_st.empty()) { if (_st.top() != _qu.front()) { return false; } _st.pop(); _qu.pop(); } return true; }private: stack<int> _st; queue<int> _qu;};

反转字符串

• Leetcode——反转字符串

只需要反转对应的区间就行，注意不能越界。

class Solution {public: string reverseStr(string s, int k) { for (size_t i = 0; i < s.size(); i += 2*k) { size_t n = i + k > s.size() ? s.size() : i + k; reverse(s.begin() + i, s.begin() + n); } return s; }};

字符串最后一个单词的长度

• 牛客——最后一个单词的长度

#include using namespace std;int main() { string s; getline(cin, s); size_t pos = s.rfind(\" \"); size_t length = s.size() - pos - 1; cout << length << endl;}

字符串中的第一个唯一字符

• Leetcode——字符串中的第一个唯一字符

这种类似计数的题可以用哈希映射的方法，首先定义一个用于计数的数组，然后将字符串映射到数组中，再通过遍历字符串得到下标间接遍历数组来找出为1的元素，返回下标。
定义数组时需要初始化为全0。

class Solution {public: int firstUniqChar(string s) { int arr[26] = {0}; for (auto e : s) { arr[e - \'a\']++; } for (size_t i = 0; i < s.size(); i++) { if (1 == arr[s[i] - \'a\']) { return i; } } return -1; }};

反转字符串中的单词

• Leetcode——反转字符串中的单词

reverse(s.begin(), s.end());
参数：双向迭代器，指向要反转的序列的初始和最终位置。使用的范围是[ )左闭右开。
从前往后遍历字符串，找\" \"空格的位置，用reverse反转单词。需要注意的是reverse的参数是左闭右开的。

class Solution {public: string reverseWords(string s) { int pos1 = 0; int pos2 = s.find(\" \", pos1); while (pos2 < s.size()) { reverse(s.begin() + pos1, s.begin() + pos2); pos1 = pos2 + 1; pos2 = s.find(\" \", pos1); } reverse(s.begin() + pos1, s.end()); return s; }};

最长公共前缀

• 最长公共前缀

class Solution {public: string longestCommonPrefix(vector<string>& strs) { string ret; int i = 0; while (true) { int flag = 1; char ch = strs[0][i]; for (auto& str : strs) { if (i == str.size() || ch != str[i]) {  flag = 0;  break; } } if (flag) ret += ch, i++; else break; } return ret; }};

最长回文子串

• 最长回文子串

注意 dp[i][j] 表示的是[i, j]区间内的子串是否回文。

class Solution {public: string longestPalindrome(string s) { int n = s.size(); vector<vector<bool>> dp(n, vector<bool>(n)); int begin = 0, len = 0; for (int j = 0; j < s.size(); j++) { for (int i = 0; i <= j; i++) { if (s[i] == s[j])  dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true; if (dp[i][j] && j - i + 1 > len) {  len = j - i + 1;  begin = i; } } } return s.substr(begin, len); }};

二进制求和

• 二进制求和

class Solution {public: string addBinary(string a, string b) { string ret; int i = a.size() - 1, j = b.size() - 1, t = 0; while (i >= 0 || j >= 0 || t) { if (i >= 0) t += a[i--] - \'0\'; if (j >= 0) t += b[j--] - \'0\'; ret += to_string(t % 2); t /= 2; } reverse(ret.begin(), ret.end()); return ret; }};

字符串相乘

• 字符串相乘

先无进位相乘相加，再处理进位。

class Solution {public: string multiply(string num1, string num2) { int n = num1.size(), m = num2.size(); vector<int> arr(n + m - 1); // 空间大小要对应 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { arr[i + j] += (num1[i] - \'0\') * (num2[j] - \'0\'); } } string ret; int k = 0; for (int i = n + m - 2; i >= 0; i--) { k += arr[i]; ret += (k % 10) + \'0\'; k /= 10; } if (k) ret += k + \'0\'; reverse(ret.begin(), ret.end()); // 处理前导0 if (ret.size() > 1 && ret.front() == \'0\') ret = \'0\'; return ret; }};

回文字符串

• 回文字符串

如果一个字符串原本不是回文串，但在字符串开头添加若干lqb字符就可以构成回文串，那么这个字符串去掉末尾只包含lqb的部分，剩下的子串必定是回文的。

#include using namespace std;bool check(const string& str){ int i = 0, j = str.size() - 1; while (i < j) { if (str[i] == str[j]) i++, j--; else if (str[j] == \'l\' || str[j] == \'q\' || str[j] == \'b\') j--; else if (str[i] == \'l\' || str[i] == \'q\' || str[i] == \'b\') i++; else return false; } return true;}int main(){ int t; cin >> t; while (t--) { string str; cin >> str; cout << (check(str) == true ? \"Yes\" : \"No\") << endl; } return 0;}

2、字符串哈希

两个数组的交集

• 两个数组的交集

这个题的关键是检查到有重复的值后把负责检查的数组对应位置的值设为false，表示已经检查过了。

class Solution {public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { vector<int> ret; bool check[1001] = {}; for (int i : nums1) check[i] = true; for (int i : nums2) { if (check[i]) { ret.push_back(i); check[i] = false; } } return ret; }};

删除公共字符

• 删除公共字符

#include using namespace std;int main(){ string s1, s2; getline(cin, s1); getline(cin, s2); int hash[200] = {}; for (auto ch : s2) hash[ch] = 1; for (auto ch : s1) if (!hash[ch]) cout << ch; return 0;}

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~