算法(51)-hard 题目汇总

整理几道常见的 hard 题目。

拼接最大数

题目

给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。

现在从这两个数组中选出 k (0 <=k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。
求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。

题解

这题整体思路是用单调栈来解决。但是当一个数组单调栈长度不足时，还是要继续取完剩下的数，所以最后每个数组并不是严格单调的。这给最后拼接也带来了困难，不能直接 sort。

代码

function getMaxSubsequence(nums, k) {
    const len = nums.length;
    const stack = new Array(k).fill(0);
    let top = -1;
    let remain = len - k;
    for (let i = 0; i < len; i++) {
        const num = nums[i];
        while (top >= 0 && stack[top] < num && remain > 0) {
            top--;
            remain--;
        }
        if (top < k - 1) {
            stack[++top] = num;
        } else {
            remain--;
        }
    }
    return stack;
}

function compare(subsequence1, i1, subsequence2, i2) {
    const x = subsequence1.length;
    const y = subsequence2.length;
    let index1 = i1;
    let index2 = i2;
    while (index1 < x && index2 < y) {
        const difference = subsequence1[index1] - subsequence2[index2];
        if (difference !== 0) {
            return difference;
        }
        index1++;
        index2++;
    }
    return x - index1 - (y - index2);
}

function merge(subsequence1, subsequence2) {
    const x = subsequence1.length;
    const y = subsequence2.length;
    if (x === 0) {
        return subsequence2;
    }
    if (y === 0) {
        return subsequence1;
    }
    const mergeLength = x + y;
    const merged = new Array(mergeLength).fill(0);
    let index1 = 0;
    let index2 = 0;
    for (let i = 0; i < mergeLength; i++) {
        if (compare(subsequence1, index1, subsequence2, index2) > 0) {
            merged[i] = subsequence1[index1++];
        } else {
            merged[i] = subsequence2[index2++];
        }
    }
    return merged;
}

function maxNumber(nums1, nums2, k) {
    const m = nums1.length;
    const n = nums2.length;
    const maxSubsequence = new Array(k).fill(0);
    const start = Math.max(0, k - n);
    const end = Math.min(k, m);
    for (let i = start; i <= end; i++) {
        const subsequence1 = getMaxSubsequence(nums1, i);
        const subsequence2 = getMaxSubsequence(nums2, k - i);
        const curMaxSubsequence = merge(subsequence1, subsequence2);
        if (compare(curMaxSubsequence, 0, maxSubsequence, 0) > 0) {
            maxSubsequence.splice(0, k, ...curMaxSubsequence);
        }
    }
    return maxSubsequence;
}

按位与为零的三元组

题目

给你一个整数数组 nums ，返回其中 按位与三元组 的数目。

按位与三元组 是由下标 (i, j, k) 组成的三元组，并满足下述全部条件：

• 0 <= i < nums.length
• 0 <= j < nums.length
• 0 <= k < nums.l ength

nums[i] & nums[j] & nums[k] == 0 ，其中 & 表示按位与运算符。

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] < 2^16

注意：时间复杂度是 O(n^3)的算法，会超出时间限制。

题解

注意这里<216 是 2 的 16 次方，即 65536。
所以暴力思路可以生成一个 2 的 16 次方长度的数组，提前计算好两两&的结果。再根据结果出现的次数再做一次遍历即可。相比于纯纯 O(n^3)的时间复杂度降低到了 O(n^2+n*2^16)。

代码

function countTriplets(nums) {
  const cnt = new Array(1 << 16).fill(0);
  for (const x of nums) {
    for (const y of nums) {
      ++cnt[x & y];
    }
  }
  let ans = 0;
  for (const x of nums) {
    for (let mask = 0; mask < 1 << 16; ++mask) {
      if ((x & mask) === 0) {
        ans += cnt[mask];
      }
    }
  }
  return ans;
}