leetcode
leetcode 1951 ~ 2000
选择建筑的方案数

选择建筑的方案数

难度:

标签:

题目描述

代码结果

运行时间: 229 ms, 内存: 16.7 MB


/* 
 * 思路:
 * 使用Java Stream进行流式处理,过滤出符合要求的建筑组合。
 * 我们可以使用IntStream.range来生成索引范围,并使用filter过滤出符合条件的组合。
 */

import java.util.stream.IntStream;

public class Solution {
    public long countValidCombinations(String s) {
        return IntStream.range(0, s.length() - 2)
                .filter(i -> s.charAt(i) != s.charAt(i + 1) && s.charAt(i + 1) != s.charAt(i + 2) && s.charAt(i) != s.charAt(i + 2))
                .count();
    }
}

解释

方法:

该题解采用一趟扫描的方式统计有效的三建筑选取方案。定义了几个计数器:n0 (遇到的'0'的数量), n1 (遇到的'1'的数量), n10 ('10'模式的数量), n01 ('01'模式的数量)。遍历字符串s中的每个字符,根据当前字符更新相关计数器。如果当前字符是'1',则更新n01为n0+n01(即当前1之前所有0的数量都可以和当前1形成'01'模式),n1自增,同时ans累加n10(即之前统计的所有'10'模式数量,每一个都可以与当前的'1'形成'101'模式)。反之,如果当前字符是'0',类似地更新n10和n0,并增加当前的答案ans值。最终,ans即为所有合法的三字符选择方案数。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在你的算法中,如何确保统计的组合中每两栋相邻建筑不是同一类型?
在算法中,通过特定的计数器逻辑,确保了统计的组合中相邻建筑不是同一类型。当遇到字符'1'时,算法会使用n10(之前累计的'10'模式的数量)来增加答案,表示这些'10'模式都可以与当前的'1'构成'101'。类似地,当遇到'0'时,使用n01(之前累计的'01'模式的数量)来增加答案,表示这些'01'模式都可以与当前的'0'构成'010'。这种方式确保了组合中的每两栋相邻建筑分别为'1'和'0',不会出现同一类型。
🦆
你提到了计数器n0, n1, n10, n01,能否详细解释这些计数器在算法中具体如何使用?
在算法中,计数器具体使用如下: - `n0`用于记录遇到的'0'的总数。 - `n1`用于记录遇到的'1'的总数。 - `n10`用于记录形成的'10'模式的数量,即每次遇到'0'时,将当前的`n1`(之前遇到的所有'1'的数量)加到`n10`上。 - `n01`用于记录形成的'01'模式的数量,即每次遇到'1'时,将当前的`n0`(之前遇到的所有'0'的数量)加到`n01`上。 这些计数器帮助追踪和构建必要的字符模式,并用于计算最终的答案。
🦆
在统计有效方案时,为什么选择在遇到'1'时累加n10,而在遇到'0'时累加n01?
选择在遇到'1'时累加n10,是因为每个'10'模式都可以与当前的'1'结合形成一个完整的'101'模式,这是一个有效的选择方案。同样,当遇到'0'时累加n01,是因为每个'01'模式都可以与当前的'0'结合形成一个完整的'010'模式。这种计数方法直接关联到目标模式的构成,确保每个计数的增加都对应一个完整且有效的建筑选择方案。

相关问题