【leetcode】2680. 最大或值

题目描述

leetcode.cn/problems/maximum-or/description

思路 (二进制暴力)

史山代码预警 ⚠️, 用时 $3ms$, 击败了 $0\%$ 的用户...

首先明确, 如何操作可以使得最终的结果最大?
因为每次的操作都是乘以二, 那么就是说每次都对最大的数进行操作, 那么最后的结果必然是最大的, 但是还有一个问题, 题目要求的是按位或之后的最大值. 如果是这样的话, 可能会有那些问题呢, 可能中间的值已经存在了, 但是扩大之后的数又或一遍, 也就是没有产生任何贡献. 对于这点, 继续想想, 样例一给出的值$12$和$9$, 把他们写成二进制的形式, 分别是$(1100)_2$和$(1000)_2$, 左移一位然后相或, 得到的结果是$(11000)_2$和$(11100)_2$. 不对劲, 最大的值可能并不会产生最优解, 也就是上面说的情况. 那么再思考一种情况, 如果是$(100)_2$和$(11)_2$的话, 很显然, 一定是$(100)_2$左移会更大, 毕竟高出了一位.
综上所述, 可以得出一个结论:

只扩大同一个数, 且扩大的这个数拥有数组中最高位的$1$.

有了这个结论, 我们就可以直接暴力了. 暴力计算拥有最高位$1$的数可能的情况, 取他们的最大值.

代码

impl Solution {
    pub fn maximum_or(nums: Vec<i32>, k: i32) -> i64 {
        let mut ans: i64 = 0;
        let mut nums: Vec<i32> = nums; // 需要所有权, 复制一份
        let mut bits: Vec<i32> = vec![0; 64]; // 记录每一位上有几个1, 只需维护这个数组即可

        // 添加一个数到 bits
        let add_bit = |x: i64, bits: &mut Vec<i32>| {
            let mut tmp = x;
            let mut index = 0;
            loop {
                if tmp & 1 == 1 {
                    bits[index] += 1;
                }

                tmp >>= 1;
                index += 1;

                if tmp == 0 {
                    break;
                }
            }
        };

        // 从 bits 里删除一个数
        let del_bit = |x: i64, bits: &mut Vec<i32>| {
            let mut tmp = x;
            let mut index = 0;
            loop {
                if tmp & 1 == 1 {
                    bits[index] -= 1;
                }

                tmp >>= 1;
                index += 1;

                if tmp == 0 {
                    break;
                }
            }
        };

        // 最高位
        let high_bit = |x: i32| -> i32 {
            let mut base = 1;
            loop {
                if (base << 1) > x {
                    return base;
                }
                base <<= 1
            }
        };

        nums.sort();

        // 预处理, 先把所有数加到 bits 里
        for i in nums.iter() {
            add_bit(*i as i64, &mut bits);
        }

        let maxn = high_bit(*nums.last().unwrap());
        for i in nums.iter().rev() {
            // 如果最高位已经不是1了, 直接退出
            if high_bit(*i) != maxn {
                break;
            }

            // 修改 bits 为扩大后的情况
            del_bit(*i as i64, &mut bits); // 数据范围 1e9, 左移 15 次可能会变负数, 需要 i64
            add_bit((*i as i64) << (k as i64), &mut bits);

            // 看是不是最大值
            ans = std::cmp::max(ans, {
                let mut res = 0;
                let mut base = 1;
                for i in bits.iter() {
                    res += if *i >= 1 { base } else { 0 };
                    base <<= 1;
                }
                res
            });

            // 还原, 准备下次处理
            add_bit(*i as i64, &mut bits);
            del_bit((*i as i64) << (k as i64), &mut bits);
        }

        ans
    }
}