Skip to main content

第 53 场双周赛

Problem A - 长度为三且各字符不同的子字符串​

方法一：暴力​

本题数据范围较小，因此暴力枚举即可。如果数据规模更大，同时子字符串长度从33变为kk，则可以使用滑动窗口来进行优化。

  • 时间复杂度O(∣S∣)\mathcal{O}(|S|)。
  • 空间复杂度O(1)\mathcal{O}(1)。
参考代码（C++）
class Solution {
public:
    int countGoodSubstrings(string s) {
        int ans = 0;
        for (int i = 0; i + 2 < s.size(); ++i)
            if (s[i] != s[i + 1] && s[i] != s[i + 2] && s[i + 1] != s[i + 2])
                ans++;
        return ans;
    }
};

Python一行解法：

参考代码（Python 3）
class Solution:
    def countGoodSubstrings(self, s: str) -> int:
        return len([i for i in range(len(s) - 2) if len(set(s[i:i + 3])) == 3])

tip 注意

这一解法的空间复杂度并不是O(1)\mathcal{O}(1)。

:::

Problem B - 数组中最大数对和的最小值​

方法一：贪心​

显然，我们应当将最大元素和最小元素配对，否则无论将最大元素与其他哪一个元素配对，数对和都不会更小。依次类推，我们需要把第二大的元素和第二小的元素配对，第三大的元素和第三小的元素配对……

  • 时间复杂度为O(Nlog⁡N)\mathcal{O}(N\log N)。
  • 空间复杂度O(1)\mathcal{O}(1)。
参考代码（C++）
class Solution {
public:
    int minPairSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = 0, n = nums.size();
        for (int i = 0; i < n / 2; ++i)
            ans = max(ans, nums[i] + nums[n - i - 1]);
        return ans;
    }
};

Python一行解法：

参考代码（Python 3）
class Solution:
    def minPairSum(self, nums: List[int]) -> int:
        return max(a + b for a, b in zip(sorted(nums), sorted(nums)[::-1]))

tip 注意

这一解法的空间复杂度并不是O(1)\mathcal{O}(1)。

:::

Problem C - 矩阵中最大的三个菱形和​

方法一：前缀和​

令l[i][j][k]l[i][j][k]表示从(i,j)(i,j)开始，向左上方走kk步的和；r[i][j][k]r[i][j][k]表示从(i,j)(i,j)开始，向右上方走kk步的和。借鉴前缀和的做法，我们可以在O(NMmin⁡(N,M))\mathcal{O}(NM\min(N,M))的时间里求出这些和。

题目要求三个最大的不同的菱形和，因此我们使用一个set来存储这些和，每当set中元素超过33个，我们就删去最小的那个值。因为任意时刻set中的元素数目不会超过44个，所以所有对set的操作的时间复杂度可以视为O(1)\mathcal{O}(1)。

我们可以枚举菱形最下方的点和菱形的大小来遍历所有的菱形。设菱形最下方的点为(i,j)(i,j)。对于一个面积不为00的菱形，其边界上的元素之和可以表示为四边的元素和减去四个顶点的元素和。而四边的元素和可以借助上面求出的前缀和快速获得。这样我们就可以在O(1)\mathcal{O}(1)时间内求得这一菱形的边界元素和。总共有O(NMmin⁡(N,M))\mathcal{O}(NM\min(N,M))个这样的菱形，因此总的时间复杂度也为O(NMmin⁡(N,M))\mathcal{O}(NM\min(N,M))。

注意面积为00的菱形需要单独处理。

  • 时间复杂度O(NMmin⁡(N,M))\mathcal{O}(NM\min(N,M))。
  • 空间复杂度O(NMmin⁡(N,M))\mathcal{O}(NM\min(N,M))。
参考代码（C++）
class Solution {
public:
    vector<int> getBiggestThree(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int h = min(n, m);
        vector<vector<vector<int>>> l(n, vector<vector<int>>(m, vector<int>(h)));
        vector<vector<vector<int>>> r(l);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                l[i][j][0] = r[i][j][0] = grid[i][j];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                for (int k = 1; i + k < n && j + k < m; ++k)
                    l[i + k][j + k][k] = l[i + k - 1][j + k - 1][k - 1] + grid[i + k][j + k]; 
                for (int k = 1; i + k < n && j - k >= 0; ++k)
                    r[i + k][j - k][k] = r[i + k - 1][j - k + 1][k - 1] + grid[i + k][j - k];
            }
        set<int> pq;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                pq.insert(grid[i][j]);
                if (pq.size() > 3)
                    pq.erase(pq.begin());
                for (int k = 1; i - k * 2 >= 0 && j - k >= 0 && j + k < m; ++k) {
                    int s = l[i][j][k] + r[i][j][k] + r[i - k][j - k][k] + l[i - k][j + k][k] - grid[i][j] - grid[i - k][j - k] - grid[i - k][j + k] - grid[i - 2 * k][j];
                    pq.insert(s);
                    if (pq.size() > 3)
                        pq.erase(pq.begin());
                }
            }
        return vector<int>(pq.rbegin(), pq.rend());
    }
};

Problem D - 两个数组最小的异或值之和​

方法一：状态压缩动态规划​

看到n=14n=14，考虑使用状态压缩动态规划。

本题中的状态是很显然的，我们可以用statestate表示当前nums2数组中元素的使用情况。对于给定的statestate，我们可以选择一个尚未使用的元素（设其为nums2的第kk个元素，则需要满足state & 2k=0state\ \&\ 2^k=0）与nums1的当前元素配对，从而进行状态转移（state→state ∣ 2kstate\rightarrow state\ |\ 2^k）。

初值为dp[0]=0dp[0]=0，其余为∞\infty。

  • 时间复杂度O(N2⋅2N)\mathcal{O}(N^2\cdot2^N)。
  • 空间复杂度O(2N)\mathcal{O}(2^N)。
参考代码（C++）
class Solution {
public:
    int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        vector<int> dp(1 << n, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = (1 << n) - 1; j >= 0; --j) {
                if (dp[j] < INT_MAX) {
                    for (int k = 0; k < n; ++k) {
                        if ((j & (1 << k)) == 0) {
                            int nxt = j ^ (1 << k);
                            dp[nxt] = min(dp[nxt], dp[j] + (nums1[i] ^ nums2[k]));
                        }
                    }
                }
            }
        }
        return dp[(1 << n) - 1];
    }
};

事实上，对于一个给定的statestate，我们可以根据其二进制中11的个数来求出添加下一个元素时，对应于nums1中的第几个元素，从而可以将时间复杂度降低到O(N⋅2N)\mathcal{O}(N\cdot2^N)。

参考代码（C++）
class Solution {
public:
    int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        vector<int> dp(1 << n, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i + 1 < (1 << n); ++i) {
            int j = __builtin_popcount(i);
            for (int k = 0; k < n; ++k)
                if (!(i & (1 << k)))
                    dp[i ^ (1 << k)] = min(dp[i ^ (1 << k)], dp[i] + (nums1[j] ^ nums2[k]));
        }
        return dp[(1 << n) - 1];
    }
};