2022-06-08：找到非负数组中拥有“最大或的结果“的最短子数组，返回最短长度。

use rand::Rng;
fn main() {
    let len: i32 = 50;
    let value: i32 = 5000;
    let test_time: i32 = 20000;
    println!("测试开始");
    for _ in 0..test_time {
        let n: i32 = rand::thread_rng().gen_range(0, len) + 1;
        let mut arr = random_array(n, value);
        let ans1 = longest1(&mut arr);
        let ans2 = longest2(&mut arr);
        if ans1 != ans2 {
            println!("出错了!");
            for num in &arr {
                print!("{} ", num);
            }
            println!("");
            println!("ans1 = {}", ans1);
            println!("ans2 = {}", ans2);
            break;
        }
    }
    println!("测试结束");
}

fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a < b {
        a
    } else {
        b
    }
}

fn longest1(arr: &mut Vec<i32>) -> i32 {
    if arr.len() == 0 {
        return 0;
    }
    let mut max = 0;
    for num in arr.iter_mut() {
        max |= *num;
    }
    if max == 0 {
        return 1;
    }
    let n = arr.len() as i32;
    let mut ans = n;
    for i in 0..n {
        let mut cur = 0;
        for j in i..n {
            cur |= arr[j as usize];
            if cur == max {
                ans = get_min(ans, j - i + 1);
                break;
            }
        }
    }
    return ans;
}

fn longest2(arr: &mut Vec<i32>) -> i32 {
    if arr.len() == 0 {
        return 0;
    }
    let mut max = 0;
    for num in arr.iter_mut() {
        max |= *num;
    }
    if max == 0 {
        return 1;
    }
    let n = arr.len() as i32;
    let mut ans = n;
    let mut counts: Vec<i32> = vec![];
    for _ in 0..32 {
        counts.push(0);
    }
    let mut l: i32 = 0;
    let mut cur = 0;
    for r in 0..n {
        cur = add(&mut counts, arr[r as usize]);
        while cur == max {
            cur = delete(&mut counts, arr[l as usize]);
            l += 1;
        }
        if l > 0 {
            l -= 1;
            cur = add(&mut counts, arr[l as usize]);
        }
        if cur == max {
            ans = get_min(ans, r - l + 1);
        }
    }
    return ans;
}

fn add(counts: &mut Vec<i32>, num: i32) -> i32 {
    let mut ans = 0;
    for i in 0..32 {
        counts[i as usize] += if (num & (1 << i)) != 0 { 1 } else { 0 };
        ans |= (if counts[i] > 0 { 1 } else { 0 }) << i;
    }
    return ans;
}

fn delete(counts: &mut Vec<i32>, num: i32) -> i32 {
    let mut ans = 0;
    for i in 0..32 {
        counts[i as usize] -= if (num & (1 << i)) != 0 { 1 } else { 0 };
        ans |= (if counts[i as usize] > 0 { 1 } else { 0 }) << i;
    }
    return ans;
}

// 为了测试
fn random_array(n: i32, v: i32) -> Vec<i32> {
    let mut arr: Vec<i32> = vec![];
    for _i in 0..n {
        arr.push(rand::thread_rng().gen_range(0, v) - rand::thread_rng().gen_range(0, v));
    }
    return arr;
}