leetcode
leetcode 1251 ~ 1300
二进制字符串前缀一致的次数

二进制字符串前缀一致的次数

难度:

标签:

题目描述

代码结果

运行时间: 48 ms, 内存: 21.9 MB


/*
思路:
使用 Java Stream 的话,我们可以利用 IntStream 和累加器来计算前缀一致的次数。
与传统方法类似,我们需要维护当前的最大翻转位置。
*/
import java.util.stream.IntStream;

public class Solution {
    public int numTimesAllBlue(int[] flips) {
        int[] maxFlip = {0};
        return (int) IntStream.range(0, flips.length)
                .filter(i -> {
                    maxFlip[0] = Math.max(maxFlip[0], flips[i]);
                    return maxFlip[0] == i + 1;
                })
                .count();
    }
}

解释

方法:

本题解的思路是通过维护一个最大翻转位置的变量来判断是否满足前缀一致的条件。遍历flips数组,每次更新最大翻转位置,如果当前最大翻转位置小于等于当前步数(i+1),则说明在当前步骤下,前缀一致的条件得到满足,因此结果计数加1。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在判断前缀一致时,我们依赖于最大翻转位置max是否小于等于当前步数i+1?这样的条件是如何确保前缀一致的?
在本题中,前缀一致的条件意味着在步骤i(从0开始计数)结束时,前i+1个位置都已被翻转至少一次。这就要求在前i+1步中,最大翻转位置至少达到i+1。如果最大翻转位置max小于等于i+1,意味着在步骤i之前的翻转已经覆盖了前i+1个位置,因此这些位置的状态是一致的。这样的检查保证了我们可以正确地数出满足前缀一致条件的步数。
🦆
在更新最大翻转位置max时,为什么只检查当前翻转位置flips[i]是否大于max而没有其他条件?是否有可能因为翻转顺序的不同而影响判断结果?
在算法中,我们关注的是确保所有位置至少被翻转一次,因此最关键的信息是已经遇到的最大翻转位置。只检查当前翻转位置是否大于已知的最大翻转位置是足够的,因为我们想知道翻转操作是否扩展了已翻转的范围。翻转顺序不会影响判断结果,因为无论翻转的顺序如何,只要每个位置最终都被翻转,就能满足前缀一致的条件。
🦆
如果数组flips中存在重复的数字,这种情况下算法的行为会如何改变?会对最终的前缀一致次数计算产生什么影响?
如果数组flips中存在重复数字,即某个位置被翻转多次,这并不会影响算法的基本行为或最终的前缀一致次数计算。这是因为算法只关心最大翻转位置是否达到或超过当前步骤数。重复翻转同一个位置不会使最大翻转位置有新的增长,因此不会影响结果计数的逻辑。
🦆
算法中使用的变量max初始化为-1而不是0的原因是什么?
变量max初始化为-1是为了正确处理第一次翻转操作前的情况。由于数组索引从0开始,如果max初始化为0,那么在处理第一个元素之前,算法会错误地认为位置0已经被覆盖,这可能导致错误的计数。初始化为-1确保在第一个翻转发生前,没有任何位置被认为已翻转,从而保证计数的正确性。

相关问题