C语言LeetCode二进制字符串分割最大得分代码错误排查求助

问题回顾 #

给定仅包含0和1的字符串s，将其分割为两个非空子串（左、右子串），得分定义为左子串中0的数量加上右子串中1的数量，返回最大得分。你的代码在输入"110000"时输出1，正确结果应为3，错误点如下：

错误点1：无效的分割范围 #

你的外层循环for(int n=0;n<length;n++)包含了n = length-1的情况，此时右子串为空，不符合题目要求的“两个非空子串”。这种无效分割的得分会被存入数组，但我们不需要考虑它。

正确的循环范围应该是n从0到length-2（即n < length-1），保证右子串至少有一个字符。

错误点2：最大值查找逻辑错误 #

你当前查找最大值的嵌套循环逻辑存在缺陷：

int ans=arr[0];
for(int i=0;i<length-1;i++)
{
    for(int j=i+1;j<length;j++)
    {
        if(arr[i]>arr[j] && arr[i]>ans)
        {
            ans=arr[i];
        }
    }
}

这个逻辑只会在arr[i]同时大于arr[j]和当前ans时才更新ans，完全漏掉了arr[j]比ans大的情况。比如在输入"110000"时，有效得分里的最大值是3（对应n=4），但你的循环根本不会把ans更新到3，因为没有触发条件。

修正后的代码 #

我们可以优化代码，不需要用数组存储所有得分，边计算边更新最大值，节省内存：

int maxScore(char* s) {
    int length = strlen(s);
    int max = 0;
    
    // 遍历所有有效分割点（n从0到length-2）
    for(int n = 0; n < length - 1; n++){
        int zero_count = 0;
        int one_count = 0;
        
        // 统计左子串的0数量
        for(int i = 0; i <= n; i++){
            if(s[i] == '0'){
                zero_count++;
            }
        }
        
        // 统计右子串的1数量
        for(int j = n + 1; j < length; j++){
            if(s[j] == '1'){
                one_count++;
            }
        }
        
        int current_score = zero_count + one_count;
        // 更新最大值
        if(current_score > max){
            max = current_score;
        }
    }
    
    return max;
}

进一步优化（可选） #

上面的代码时间复杂度是O(n²)，可以优化到O(n)：

1. 先统计整个字符串中1的总数
2. 遍历分割点，左子串每遇到一个0就加1，每遇到一个1就从总1数里减1（因为这个1被分到左子串，右子串的1数就少了一个）
3. 实时计算当前得分，更新最大值

优化后的代码：

int maxScore(char* s) {
    int length = strlen(s);
    int total_ones = 0;
    
    // 统计总1的数量
    for(int i = 0; i < length; i++){
        if(s[i] == '1'){
            total_ones++;
        }
    }
    
    int max_score = 0;
    int left_zeros = 0;
    
    // 遍历有效分割点
    for(int n = 0; n < length - 1; n++){
        if(s[n] == '0'){
            left_zeros++;
        } else {
            total_ones--; // 当前1被分到左子串，右子串的1数减少
        }
        int current_score = left_zeros + total_ones;
        if(current_score > max_score){
            max_score = current_score;
        }
    }
    
    return max_score;
}

内容的提问来源于stack exchange，提问作者Neeraj Mansingh