DeepSeek LeetCode 3897. 连接二进制片段得到的最大值 Rust实现
这道题的核心是贪心排序,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 范围内)
如果还有疑问,欢迎继续追问!

更多推荐



所有评论(0)