且听疯吟

leetcode biweekly contes 108

2023-07-09

leetcode biweekly contes 108

本周两场周赛放水都很严重啊，竟然没有 $6$ 分的题目。

2765. 最长交替子序列

给你一个下标从 0 开始的整数数组 nums 。如果 nums 中长度为 m 的子数组 s 满足以下条件，我们称它是一个交替子序列：

  • m 大于 1 。
  • s1 = s0 + 1 。
  • 下标从 0 开始的子数组 s 与数组 [s0, s1, s0, s1,...,s(m-1) % 2] 一样。也就是说，s1 - s0 = 1 ，s2 - s1 = -1 ，s3 - s2 = 1 ，s4 - s3 = -1 ，以此类推，直到 s[m - 1] - s[m - 2] = (-1)m 。

请你返回 nums 中所有 交替 子数组中，最长的长度，如果不存在交替子数组，请你返回 -1 。

子数组是一个数组中一段连续 非空 的元素序列。

示例 1：

输入：nums = [2,3,4,3,4]
输出：4
解释：交替子数组有 [3,4] ，[3,4,3] 和 [3,4,3,4] 。最长的子数组为 [3,4,3,4] ，长度为4 。

示例 2：

输入：nums = [4,5,6]
输出：2
解释：[4,5] 和 [5,6] 是仅有的两个交替子数组。它们长度都为 2 。

提示：

  • 2 <= nums.length <= 100
  • 1 <= nums[i] <= 104

地址

https://leetcode.cn/contest/biweekly-contest-108/problems/longest-alternating-subarray/

题意

直接模拟

思路

  1. 可以直接进行模拟即可，时间复杂度为 $O(n^2)$，还可以继续优化到 $O(n)$ 即可，比较简单的题目。
  2. 复杂度分析：
  • 时间复杂度：$O(n^2)$，其中 $n$ 表示数组的长度。
  • 空间复杂度：$O(1)$。

代码

class Solution {
public:
    int alternatingSubarray(vector<int>& nums) {
        int n = nums.size();
        int res = -1;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((j - i) % 2) {
                    if (nums[j] - nums[j - 1] == 1) {
                        res = max(res, j - i + 1);
                    } else {
                        break;
                    }
                } else {
                    if (nums[j] - nums[j - 1] == -1) {
                        res = max(res, j - i + 1);
                    } else {
                        break;
                    }
                }
            }
        }
        return res;
    }
};

6469. 重新放置石块

给你一个下标从 0 开始的整数数组 nums ，表示一些石块的初始位置。再给你两个长度 相等 下标从 0 开始的整数数组 moveFrom 和 moveTo 。

在 moveFrom.length 次操作内，你可以改变石块的位置。在第 i 次操作中，你将位置在 moveFrom[i] 的所有石块移到位置 moveTo[i] 。

完成这些操作后，请你按升序返回所有 有 石块的位置。

注意：

  • 如果一个位置至少有一个石块，我们称这个位置 有 石块。
  • 一个位置可能会有多个石块。

示例 1：

输入：nums = [1,6,7,8], moveFrom = [1,7,2], moveTo = [2,9,5]
输出：[5,6,8,9]
解释：一开始，石块在位置 1,6,7,8 。
第 i = 0 步操作中，我们将位置 1 处的石块移到位置 2 处，位置 2,6,7,8 有石块。
第 i = 1 步操作中，我们将位置 7 处的石块移到位置 9 处，位置 2,6,8,9 有石块。
第 i = 2 步操作中，我们将位置 2 处的石块移到位置 5 处，位置 5,6,8,9 有石块。
最后，至少有一个石块的位置为 [5,6,8,9] 。

示例 2：

输入：nums = [1,1,3,3], moveFrom = [1,3], moveTo = [2,2]
输出：[2]
解释：一开始，石块在位置 [1,1,3,3] 。
第 i = 0 步操作中，我们将位置 1 处的石块移到位置 2 处，有石块的位置为 [2,2,3,3] 。
第 i = 1 步操作中，我们将位置 3 处的石块移到位置 2 处，有石块的位置为 [2,2,2,2] 。
由于 2 是唯一有石块的位置，我们返回 [2] 。

提示：

  • 1 <= nums.length <= 105
  • 1 <= moveFrom.length <= 105
  • moveFrom.length == moveTo.length
  • 1 <= nums[i], moveFrom[i], moveTo[i] <= 109
  • 测试数据保证在进行第 i 步操作时，moveFrom[i] 处至少有一个石块。

地址

https://leetcode.cn/contest/weekly-contest-352/problems/prime-pairs-with-target-sum/

题意

直接模拟 + 哈希

思路

  1. 利用哈希表统计，每次移动时对哈希表内的值进行移动，比如将坐标 $x$ 的点移动到坐标 $y$:
    • $cnt[y] += cnt[x]$;
    • $cnt[x] = 0$;
  2. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 为数组的长度。
  • 空间复杂度：$O(n)$，其中 $n%$ 为数组的长度。

代码

class Solution {
public:
    vector<int> relocateMarbles(vector<int>& nums, vector<int>& moveFrom, vector<int>& moveTo) {
        unordered_map<int, int> cnt;
        for (auto v : nums) {
            cnt[v]++;
        }
        for (int i = 0; i < moveFrom.size(); i++) {
            int from = moveFrom[i];
            int to = moveTo[i];
            int x = cnt[from];
            cnt[from] = 0;
            cnt[to] += x;
        }
        vector<int> res;
        for (auto [v, x] : cnt) {
            if (x > 0) {
                res.emplace_back(v);
            }
        }
        sort(res.begin(), res.end());
        return res;
    }
};

6923. 将字符串分割为最少的美丽子字符串

给你一个二进制字符串 s ，你需要将字符串分割成一个或者多个 子字符串 ，使每个子字符串都是 美丽 的。

如果一个字符串满足以下条件，我们称它是 美丽 的：

  • 它不包含前导 0 。
  • 它是 5 的幂的 二进制 表示。

请你返回分割后的子字符串的 最少 数目。如果无法将字符串 s 分割成美丽子字符串，请你返回 -1 。

子字符串是一个字符串中一段连续的字符序列。

示例 1：

输入：s = "1011"
输出：2
解释：我们可以将输入字符串分成 ["101", "1"] 。
- 字符串 "101" 不包含前导 0 ，且它是整数 51 = 5 的二进制表示。
- 字符串 "1" 不包含前导 0 ，且它是整数 50 = 1 的二进制表示。
最少可以将 s 分成 2 个美丽子字符串。

示例 2：

输入：s = "111"
输出：3
解释：我们可以将输入字符串分成 ["1", "1", "1"] 。
- 字符串 "1" 不包含前导 0 ，且它是整数 50 = 1 的二进制表示。
最少可以将 s 分成 3 个美丽子字符串。

示例 3：

输入：s = "0"
输出：-1
解释：无法将给定字符串分成任何美丽子字符串。

提示：

  • 1 <= s.length <= 15
  • s[i] 要么是 '0' 要么是 '1' 。

地址

https://leetcode.cn/contest/biweekly-contest-108/problems/partition-string-into-minimum-beautiful-substrings/

题意

动态规划

思路

  1. 题目出的不是很好，当然数量级给的太小了，完全的纯暴力解法即可通过，设 $dp[i]$ 表示 前 $i$ 个字符中可被最少分割的美丽字符串的数目，则可以得到以下递推公式：
  • $dp[i] = \min(dp[i], dp[i-j] + 1) \quad if \quad s[i-j+1 \cdots i] is \quad beautiful$ ;
  1. 检测一个字符是否为美丽字符的方法有很多，在这里可以用以下两种方法：
    • 利用 $trie$ 树，将所有为二进制位 $5$ 的幂的数用 $trie$ 树保存起来，每次直接搜索 $trie$ 树即可；
    • 我们可以将子字符串的转化为整数 $x$, 然后检测 $x$ 是否为 $5$ 的幂即可；
  2. 复杂度分析：
  • 时间复杂度：$O(n^3)$，其中 $n$ 表示子数组的数目，利用 $trie$ 优化的话可以优化到 $O(n^2 \log n)$。
  • 空间复杂度：$O(C)$。

代码

class Solution {
public:
    int minimumBeautifulSubstrings(string s) {
        int n = s.size();
        unordered_set<int> cnt;
        cnt.emplace(1);
        int curr = 1;
        for (int i = 1; i <= 10; i++) {
            curr = curr * 5;
            cnt.emplace(curr);
        }
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                string t = s.substr(i - j, j);
                if (t[0] == '0') continue;
                int x = 0;
                for (auto c : t) {
                    x = x * 2 + c - '0';
                }
                if (cnt.count(x) && dp[i - j] != INT_MAX) {
                    dp[i] = min(dp[i], dp[i - j] + 1);
                }
             }
        }
        return dp[n] == INT_MAX ? -1 : dp[n];
    }
};

6928. 黑格子的数目

给你两个整数 m 和 n ，表示一个下标从 0 开始的 m x n 的网格图。

给你一个下标从 0 开始的二维整数矩阵 coordinates ，其中 coordinates[i] = [x, y] 表示坐标为 [x, y] 的格子是 黑色的 ，所有没出现在 coordinates 中的格子都是 白色的。

一个块定义为网格图中 2 x 2 的一个子矩阵。更正式的，对于左上角格子为 [x, y] 的块，其中 0 <= x < m - 1 且 0 <= y < n - 1 ，包含坐标为 [x, y] ，[x + 1, y] ，[x, y + 1] 和 [x + 1, y + 1] 的格子。

请你返回一个下标从 0 开始长度为 5 的整数数组 arr ，arr[i] 表示恰好包含 i 个 黑色 格子的块的数目。

示例 1：

输入：m = 3, n = 3, coordinates = [[0,0]]
输出：[3,1,0,0,0]
解释：网格图如下：

只有 1 个块有一个黑色格子，这个块是左上角为 [0,0] 的块。
其他 3 个左上角分别为 [0,1] ，[1,0] 和 [1,1] 的块都有 0 个黑格子。
所以我们返回 [3,1,0,0,0] 。

示例 2：

输入：m = 3, n = 3, coordinates = [[0,0],[1,1],[0,2]]
输出：[0,2,2,0,0]
解释：网格图如下：

有 2 个块有 2 个黑色格子（左上角格子分别为 [0,0] 和 [0,1]）。
左上角为 [1,0] 和 [1,1] 的两个块，都有 1 个黑格子。
所以我们返回 [0,2,2,0,0] 。

提示：

  • 2 <= m <= 105
  • 2 <= n <= 105
  • 0 <= coordinates.length <= 104
  • coordinates[i].length == 2
  • 0 <= coordinates[i][0] < m
  • 0 <= coordinates[i][1] < n
  • coordinates 中的坐标对两两互不相同。

地址

https://leetcode.cn/problems/number-of-black-blocks/description/

题意

哈希统计

思路

  1. 题目本身比较简单，基本上看到题目就知道解法了，基本解法为点 $(x, y)$ 可能被四种 $2*2$ 的子矩阵包含，所以我们依次枚举这四种情形即可：
    • 子矩阵的顶点为 $(x,y)$, 此时包含的 $4$ 个点分别为 $(x,y), (x+1, y), (x,y+1), (x+1,y+1)$;
    • 子矩阵的顶点为 $(x-1,y-1)$, 此时包含的 $4$ 个点分别为 $(x-1,y-1), (x, y-1), (x-1,y), (x,y)$;
    • 子矩阵的顶点为 $(x-1,y)$, 此时包含的 $4$ 个点分别为 $(x-1,y), (x-1, y+1), (x,y), (x,y+1)$;
    • 子矩阵的顶点为 $(x,y-1)$, 此时包含的 $4$ 个点分别为 $(x,y-1), (x+1, y-1), (x,y), (x+1,y)$;
  2. 分别检测以上四种情形下，该子矩阵覆盖的黑色格子块数即可。
  3. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 表示数组的长度。
  • 空间复杂度：$O(n)$，其中 $n$ 表示数组的长度。

代码

class Solution {
public:
    vector<long long> countBlackBlocks(int m, int n, vector<vector<int>>& coordinates) {
        unordered_set<long long> cnt;
        unordered_set<long long> visit;
        for (auto v : coordinates) {
            cnt.emplace((long long) v[0] * n + v[1]);
        }
        vector<long long> res(5);
        int dir[4][2] = {{0, 0}, {0, 1}, {1, 0}, {1, 1}};
        for (auto v : coordinates) {
            int x = v[0], y= v[1];
            for (int i = max(x - 1, 0); i < min(x + 1, m - 1); i++) {
                for (int j = max(y - 1, 0); j < min(y + 1, n - 1); j++) {
                    long long curr = (long long) i * n + j;
                    if (visit.count(curr)) continue;
                    visit.emplace(curr);
                    int tot = 0;
                    for (int k = 0; k < 4; k++) {
                        if (cnt.count((long long)(i + dir[k][0]) * n + j + dir[k][1])) {
                            tot++;
                        }
                    }
                    res[tot]++;
                }
            }
        }
        res[0] = (long long)(m - 1) * (n - 1) - visit.size();
        return res;
    }
};

欢迎关注和打赏，感谢支持！

Tags: 题解 力扣周赛赛
← leetcode weekly contes 352 leetcode weekly contes 353 →

扫描二维码，分享此文章