class Solution {
public:
int numWays(string s) {
}
};
1573. 分割字符串的方案数
给你一个二进制串 s （一个只包含 0 和 1 的字符串），我们可以将 s 分割成 3 个 非空 字符串 s1, s2, s3 （s1 + s2 + s3 = s）。
请你返回分割 s 的方案数，满足 s1，s2 和 s3 中字符 '1' 的数目相同。
由于答案可能很大，请将它对 10^9 + 7 取余后返回。
示例 1：
输入：s = "10101" 输出：4 解释：总共有 4 种方法将 s 分割成含有 '1' 数目相同的三个子字符串。 "1|010|1" "1|01|01" "10|10|1" "10|1|01"
示例 2：
输入：s = "1001" 输出：0
示例 3：
输入：s = "0000" 输出：3 解释：总共有 3 种分割 s 的方法。 "0|0|00" "0|00|0" "00|0|0"
示例 4：
输入：s = "100100010100110" 输出：12
提示：
s[i] == '0' 或者 s[i] == '1'3 <= s.length <= 10^5原站题解
golang 解法, 执行用时: 20 ms, 内存消耗: 6.4 MB, 提交时间: 2023-07-12 10:14:28
const mode int = 1e9 + 7
func numWays(s string) int {
ones := []int{}
slen := len(s)
for i := 0; i < slen; i++ {
if s[i] == '1' {
ones = append(ones, i)
}
}
olen := len(ones)
if olen % 3 != 0 {
return 0
}
if olen == 0 {
res := (slen-1)*(slen-2)/2
return res%mode
} else {
idx1 := olen/3
idx2 := olen/3*2
cnt1 := ones[idx1]-ones[idx1-1]
cnt2 := ones[idx2]-ones[idx2-1]
res := cnt1*cnt2
return res%mode
}
}
cpp 解法, 执行用时: 28 ms, 内存消耗: 14.7 MB, 提交时间: 2023-07-12 10:13:17
class Solution {
private:
static constexpr int MODULO = 1000000007;
public:
int numWays(string s) {
vector<int> ones;
int n = s.size();
for (int i = 0; i < n; ++i) {
if (s[i] == '1') {
ones.push_back(i);
}
}
int m = ones.size();
if (m % 3 != 0) {
return 0;
}
if (m == 0) {
long long ways = (long long)(n - 1) * (n - 2) / 2;
return ways % MODULO;
}
else {
int index1 = m / 3, index2 = m / 3 * 2;
int count1 = ones[index1] - ones[index1 - 1];
int count2 = ones[index2] - ones[index2 - 1];
long long ways = (long long)count1 * count2;
return ways % MODULO;
}
}
};
java 解法, 执行用时: 6 ms, 内存消耗: 43.2 MB, 提交时间: 2023-07-12 10:13:03
class Solution {
public int numWays(String s) {
final int MODULO = 1000000007;
List<Integer> ones = new ArrayList<Integer>();
int n = s.length();
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '1') {
ones.add(i);
}
}
int m = ones.size();
if (m % 3 != 0)
return 0;
if (m == 0) {
long ways = (long) (n - 1) * (n - 2) / 2;
return (int) (ways % MODULO);
} else {
int index1 = m / 3, index2 = m / 3 * 2;
int count1 = ones.get(index1) - ones.get(index1 - 1);
int count2 = ones.get(index2) - ones.get(index2 - 1);
long ways = (long) count1 * count2;
return (int) (ways % MODULO);
}
}
}
python3 解法, 执行用时: 88 ms, 内存消耗: 16.7 MB, 提交时间: 2023-07-12 10:12:45
# 模拟
class Solution:
def numWays(self, s: str) -> int:
MODULO = 1000000007
ones = [i for i, digit in enumerate(s) if digit == '1']
m, n = len(ones), len(s)
# 0的个数不为3的整数倍
if m % 3 != 0: return 0
# 没有0，则计算(n-1)个位置放2个不同卡槽的方法数，等于组合问题
if m == 0:
ways = (n - 1) * (n - 2) // 2
return ways % MODULO
else:
index1, index2 = m // 3, m // 3 * 2 # 两个卡槽的位置
count1 = ones[index1] - ones[index1 - 1]
count2 = ones[index2] - ones[index2 - 1]
ways = count1 * count2
return ways % MODULO
python3 解法, 执行用时: 112 ms, 内存消耗: 16.7 MB, 提交时间: 2023-07-12 10:08:06
# 统计'1'的下标，分组讨论，
class Solution:
def numWays(self, s: str) -> int:
news = [i for i,num in enumerate(s) if num == '1']
k = len(news)
if k % 3: return 0
if not k: return (len(s) - 1 ) * ( len(s) - 2) // 2 % 1000000007
return (news[k//3] - news[k//3-1]) * (news[k//3*2] - news[k//3*2-1]) % 1000000007