当前位置:网站首页>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
}
}
边栏推荐
猜你喜欢
Single-click to cancel the function
【PCBA scheme design】Bluetooth skipping scheme
着力提升制造业核心竞争力,仪器仪表产业迎高质量发展
Using SylixOS virtual serial port, serial port free implementation system
paddle 35 paddledetection保存训练过程中的log信息
npm warn config global `--global`, `--local` are deprecated. use `--location=global` instead.
【PCBA方案】电子握力测试仪方案she‘ji
ES6中的for...in/of的使用
npm warn config global `--global`, `--local` are deprecated. use `--location=global` instead.
数据标注太昂贵?这个方法可以用有限的数据训练模型实现基于文本的ReID!
随机推荐
paddle 35 paddledetection保存训练过程中的log信息
管理员必须知道的RADIUS认证服务器的部署成本
玩转doxygen 之RT-THREAD
Bedtime story | made a Bitmap and AST length system configuration
将视图模型转换为使用 Hilt 依赖注入
日期选择器组件(限制年份 设定仅展示的月份)
Detailed explanation and use of each module of ansible
HGAME 2022 Week2 writeup by pankas
Application of Spatial 3D Model Reconstruction Based on Pix4Dmapper - Spatial Analysis and Site Selection
LeetCode-36-二叉搜索树与双向链表
ansible各个模块的详解和使用
The use of TortoiseSVN little turtle
Likou 215 questions, the Kth largest element in an array
2022.8.9 模拟赛
国内Gravatar头像的完美替代方案Cravatar
wget编译升级故障解决
自建函数 测试例和语法——《mysql 从入门到内卷再到入土》
APP application related instructions in Auto.js
D. Game With Array
shell小技巧(一百三十五)打包指定目录下所用文件,每个文件单独打包