深入解析字符串刷题技巧：从基础到进阶

前言

字符串是编程中常见且重要的基础数据类型，特别是在刷题过程中，它经常与其他数据结构和算法相结合，成为关键的一环。本篇博客将系统性地探讨字符串相关的典型题目，分享高效的解题思路与技巧，帮助你在刷题时游刃有余。

✴️一、力扣LCR 192. 把字符串转换成整数 (atoi)

1.1 解法：

1. 初始化变量：
   • res：用于存储转换后的整数结果，初始化为0。
   • bndry：用于判断当前结果乘以10后是否可能溢出，初始化为INT_MAX / 10（即整数最大值的十分之一，用于检查在乘以10之前是否已接近溢出边界）。
   • i：字符串的索引，用于遍历字符串。
   • sign：符号变量，用于存储数字的正负，初始化为1（表示正数），如果遇到’-'则设置为-1。
   • length：字符串的长度。
2. 处理空字符串：如果字符串长度为0，直接返回0。
3. 跳过空格：使用while循环跳过字符串开头的空格字符。如果跳过所有空格后索引i等于字符串长度，说明字符串只包含空格，返回0。
4. 处理符号：检查当前字符是否为’-‘或’+‘，以确定数字的符号。如果是，将sign设置为-1（对于’-‘）或保持为1（对于’+'），并将索引i增加1以跳过符号字符。
5. 数字转换：从索引i开始遍历字符串的剩余部分。
   • 如果当前字符不是数字（即小于’0’或大于’9’），则跳出循环。
   • 在每次迭代中，检查res是否大于bndry，或者res等于bndry且当前字符大于’7’（因为如果res已经是INT_MAX / 10，那么只有当前字符小于或等于’7’时，res * 10 + (char - '0')才不会溢出）。如果满足这些条件之一，则返回INT_MAX（如果sign为1）或INT_MIN（如果sign为-1）。
   • 否则，将res乘以10并加上当前字符表示的数字（通过str[j] - '0'计算）。
6. 返回结果：返回sign * res，即考虑了符号的转换结果。

1.2 代码：

class Solution {
public:
    int myAtoi(string str) {
        int res = 0, bndry = INT_MAX / 10;
        int i = 0, sign = 1, length = str.size();
        if(length == 0) return 0;
        while(str[i] == ' ')
            if(++i == length) return 0;
        if(str[i] == '-') sign = -1;
        if(str[i] == '-' || str[i] == '+') i++;
        for(int j = i; j < length; j++) {
            if(str[j] < '0' || str[j] > '9') break;
            if(res > bndry || res == bndry && str[j] > '7')
                return sign == 1 ? INT_MAX : INT_MIN;
            res = res * 10 + (str[j] - '0');
        }
        return sign * res;
    }
};

✴️二、力扣415. 字符串相加

2.1 解法：

1. 初始化
   • i 和 j 分别用于遍历 num1 和 num2 字符串，从最后一个字符（即最低位）开始。
   • add 用于存储进位值，初始化为0。
   • res 是一个空字符串，用于存储相加的结果。
2. 循环条件
   • 循环继续执行，直到 i 和 j 都小于0，并且没有进位（add == 0）。
   • 这意味着只要有一个字符串还有字符未处理，或者还有进位需要加到下一轮，循环就会继续。
3. 字符到数字的转换
   • 使用条件表达式 (i >= 0) ? num1[i] - '0' : 0 将 num1 中当前位置的字符转换为对应的数字（如果 i 小于0，则默认为0）。
   • 同样地，对 num2 中的字符进行转换。
4. 计算当前位的和及进位
   • 将 x（来自 num1 的数字）、y（来自 num2 的数字）和 add（进位）相加，得到 sum。
   • sum % 10 是当前位的值（0-9），将其转换为字符并添加到 res 字符串中。
   • sum / 10 是新的进位值，存储到 add 中以供下一轮使用。
5. **移动到下一个字符：**将 i 和 j 分别减1，以移动到 num1 和 num2 的下一个较低位的字符。
6. **反转结果字符串：**由于我们是从低位到高位构建 res 字符串的，因此在循环结束后，需要使用 std::reverse 函数将其反转，以得到正确的数字顺序。
7. **返回结果：**返回构建并反转后的 res 字符串，即两个输入字符串表示的数字相加的结果。

2.2 代码：

class Solution {
public:
    string addStrings(string num1, string num2) {
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        int add = 0;
        string res = "";
        while(i >= 0 || j >= 0 || add != 0)
        {
            int x = i >= 0 ? num1[i] - '0' : 0;
            int y = j >= 0 ? num2[j] - '0' : 0;
            int sum = x + y + add;
            
            res.push_back(sum % 10 + '0');
            add = sum/10;
            --i;
            --j;
        }

        reverse(res.begin(), res.end());
        return res;
    }
};

✴️三、力扣344. 反转字符串

3.1 解法：

双指针（力扣官方题解）

对于长度为 N 的待被反转的字符数组，我们可以观察反转前后下标的变化，假设反转前字符数组为 s[0] s[1] s[2] ... s[N - 1]，那么反转后字符数组为 s[N - 1] s[N - 2] ... s[0]。比较反转前后下标变化很容易得出 s[i] 的字符与 s[N - 1 - i] 的字符发生了交换的规律，因此我们可以得出如下双指针的解法：

• 将 left 指向字符数组首元素，right 指向字符数组尾元素。
• 当 left < right：
  • 交换 s[left] 和 s[right]；
  • left 指针右移一位，即 left = left + 1；
  • right 指针左移一位，即 right = right - 1。
• 当 left >= right，反转结束，返回字符数组即可。

3.2 代码：

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

✴️四、力扣387. 字符串中的第一个唯一字符

4.1 解法：

1. 函数签名：int firstUniqChar(string s)：函数接受一个 string 类型的参数 s，并返回一个 int 类型的值。
2. **循环遍历字符串：**使用 for 循环遍历字符串 s 的每个字符，索引从 0 到 s.length() - 1。
3. 检查字符的唯一性：
   • 在循环内部，使用 s.find(s[i]) 来查找当前字符 s[i] 在字符串中第一次出现的位置。
   • 使用 s.rfind(s[i]) 来查找当前字符 s[i] 在字符串中最后一次出现的位置。
   • 如果这两个位置相同（s.find(s[i]) == s.rfind(s[i])），则意味着当前字符在字符串中只出现了一次。
4. **返回索引：**一旦找到只出现一次的字符，就立即返回其索引 i。
5. **处理未找到情况：**如果循环结束后没有找到只出现一次的字符，则返回 -1。

4.2 代码：

class Solution {
public:
    int firstUniqChar(string s) {
        for(int i = 0; i < s.length(); i++)
        {
            if(s.find(s[i]) == s.rfind(s[i]))
                return i; 
        }
        return -1;   
    }
};

✴️五、力扣125. 验证回文串

5.1 解法：

1. 函数签名：bool isPalindrome(string s)：函数接受一个 string 类型的参数 s，并返回一个 bool 类型的值，表示字符串是否是回文串。
2. **空字符串检查：**如果输入字符串 s 为空，则直接返回 true，因为空字符串被认为是回文串。
3. 构建处理后的字符串：
   • 定义一个空字符串 str，用于存储处理后的字符（只包含字母数字字符，且转换为小写）。
   • 使用范围 for 循环遍历输入字符串 s 中的每个字符 ch。
   • 使用 isalnum(ch) 函数检查字符是否是字母或数字。如果是，则使用 tolower(ch) 函数将其转换为小写，并添加到 str 中。
4. 双指针检查回文：
   • 定义两个整数 left 和 right，分别初始化为 0 和 str.size() - 1，表示处理后的字符串 str 的左右两端索引。
   • 使用 for 循环，在 left < right 的条件下，每次循环将 left 增加 1，将 right 减少 1，以向中间移动。
   • 在循环内部，如果 str[left] 不等于 str[right]，则立即返回 false，表示字符串不是回文串。
5. **返回结果：**如果循环结束后没有找到不匹配的字符，则返回 true，表示字符串是回文串。

5.2 代码：

class Solution {
public:
    bool isPalindrome(string s) {
        if(s.empty()) 
            return true;

        string str;
        for(char ch : s){
            if(isalnum(ch)){
                str += tolower(ch);
            }
        }

        int left = 0;
        int right = str.size() - 1;
        for(; left < right; left++, right--)
        {
            if(str[left] != str[right])
                return false;
        }
        return true;
    }
};

结语

通过对字符串问题的深入分析和多样的解法展示，相信你对这一类题目有了更清晰的理解。多加练习与总结，你会逐步提升处理字符串问题的能力，为后续刷题与实际开发打下坚实基础。