选择建筑的方案数
难度:
标签:
题目描述
代码结果
运行时间: 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)
代码细节讲解
🦆
在你的算法中,如何确保统计的组合中每两栋相邻建筑不是同一类型?
▷🦆
你提到了计数器n0, n1, n10, n01,能否详细解释这些计数器在算法中具体如何使用?
▷🦆
在统计有效方案时,为什么选择在遇到'1'时累加n10,而在遇到'0'时累加n01?
▷