这道题的核心是贪心排序,Rust实现需要处理自定义排序和模运算。

核心解题思路

每个片段形如 "111...000..."(nums1[i] 个 1 后跟 nums0[i] 个 0)。排序规则:

1. 纯 1 片段优先:nums0[i] == 0 的片段全由 1 组成
2. 1 多的靠前:1 的数量越多,高位 1 越多
3. 1 相同时,0 少的靠前

Rust 代码实现

```rust
impl Solution {
    pub fn max_value(nums1: Vec<i32>, nums0: Vec<i32>) -> i32 {
        const MOD: i64 = 1_000_000_007;
        let n = nums1.len();
        
        // 1. 创建片段向量 (ones, zeros)
        let mut fragments: Vec<(i32, i32)> = nums1
            .into_iter()
            .zip(nums0.into_iter())
            .collect();
        
        // 2. 自定义排序
        fragments.sort_by(|a, b| {
            let (ones_a, zeros_a) = a;
            let (ones_b, zeros_b) = b;
            
            // 纯 1 片段优先
            if *zeros_a == 0 && *zeros_b == 0 {
                return ones_b.cmp(ones_a); // 1 多的在前
            }
            if *zeros_a == 0 {
                return std::cmp::Ordering::Less;
            }
            if *zeros_b == 0 {
                return std::cmp::Ordering::Greater;
            }
            
            // 都含 0:1 多的在前
            if ones_a != ones_b {
                return ones_b.cmp(ones_a);
            }
            // 1 相同:0 少的在前
            return zeros_a.cmp(zeros_b);
        });
        
        // 3. 拼接并计算结果
        let mut ans: i64 = 0;
        for (ones, zeros) in fragments {
            // 追加 ones 个 '1'
            if ones > 0 {
                let pow2_ones = Self::pow_mod(2, ones as u64, MOD);
                ans = (ans * pow2_ones + (pow2_ones - 1)) % MOD;
            }
            // 追加 zeros 个 '0'
            if zeros > 0 {
                ans = (ans * Self::pow_mod(2, zeros as u64, MOD)) % MOD;
            }
        }
        
        ans as i32
    }
    
    // 快速幂取模
    fn pow_mod(base: i64, exp: u64, mod_val: i64) -> i64 {
        let mut result = 1;
        let mut base = base % mod_val;
        let mut exp = exp;
        
        while exp > 0 {
            if exp & 1 == 1 {
                result = (result * base) % mod_val;
            }
            base = (base * base) % mod_val;
            exp >>= 1;
        }
        result
    }
}
```

更简洁的排序(使用 Ordering 链式调用)

```rust
use std::cmp::Ordering;

impl Solution {
    pub fn max_value(nums1: Vec<i32>, nums0: Vec<i32>) -> i32 {
        const MOD: i64 = 1_000_000_007;
        
        let mut fragments: Vec<(i32, i32)> = nums1
            .into_iter()
            .zip(nums0.into_iter())
            .collect();
        
        // 使用链式比较
        fragments.sort_by(|a, b| {
            let (ones_a, zeros_a) = a;
            let (ones_b, zeros_b) = b;
            
            // 判断是否纯 1(zeros == 0)
            let pure_a = *zeros_a == 0;
            let pure_b = *zeros_b == 0;
            
            // 纯 1 优先
            if pure_a && !pure_b {
                return Ordering::Less;
            }
            if !pure_a && pure_b {
                return Ordering::Greater;
            }
            
            // 都纯 1 或都含 0
            match ones_b.cmp(ones_a) { // 1 多的在前
                Ordering::Equal => zeros_a.cmp(zeros_b), // 1 相同,0 少的在前
                other => other,
            }
        });
        
        let mut ans: i64 = 0;
        for (ones, zeros) in fragments {
            // 批量处理连续的 1
            if ones > 0 {
                let pow2_ones = Self::mod_pow(2, ones as u64, MOD);
                ans = (ans * pow2_ones + (pow2_ones - 1)) % MOD;
            }
            // 批量处理连续的 0
            if zeros > 0 {
                ans = (ans * Self::mod_pow(2, zeros as u64, MOD)) % MOD;
            }
        }
        
        ans as i32
    }
    
    fn mod_pow(mut base: i64, mut exp: u64, mod_val: i64) -> i64 {
        let mut result = 1;
        base %= mod_val;
        while exp > 0 {
            if exp & 1 == 1 {
                result = (result * base) % mod_val;
            }
            base = (base * base) % mod_val;
            exp >>= 1;
        }
        result
    }
}
```

优化版本(使用迭代器)

```rust
impl Solution {
    pub fn max_value(nums1: Vec<i32>, nums0: Vec<i32>) -> i32 {
        const MOD: i64 = 1_000_000_007;
        
        let mut fragments: Vec<_> = nums1
            .into_iter()
            .zip(nums0.into_iter())
            .collect();
        
        // 排序键:(是否纯1, -1的数量, 0的数量)
        fragments.sort_by_key(|(ones, zeros)| {
            let pure = if *zeros == 0 { 0 } else { 1 };
            (pure, -ones, *zeros)
        });
        
        let mut ans: i64 = 0;
        for (ones, zeros) in fragments {
            // 使用快速幂批量追加
            if ones > 0 {
                let pow2 = Self::mod_pow(2, ones as u64, MOD);
                ans = (ans * pow2 + pow2 - 1) % MOD;
            }
            if zeros > 0 {
                ans = (ans * Self::mod_pow(2, zeros as u64, MOD)) % MOD;
            }
        }
        
        ans as i32
    }
    
    fn mod_pow(mut base: i64, mut exp: u64, mod_val: i64) -> i64 {
        let mut result = 1;
        base %= mod_val;
        while exp > 0 {
            if exp & 1 == 1 {
                result = (result * base) % mod_val;
            }
            base = (base * base) % mod_val;
            exp >>= 1;
        }
        result
    }
}
```

测试用例

```rust
#[cfg(test)]
mod tests {
    use super::*;
    
    #[test]
    fn test_example1() {
        let nums1 = vec![1, 1];
        let nums0 = vec![1, 1];
        assert_eq!(Solution::max_value(nums1, nums0), 10);
        // "10" + "10" = "1010" = 10
    }
    
    #[test]
    fn test_example2() {
        let nums1 = vec![2, 1];
        let nums0 = vec![0, 1];
        assert_eq!(Solution::max_value(nums1, nums0), 14);
        // "11" + "10" = "1110" = 14
    }
    
    #[test]
    fn test_example3() {
        let nums1 = vec![1, 2, 1];
        let nums0 = vec![2, 0, 1];
        assert_eq!(Solution::max_value(nums1, nums0), 116);
        // "11" + "10" + "100" = "1110100" = 116
    }
    
    #[test]
    fn test_pure_ones() {
        let nums1 = vec![3, 2];
        let nums0 = vec![0, 0];
        assert_eq!(Solution::max_value(nums1, nums0), 31);
        // "111" + "11" = "11111" = 31
    }
}
```

关键点说明

1. 排序规则:Rust 的 sort_by 需要返回 Ordering 枚举
2. 批量处理:使用快速幂 mod_pow 处理连续的 1 或 0
3. 数学公式:
   · 追加 ones 个 1:ans = ans * 2^ones + (2^ones - 1)
   · 追加 zeros 个 0:ans = ans * 2^zeros
4. 类型转换:注意 i32 和 i64 之间的转换,避免溢出

复杂度分析

· 时间复杂度:O(n log n + L),L 是总长度
· 空间复杂度:O(n),存储片段向量

注意事项

· Rust 的 sort_by_key 要求 key 实现 Ord trait
· 使用 usize 作为幂运算的指数类型
· 模运算时注意 i64 的范围(10^9+7 平方约 10^18,在 i64 范围内)

如果还有疑问,欢迎继续追问!

 

Logo

欢迎加入DeepSeek 技术社区。在这里,你可以找到志同道合的朋友,共同探索AI技术的奥秘。

更多推荐