当前位置:网站首页>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
}
}
边栏推荐
- 自建函数 测试例和语法——《mysql 从入门到内卷再到入土》
- 石油化工行业商业供应链管理系统:标准化供应商管理,优化企业供应链采购流程
- Mark!画出漂亮的神经网络图!神经网络可视化工具集锦搜集
- Likou 221 questions, the largest square
- 我的世界整合包 云服务器搭建方法(ECS)
- ansible各个模块的详解和使用
- D. Game With Array
- C#【必备技能篇】Hex文件转bin文件的代码实现
- 流程控制结构——《mysql 从入门到内卷再到入土》
- npm warn config global `--global`, `--local` are deprecated. use `--location=global` instead.
猜你喜欢
LeetCode-36-二叉搜索树与双向链表
paddle 35 paddledetection保存训练过程中的log信息
Redis Performance Impact - Asynchronous Mechanisms and Response Latency
JS中的filter、map、reduce
Uniapp编译后小程序的代码反编译一些思路
C#【必备技能篇】Hex文件转bin文件的代码实现
Future与CompletableFuture
ES6中的for...in/of的使用
优化是一种习惯●出发点是'站在靠近临界'的地方
【nvm】【node多版本管理工具】使用说明和踩坑(exit status 1)
随机推荐
2021 CybricsCTF
Before implementing MES management system, these three questions to consider
Mark!画出漂亮的神经网络图!神经网络可视化工具集锦搜集
Play RT-THREAD of doxygen
ArcPy读取Excel时序数据、批量反距离加权IDW插值与掩膜
TCL:事务的特点,语法,测试例——《mysql 从入门到内卷再到入土》
ES6中的for...in/of的使用
Future与CompletableFuture
力扣215题,数组中的第K个最大元素
Intelligent scheme design - intelligent rope skipping scheme
Getting started with kuberentes Auditing
Floating window in Auto.js
Detailed explanation of the use of Oracle's windowing function (2)
Redis Command Manual
《mysql 从入门到内卷再到入土》——Mysql基础 学习笔记目录
基于Pix4Dmapper的空间三维模型重建应用——空间分析选址
日期选择器组件(限制年份 设定仅展示的月份)
Introduction to PostgreSQL
ArcMap时间滑块功能动态显示图层数据并生成视频或动图
数据标注太昂贵?这个方法可以用有限的数据训练模型实现基于文本的ReID!