2022-06-08：找到非负数组中拥有"最大或的结果"的最短子数组，返回最短长度。
答案2022-06-08：
双指针滑动窗口，统计32位数字每位1的个数。
代码用rust编写。代码如下：
代码语言：javascript复制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;
}
执行结果如下：
***
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_04_1_week/Code02_MaxOrSmallestSubarray.java)
