Leetcode每日一题 —— 3499. 操作后最大活跃区段数 I

题意有点绕，读了半天才懂。

题目中的操作只能执行一次，这一次操作分两步。因为两端有虚拟的 1，第二步必然能操作，因此能不能把 0…1…0 转换为 0…0…0 再转换为 1…1…1，主要就看能不能找到符合第一步要求的 0…1…0 形式。

然后要求结果找到最大的 1 数量，因此我们要找到 0…1…0 形式中全变成 1，转换最多的 0 的数目。

注意最终结果要的是转换后总的 1 数量。

class Solution {

public:

    int maxActiveSectionsAfterTrade(string s) {

        // 意思是两端都有虚拟的 1

        // 操作只能**执行一次**，一次操作分两步，先看被 0 包围的，转换后再看被 1 包围的

        // 因为两端有虚拟的 1，第二步必然是有的

        

        int oneCnt=0; // 对原本 s 中的 1 数量进行计数

        int prevZeros=0;

        int prevOnes=0;

        int currZeros=0;

        int currOnes=0;

        int transformed=0; // 被转换为 1 的最大 0 数量

        if(s[0]=='0'){

            currZeros++;

        }else{

            oneCnt++;

        }

        for(int i=1;i<s.size();i++){

            if(s[i]!=s[i-1]){

                // 出现交界

                if(s[i]=='0'){

                    // 前面一段是 1

                    prevOnes=currOnes;

                    currOnes=0;

                }else{

                    if(prevZeros>0){

                        // 前面一段是 0 且形成了 0 - 1 - 0 的情况

                        // 包围 1 的 0 都可转换为 1

                        // 结算

                        transformed=max(transformed,prevZeros+currZeros);

                    }

                    prevZeros=currZeros;

                    currZeros=0;

                    prevOnes=0;

                }

            }

            if(s[i]=='0'){

                currZeros++;

                if(i==s.size()-1&&prevZeros>0){

                    // 最后一个位置是 0，也要结算一下

                    transformed=max(transformed, prevZeros+currZeros);

                }

            }else{

                currOnes++;

                oneCnt++;

            }

        }

        return oneCnt+transformed;

    }

};

原题评论区说的好

算术评级4 第 153 场双周赛 Q2 难度分1729

class Solution:

    def maxActiveSectionsAfterTrade(self, s: str) -> int:

        s = '1' + s + '1'

        prev_zero, cur_zero, cur_one = None, 0, 0

        max_added = 0

        n = len(s)

        for i in range(n):

            if s[i]=='0':

                cur_zero+=1

                cur_one = 0

            elif i==0 or s[i-1]=='1':

                cur_one+=1

            else:

                if prev_zero is not None:

                    max_added = max(max_added, prev_zero+cur_zero)

                prev_zero = cur_zero

                cur_zero = 0

        return s.count('1')-2+max_added

class Solution {

public:

    int maxActiveSectionsAfterTrade(string s) {

        int mx = 0, ans = 0;

        int lst0 = 0;

        int i = 0, j = 0;

        int n = s.size();

        while (i < n) {

            int j = i;

            while (j < n and s[j] == s[i]) {

                j++;

            }

            if (s[i] == '1') {

                ans += j - i;

            } else {

                if (lst0 != 0) {

                    mx = max(mx, j - i + lst0);

                }

                lst0 = j - i;

            }

            i = j;

        }

        return ans + mx;

    }

};

逆天的题目 真读不懂

Codex 帮我理解的

class Solution:

    def maxActiveSectionsAfterTrade(self, s: str) -> int:

        tt = s.count('1')

        l = pre = cur = 0

        ans = 0

        n = len(s)

        while l < n:

            if s[l] == '1':

                l += 1

                continue

            r = l 

            while r < n and s[r] == '0':

                r += 1

            cur = r - l 

            if pre:

                ans = max(ans, pre + cur)

            pre = cur

            l = r

        return ans + tt