2022-06-27：给出一个长度为n的01串，现在请你找到两个区间， 使得这两个区间中，1的个数相等，0的个数也相等， 这两个区间可以相交，但是不可以完全重叠

2022-06-27：给出一个长度为n的01串，现在请你找到两个区间，

使得这两个区间中，1的个数相等，0的个数也相等，

这两个区间可以相交，但是不可以完全重叠，即两个区间的左右端点不可以完全一样。

现在请你找到两个最长的区间，满足以上要求。

来自百度。

答案2022-06-27：

这道题取巧了。用动态规划不是取巧的方式。

L0=最左0和最右0的长度，L1=最左1和最右1的长度,求L0和L1的最大值即可。

代码用rust编写。代码如下：

代码语言：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;
}

执行结果如下：

在这里插入图片描述

---

左神java代码

java rust 百度 动态规划

0 人点赞