class Solution {
public:
long long numberOfWays(string s) {
}
};
2222. 选择建筑的方案数
给你一个下标从 0 开始的二进制字符串 s ，它表示一条街沿途的建筑类型，其中：
s[i] = '0' 表示第 i 栋建筑是一栋办公楼，s[i] = '1' 表示第 i 栋建筑是一间餐厅。作为市政厅的官员，你需要随机 选择 3 栋建筑。然而，为了确保多样性，选出来的 3 栋建筑 相邻 的两栋不能是同一类型。
s = "001101" ，我们不能选择第 1 ，3 和 5 栋建筑，因为得到的子序列是 "011" ，有相邻两栋建筑是同一类型，所以 不合 题意。请你返回可以选择 3 栋建筑的 有效方案数 。
示例 1：
输入：s = "001101" 输出：6 解释： 以下下标集合是合法的： - [0,2,4] ，从 "001101" 得到 "010" - [0,3,4] ，从 "001101" 得到 "010" - [1,2,4] ，从 "001101" 得到 "010" - [1,3,4] ，从 "001101" 得到 "010" - [2,4,5] ，从 "001101" 得到 "101" - [3,4,5] ，从 "001101" 得到 "101" 没有别的合法选择，所以总共有 6 种方法。
示例 2：
输入：s = "11100" 输出：0 解释：没有任何符合题意的选择。
提示：
3 <= s.length <= 105s[i] 要么是 '0' ，要么是 '1' 。原站题解
rust 解法, 执行用时: 8 ms, 内存消耗: 2.3 MB, 提交时间: 2023-09-14 00:00:40
impl Solution {
pub fn number_of_ways(s: String) -> i64 {
let n = s.len();
let o = s.chars().map(|c| if c == '1' { 1 } else { 0 }).sum::<usize>();
let ss = s.as_bytes();
let mut cnt = 0;
let mut ans = 0;
for i in 0..n {
if ss[i] == b'1' {
ans += (i - cnt) as i64 * (n - o - i + cnt) as i64;
cnt += 1;
} else {
ans += cnt as i64 * (o - cnt) as i64;
}
}
ans
}
pub fn number_of_ways2(s: String) -> i64 {
/*
dp[0][0] // number one building end with 0
dp[0][1] // number one building end with 1
dp[1][0] // number of two building end with 0
dp[1][1] // number of two building end with 1
*/
let mut dp = [[0,0],[0,0]];
let mut ans = 0;
for c in s.chars() {
if c == '0' {
dp[0][0] += 1;
dp[1][0] += dp[0][1];
ans += dp[1][1];
} else {
dp[0][1] += 1;
dp[1][1] += dp[0][0];
ans += dp[1][0];
}
}
ans
}
}
golang 解法, 执行用时: 32 ms, 内存消耗: 6.6 MB, 提交时间: 2023-09-13 23:59:11
func numberOfWays(s string) int64 {
tot0 := strings.Count(s, "0")
ans, c0 := 0, 0
for i, ch := range s {
if ch == '1' {
ans += c0 * (tot0 - c0) // 对每个 1，统计左边 0 的个数和右边 0 的个数
} else {
c1 := i - c0
ans += c1 * (len(s) - tot0 - c1) // 对每个 0，统计左边 1 的个数和右边 1 的个数
c0++
}
}
return int64(ans)
}
java 解法, 执行用时: 16 ms, 内存消耗: 42.7 MB, 提交时间: 2023-09-13 23:58:17
class Solution {
public long numberOfWays(String s) {
long ans=0, n0=0, n1=0, n10=0, n01=0;
for(char c : s.toCharArray()) {
if(c=='1'){
n01 += n0;
n1 ++;
ans += n10;
} else {
n10 += n1;
n0 ++;
ans += n01;
}
}
return ans;
}
}
cpp 解法, 执行用时: 92 ms, 内存消耗: 24.3 MB, 提交时间: 2023-09-13 23:57:44
class Solution {
public:
long long numberOfWays(string s) {
int n = s.size();
int n1 = count(s.begin(), s.end(), '1'); // s 中 '1' 的个数
long long res = 0; // 两种子序列的个数总和
int cnt = 0; // 遍历到目前为止 '1' 的个数
for (int i = 0; i < n; ++i) {
if (s[i] == '1') {
res += (long long) (i - cnt) * (n - n1 - i + cnt);
++cnt;
} else {
res += (long long) cnt * (n1 - cnt);
}
}
return res;
}
};
python3 解法, 执行用时: 532 ms, 内存消耗: 16.5 MB, 提交时间: 2023-09-13 23:57:34
class Solution:
def numberOfWays(self, s: str) -> int:
n = len(s)
n1 = s.count('1') # s 中 '1' 的个数
res = 0 # 两种子序列的个数总和
cnt = 0 # 遍历到目前为止 '1' 的个数
for i in range(n):
if s[i] == '1':
res += (i - cnt) * (n - n1 - i + cnt)
cnt += 1
else:
res += cnt * (n1 - cnt)
return res