当前位置:网站首页>LeetCode每日一题(1573. Number of Ways to Split a String)
LeetCode每日一题(1573. Number of Ways to Split a String)
2022-08-10 21:11:00 【wangjun861205】
Given a binary string s, you can split s into 3 non-empty strings s1, s2, and s3 where s1 + s2 + s3 = s.
Return the number of ways s can be split such that the number of ones is the same in s1, s2, and s3. Since the answer may be too large, return it modulo 109 + 7.
Example 1:
Input: s = “10101”
Output: 4
Explanation: There are four ways to split s in 3 parts where each part contain the same number of letters ‘1’.
“1|010|1”
“1|01|01”
“10|10|1”
“10|1|01”
Example 2:
Input: s = “1001”
Output: 0
Example 3:
Input: s = “0000”
Output: 3
Explanation: There are three ways to split s in 3 parts.
“0|0|00”
“0|00|0”
“00|0|0”
Constraints:
- 3 <= s.length <= 105
- s[i] is either ‘0’ or ‘1’.
整体分成 3 种情况:
- 全是 0 的情况
- 1 的数量不能被 3 整除的情况
- 1 的数量可以被 3 整除的情况
情况 2 很简单,直接返回 0 即可。
情况 1 我们其实相当于将放 2 个隔板到任意 2 个槽里, 我们认为两个数之间是一个槽, 比如"0000"就有 3 个槽, 当我们将第一个挡板放到 slot[i]里面的时候, 我们第二个挡板可以放置在槽的总数量-i-1
个槽当中, 注意 i 从 0 开始, 所以我们只需要将这些选项数量相加即可, 时间复杂度 O(n)
情况 2 的话其实我们要找的是三组之间的 0 的数量, 比如"10100101000101", 我们可以把它拆解为 101|00|101|000|101, 每组含有 1 的组的两端一定都是 1, 也就是最小的符合题目要求的组, 这其中的 00 和 000, 与两边的 1 进行组合分别是 1001, 10001, 我们可以在其中任何一个槽上放置挡板, 所隔成的组一定是符合题目标准的, 1001 有 3 个槽, 10001 有 4 个槽, 这样我们实际的选择有 3 * 4 = 12 种
impl Solution {
pub fn num_ways(s: String) -> i32 {
let one_num = s.chars().filter(|v| v == &'1').count();
if one_num % 3 != 0 {
return 0;
}
let mut ans = 0i64;
if one_num == 0 {
let slot_num = s.len() - 1;
for i in 0..slot_num {
ans += slot_num as i64 - i as i64 - 1;
}
return (ans % (10i64.pow(9) + 7)) as i32;
}
let mut zero_span1 = 0;
let mut zero_span2 = 0;
let mut prev_one_index = -1;
let mut ones = 0;
for (i, c) in s.chars().enumerate() {
if c == '1' {
ones += 1;
if ones == one_num / 3 + 1 {
if prev_one_index == -1 {
zero_span1 = i as i64 + 1;
} else {
zero_span1 = i as i64 - prev_one_index;
}
} else if ones == one_num / 3 * 2 + 1 {
if prev_one_index == -1 {
zero_span2 = i as i64 + 1;
} else {
zero_span2 = i as i64 - prev_one_index;
}
break;
}
prev_one_index = i as i64;
}
}
(zero_span1 * zero_span2 % (10i64.pow(9) + 7)) as i32
}
}
边栏推荐
- 异常的了解
- Detailed explanation and use of each module of ansible
- DDL:视图——《mysql 从入门到内卷再到入土》
- Rider调试ASP.NET Core时报thread not gc-safe的解决方法
- 地理探测器Geodetector软件的下载、应用与结果解读
- npm warn config global `--global`, `--local` are deprecated. use `--location=global` instead.
- ansible各个模块的详解和使用
- C. Social Distance
- LeetCode-498-对角线遍历
- 【PCBA方案】电子握力测试仪方案she‘ji
猜你喜欢
随机推荐
将视图模型转换为使用 Hilt 依赖注入
The evolution history of Go programmers
Mark!画出漂亮的神经网络图!神经网络可视化工具集锦搜集
内置模板市场,DataEase开源数据可视化分析平台v1.13.0发布
深度学习之 12 循环神经网络RNN2
【nvm】【node多版本管理工具】使用说明和踩坑(exit status 1)
PostgreSQL — Installation and Common Commands
labelme - block drag and drop events
ENVI感兴趣区ROI文件由XML格式转为ROI格式
ArcMap时间滑块功能动态显示图层数据并生成视频或动图
数字化转型:如何引导创新领导者
【SQL刷题】Day3----SQL必会的常用函数专项练习
2021 GKCTF X DASCTF应急挑战杯
wget编译升级故障解决
DDL:CREATE 创建数据库——《mysql 从入门到内卷再到入土》
2021年中国工业互联网安全大赛(福建省选拔赛) 暨首届福建省工业互联网创新大赛
Bedtime story | made a Bitmap and AST length system configuration
测试代码新的规则
如何提高代码的可读性 学习笔记
Common functions of Auto.js to find pictures and colors