原题链接: AcWing

题目描述:

给定一个字符串 s，其中的每个字符要么是 1，要么是 0。 我们希望字符串中的所有 1 能够形成一个连续的子串，例如，字符串 0、1、00111、01111100 均满足此条件，而字符串 0101、100001、11111111111101 均不满足此条件。 你可以从字符串中删除一些（也可以不删）0，使得字符串满足上述条件。 请问，你必须删除的最小 0 数量是多少。

输入格式

第一行包含整数 T，表示共有 T 组测试数据。 每组数据占一行，包含一个 01 字符串 s。

输出格式

每组数据输出一行结果，一个整数，表示必须删除的最小 0 数量。

数据范围

前 3 个测试点满足 1≤T≤10， 所有测试点满足 1≤T≤100，1≤|s|≤100。

输入样例：

3
010011
0
1111000

输出样例：

2
0
0

解题思路:

这道题咋一看像是那种求最长连续或不连续子串的类型的题，还以为可能会用到双指针算法，现在看来其实题目已经给了可以直接暴力求解的办法，既然说了可以不删除 0，那么实际上只要求出字符串中从左往右开始遇到第一个 1 之后到最后一个 1 之间的 0 的个数就行了，省略掉前面和末尾的 0，只用一个变量来对 1 之间的所有的 0 计数，最后得到的就是答案。

代码:

#include <iostream>
#include <cstring>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        int n = 0,m = 0;
        for(int i=0;s[i];++i)
        {
            if(s[i]=='0'&&m)
            {
                n++;
            }
            if(s[i]=='1')
            {
                m = 1;
            }
        }
        for(int i=s.size()-1;s[i]=='0'&&n;--i)
        {
            n--;
        }
        cout<<n<<endl;
    }
    return 0;
}