力扣2315题：统计星号的有效数量 - 状态标记解法详解

内容简介

本文详细解析了力扣2315题"统计星号的有效数量"的巧妙解法。通过状态标记法处理字符串中的竖线对，实现了只统计竖线对之外的星号数量的功能。文章包含完整注释代码、算法思路讲解和复杂度分析，帮助读者掌握字符串处理的实用技巧。

算法思路

‌一、状态标记‌：使用布尔变量标记当前是否处于竖线对之间

二、字符遍历‌：

    1.遇到竖线：切换状态标记

    2.遇到星号：只在非竖线对区域内计数

‌三、结果统计‌：最终统计的星号数量即为有效数量

代码实现（带详细注释）

class Solution {
public:
    int countAsterisks(string s) {
        bool flag = true;  // 状态标记，true表示不在竖线对之间
        int cnt = 0;       // 星号计数器
        
        // 遍历字符串中的每个字符
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '|') {      // 遇到竖线字符
                flag = !flag;       // 切换状态标记
                continue;           // 跳过后续处理
            }
            if (flag && s[i] == '*') {  // 当前不在竖线对之间且字符是星号
                cnt++;                  // 增加星号计数
            }
        }
        return cnt;  // 返回有效星号数量
    }
};

复杂度分析

‌时间复杂度‌：O(n)，只需遍历字符串一次

‌空间复杂度‌：O(1)，仅使用常数个额外变量

优化方向

‌位运算优化‌：可以使用位运算替代布尔变量切换

‌并行处理‌：对超长字符串可考虑分段并行处理

‌提前终止‌：当剩余字符不可能包含更多有效星号时可提前终止

总结

字符串星号统计问题是状态标记法的典型应用场景，通过简单的状态切换可以高效实现题目要求。理解这种解法有助于掌握字符串处理的基本技巧和状态管理的思想。

参考：力扣2315题 解题思路和步骤 C++实现带注释,c++题库编程题