当前位置:网站首页>2022-06-27:给出一个长度为n的01串,现在请你找到两个区间, 使得这两个区间中,1的个数相等,0的个数也相等, 这两个区间可以相交,但是不可以完全重叠
2022-06-27:给出一个长度为n的01串,现在请你找到两个区间, 使得这两个区间中,1的个数相等,0的个数也相等, 这两个区间可以相交,但是不可以完全重叠
2022-06-28 09:22:00 【福大大架构师每日一题】
2022-06-27:给出一个长度为n的01串,现在请你找到两个区间,
使得这两个区间中,1的个数相等,0的个数也相等,
这两个区间可以相交,但是不可以完全重叠,即两个区间的左右端点不可以完全一样。
现在请你找到两个最长的区间,满足以上要求。
来自百度。
答案2022-06-27:
这道题取巧了。用动态规划不是取巧的方式。
L0=最左0和最右0的长度,L1=最左1和最右1的长度,求L0和L1的最大值即可。
代码用rust编写。代码如下:
use rand::Rng;
use std::collections::HashMap;
fn main() {
let n: i32 = 500;
let test_time: i32 = 10000;
println!("测试开始");
for i in 0..test_time {
let size = rand::thread_rng().gen_range(0, n) + 2;
let mut arr = random_array(size);
let ans1 = longest1(&mut arr);
let ans2 = longest2(&mut arr);
if ans1 != ans2 {
println!("出错了!{}", i);
println!("ans1 = {}", ans1);
println!("ans2 = {}", ans2);
break;
}
}
println!("测试结束");
}
fn longest1(arr: &mut Vec<i32>) -> i32 {
let mut map: HashMap<i32, HashMap<i32, i32>> = HashMap::new();
for i in 0..arr.len() as i32 {
let mut zero = 0;
let mut one = 0;
for j in i..arr.len() as i32 {
zero += if arr[j as usize] == 0 { 1 } else { 0 };
one += if arr[j as usize] == 1 { 1 } else { 0 };
map.entry(zero).or_insert(HashMap::new());
let mapzero = map.get_mut(&zero).unwrap();
mapzero.insert(one, if mapzero.get(&one) == None { 0 } else { 1 } + 1);
}
}
let mut ans = 0;
for (k, v) in map.iter() {
for (k2, v2) in v.iter() {
let num = *v2;
if num > 1 {
ans = get_max(ans, k + k2);
}
}
}
return ans;
}
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a > b {
a
} else {
b
}
}
fn longest2(arr: &mut Vec<i32>) -> i32 {
let mut left_zero = -1;
let mut right_zero: i32 = -1;
let mut left_one = -1;
let mut right_one: i32 = -1;
for i in 0..arr.len() as i32 {
if arr[i as usize] == 0 {
left_zero = i;
break;
}
}
for i in 0..arr.len() as i32 {
if arr[i as usize] == 1 {
left_one = i;
break;
}
}
let mut i = arr.len() as i32 - 1;
while i >= 0 {
if arr[i as usize] == 0 {
right_zero = i;
break;
}
i -= 1;
}
let mut i = arr.len() as i32 - 1;
while i >= 0 {
if arr[i as usize] == 1 {
right_one = i;
break;
}
i -= 1;
}
let p1 = right_zero - left_zero;
let p2 = right_one - left_one;
return get_max(p1, p2);
}
// 为了测试
fn random_array(len: i32) -> Vec<i32> {
let mut arr: Vec<i32> = vec![];
for _i in 0..len {
arr.push(rand::thread_rng().gen_range(0, 2));
}
return arr;
}
执行结果如下:
边栏推荐
- 为什么SELECT * 会导致查询效率低?
- Fastjason filter field
- Apiccloud, together with 360 Tianyu, helps enterprises keep the "first pass" of APP security
- Implement global double finger long press to return to the desktop
- 硬盘基本知识(磁头、磁道、扇区、柱面)
- [ybtoj advanced training guide] maximum separation [hash] [Floyd]
- How do I open an account on my mobile phone? Is it safe to open an account online now?
- P2394 yyy loves Chemistry I
- HDI的盲孔设计,你注意到这个细节了吗?
- Apache Doris 成为 Apache 顶级项目
猜你喜欢
Apache Doris 成为 Apache 顶级项目
A classic JVM class loaded interview question class singleton{static singleton instance = new singleton(); private singleton() {}
rman備份報ORA-19809 ORA-19804
Redis5.0 slot migration, free play (single machine migration cluster)
线程的生命周期
File operations in QT
For the development of short video app, the elder warned me to choose the open source code
1182:合影效果
1182: group photo effect
Ingersoll Rand panel maintenance IR Ingersoll Rand microcomputer controller maintenance xe-145m
随机推荐
满电出发加速品牌焕新,长安电动电气化产品吹响“集结号”
A classic JVM class loaded interview question class singleton{static singleton instance = new singleton(); private singleton() {}
==和eqauls()的区别
如何实现基于 RADIUS 协议的双因子认证 MFA?
在本类私有属性直接使用?new()在使用!!!
硬盘基本知识(磁头、磁道、扇区、柱面)
How do I open an account on my mobile phone? Is it safe to open an account online now?
两道面试小Demo
P2394 yyy loves Chemistry I
1182:合影效果
自动转换之-面试题
Postman interface test
Import and export of a single collection in postman
[share OpenGL tutorial]
買賣股票費用計算
Interpretation of new products: realm launched GT neo2 Dragon Ball customized version
Boundary value analysis method for learning basic content of software testing (2)
Screen settings in the source code of OBS Live Room
APICloud携手三六零天御,助力企业守好App安全“第一关”
图解MySQL的binlog、redo log和undo log