DeepSeek LeetCode 3897. 连接二进制片段得到的最大值 TypeScript实现
这道题的核心是贪心排序,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. 取模运算:确保每一步都在模运算下进行,避免大数溢出
如果还有疑问,欢迎继续追问!

更多推荐



所有评论(0)