June 27, 2022: give a 01 string with a length of N. now please find two intervals so that the number of 1 is equal and the number of 0 is equal in the two intervals. The two intervals can intersect bu

2022-06-27： Give a length of n Of 01 strand , Now please find two intervals ,

So that in these two intervals ,1 The number of is equal ,0 The number of is also equal ,

These two intervals can intersect , But it can not overlap completely , That is, the left and right endpoints of the two intervals cannot be exactly the same .

Now please find the two longest intervals , Meet the above requirements .

From Baidu .

answer 2022-06-27：

This question is ingenious . Dynamic programming is not an ingenious way .

L0= Leftmost left 0 And rightmost 0 The length of ,L1= Leftmost left 1 And rightmost 1 The length of , seek L0 and L1 The maximum value of .

The code to use rust To write . The code is as follows ：

use rand::Rng;
use std::collections::HashMap;
fn main() {
    let n: i32 = 500;
    let test_time: i32 = 10000;
    println!(" Beginning of the test ");
    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!(" Something went wrong !{}", i);
            println!("ans1 = {}", ans1);
            println!("ans2 = {}", ans2);
            break;
        }
    }
    println!(" End of test ");
}

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);
}

//  In order to test 
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;
}

Copy

The results are as follows ：

Insert picture description here

---

Zuo Shen java Code