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

核心解题思路

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

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

TypeScript 代码实现

```typescript
function maxValue(nums1: number[], nums0: number[]): number {
    const MOD = 1_000_000_007;
    const n = nums1.length;
    
    // 1. 创建片段数组 [ones, zeros]
    const fragments: [number, number][] = [];
    for (let i = 0; i < n; i++) {
        fragments.push([nums1[i], nums0[i]]);
    }
    
    // 2. 自定义排序
    fragments.sort((a, b) => {
        const [onesA, zerosA] = a;
        const [onesB, zerosB] = b;
        
        // 纯 1 片段优先
        if (zerosA === 0 && zerosB === 0) {
            return onesB - onesA; // 1 多的在前
        }
        if (zerosA === 0) return -1;
        if (zerosB === 0) return 1;
        
        // 都含 0:1 多的在前
        if (onesA !== onesB) {
            return onesB - onesA;
        }
        // 1 相同:0 少的在前
        return zerosA - zerosB;
    });
    
    // 3. 拼接并计算结果
    let ans = 0;
    for (const [ones, zeros] of fragments) {
        // 追加 ones 个 '1'
        if (ones > 0) {
            const pow2Ones = modPow(2, ones, MOD);
            ans = (ans * pow2Ones + (pow2Ones - 1)) % MOD;
        }
        // 追加 zeros 个 '0'
        if (zeros > 0) {
            ans = (ans * modPow(2, zeros, MOD)) % MOD;
        }
    }
    
    return ans;
}

// 快速幂取模
function modPow(base: number, exp: number, mod: number): number {
    let result = 1;
    let b = base % mod;
    let e = exp;
    
    while (e > 0) {
        if (e & 1) {
            result = (result * b) % mod;
        }
        b = (b * b) % mod;
        e >>= 1;
    }
    
    return result;
}
```

更简洁的实现(使用排序键)

```typescript
function maxValue(nums1: number[], nums0: number[]): number {
    const MOD = 1_000_000_007;
    const n = nums1.length;
    
    // 创建片段并排序
    const fragments: [number, number][] = Array.from(
        { length: n }, 
        (_, i) => [nums1[i], nums0[i]]
    );
    
    // 排序键:(是否纯1, -1的数量, 0的数量)
    fragments.sort((a, b) => {
        const pureA = a[1] === 0 ? 0 : 1;
        const pureB = b[1] === 0 ? 0 : 1;
        
        if (pureA !== pureB) return pureA - pureB;
        if (a[0] !== b[0]) return b[0] - a[0]; // 1 多的在前
        return a[1] - b[1]; // 0 少的在前
    });
    
    // 批量拼接
    let ans = 0;
    for (const [ones, zeros] of fragments) {
        // 追加 ones 个 1
        if (ones > 0) {
            const pow2 = modPow(2, ones, MOD);
            ans = (ans * pow2 + (pow2 - 1)) % MOD;
        }
        // 追加 zeros 个 0
        if (zeros > 0) {
            ans = (ans * modPow(2, zeros, MOD)) % MOD;
        }
    }
    
    return ans;
}
```

优化版本(使用 BigInt 避免溢出)

当 nums1 或 nums0 很大时,使用 BigInt 更安全:

```typescript
function maxValue(nums1: number[], nums0: number[]): number {
    const MOD = BigInt(1_000_000_007);
    const n = nums1.length;
    
    const fragments: [number, number][] = [];
    for (let i = 0; i < n; i++) {
        fragments.push([nums1[i], nums0[i]]);
    }
    
    fragments.sort((a, b) => {
        const [onesA, zerosA] = a;
        const [onesB, zerosB] = b;
        
        if (zerosA === 0 && zerosB === 0) return onesB - onesA;
        if (zerosA === 0) return -1;
        if (zerosB === 0) return 1;
        if (onesA !== onesB) return onesB - onesA;
        return zerosA - zerosB;
    });
    
    let ans = 0n;
    for (const [ones, zeros] of fragments) {
        if (ones > 0) {
            const pow2 = modPowBigInt(2n, BigInt(ones), MOD);
            ans = (ans * pow2 + (pow2 - 1n)) % MOD;
        }
        if (zeros > 0) {
            ans = (ans * modPowBigInt(2n, BigInt(zeros), MOD)) % MOD;
        }
    }
    
    return Number(ans);
}

// BigInt 快速幂
function modPowBigInt(base: bigint, exp: bigint, mod: bigint): bigint {
    let result = 1n;
    let b = base % mod;
    let e = exp;
    
    while (e > 0n) {
        if (e & 1n) {
            result = (result * b) % mod;
        }
        b = (b * b) % mod;
        e >>= 1n;
    }
    
    return result;
}
```

测试用例

```typescript
// 测试
console.log(maxValue([1, 1], [1, 1]));  // 输出: 10
// "10" + "10" = "1010" = 10

console.log(maxValue([2, 1], [0, 1]));  // 输出: 14
// "11" + "10" = "1110" = 14

console.log(maxValue([1, 2, 1], [2, 0, 1]));  // 输出: 116
// "11" + "10" + "100" = "1110100" = 116

console.log(maxValue([3, 2], [0, 0]));  // 输出: 31
// "111" + "11" = "11111" = 31

console.log(maxValue([10, 5], [3, 2]));  // 大片段测试
// 输出: 根据实际情况计算
```

数学原理解释

批量追加的数学公式:

追加 ones 个 1

当前二进制数为 ans,追加 ones 个 1:

```
新值 = ans * 2^ones + (2^ones - 1)
```

例如:ans = 0b101 (5),追加 3 个 1:

```
5 * 2^3 + (2^3 - 1) = 5 * 8 + 7 = 47 = 0b101111
```

追加 zeros 个 0

当前二进制数为 ans,追加 zeros 个 0:

```
新值 = ans * 2^zeros
```

例如:ans = 0b1011 (11),追加 2 个 0:

```
11 * 2^2 = 44 = 0b101100
```

复杂度分析

· 时间复杂度:O(n log n + sum(nums1) + sum(nums0)),但实际上我们用快速幂批量处理,所以是 O(n log n + n log M),其中 M 是最大的片段长度
· 空间复杂度:O(n),存储片段数组

关键注意事项

1. 排序稳定性:TypeScript 的 sort 是稳定的,但建议明确所有比较规则
2. 大数处理:当 nums1 或 nums0 超过 10^9 时,需要使用 BigInt
3. 性能优化:使用快速幂而不是逐位循环,特别当片段长度很大时
4. 取模运算:确保每一步都在模运算下进行,避免大数溢出

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

 

Logo

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

更多推荐