Leetcode 第 362 场周赛题解

Leetcode 第 362 场周赛题解

题目1：2848. 与车相交的点

思路

哈希。

代码

/** @lc app=leetcode.cn id=2848 lang=cpp** [2848] 与车相交的点*/// @lc code=start
class Solution
{
public:int numberOfPoints(vector<vector<int>> &nums){vector<bool> seat(101, false);for (const vector<int> &num : nums){int start = num[0], end = num[1];for (int i = start; i <= end; i++)seat[i] = true;}int count = 0;for (int i = 1; i <= 100; i++)if (seat[i])count++;return count;}
};
// @lc code=end

复杂度分析

时间复杂度：O(n)，其中 n 为数组 nums 的长度。

空间复杂度：O(L)，辅助数组的长度，据题意 L = 100。

题目2：2849. 判断能否在给定时间到达单元格

思路

脑筋急转弯。

带点贪心的思想。

代码

class Solution
{
public:bool isReachableAtTime(int sx, int sy, int fx, int fy, int t){if (t == 1 && sx == fx && sy == fy)return false;return abs(sx - fx) <= t && abs(sy - fy) <= t;}
};

复杂度分析

时间复杂度：O(1)。

空间复杂度：O(1)，没有辅助变量。

题目3：2850. 将石头分散到网格图的最少移动次数

思路

暴力列举全排列，每次计算出一个曼哈顿距离，更新最小值即为最小移动次数。

代码

/** @lc app=leetcode.cn id=2850 lang=cpp** [2850] 将石头分散到网格图的最少移动次数*/// @lc code=start
class Solution
{
public:int minimumMoves(vector<vector<int>> &grid){int m = grid.size(), n = m ? grid[0].size() : 0; // m = n = 3// 所有移走的石子个数 = 所有移入的石子个数（grid[i][j] = 0）vector<pair<int, int>> from; // 移走石子坐标数组vector<pair<int, int>> to;   // 移入石子坐标数组// 构建 from 和 to 数组for (int i = 0; i < 3; i++)for (int j = 0; j < 3; j++){if (grid[i][j] > 1){// 有 grid[i][j] - 1 个可以移走的石子for (int k = 0; k < grid[i][j] - 1; k++)from.push_back(make_pair(i, j));}else if (grid[i][j] == 0)to.push_back(make_pair(i, j));}// 枚举 from 的全部排列可能，与 to 匹配，求 from[i] 和 to[i] 的曼哈顿距离之和，最小值即为答案int minCount = __INT_MAX__; // 最少移动次数// 使用 next_permutation 枚举全排列必须先对数组进行排序sort(from.begin(), from.end());do{int count = 0;for (int i = 0; i < from.size(); i++){// 计算曼哈顿距离count += abs(from[i].first - to[i].first) + abs(from[i].second - to[i].second);}minCount = min(minCount, count); // 更新答案} while (next_permutation(from.begin(), from.end()));return minCount;}
};
// @lc code=end

复杂度分析

时间复杂度：O(m×n×(m×n)!)，使用 STL 函数 next_permutation 进行全排列的时间复杂度为O((m×n)!)，循环内计算单次计算曼哈顿距离的时间复杂度为O(m×n)，其中 m、n 分别为矩阵 gird 的长度和宽度，m = n = 3。

空间复杂度：O(mn)，为辅助数组 from 和 to 的空间，其中 m、n 分别为矩阵 gird 的长度和宽度，m = n = 3。

题目4：2851. 字符串转换

超出能力范围。

思路

矩阵快速幂优化 DP（矩阵快速幂 + 动态规划 + KMP）

视频讲解：

https://www.bilibili.com/video/BV1U34y1N7Pe/?vd_source=df165d34990cd0aa2cacb2c452e99aad

代码

/** @lc app=leetcode.cn id=2851 lang=cpp** [2851] 字符串转换*/// @lc code=start// 矩阵快速幂优化 DPclass Solution
{
public:int numberOfWays(string s, string t, long long k){int n = s.size();int c = kmp_search(s + s.substr(0, n - 1), t);vector<vector<long long>> m = {{c - 1, c},{n - c, n - 1 - c}};m = pow(m, k);return m[0][s != t];}private:// KMP 模板vector<int> calc_max_match(string s){vector<int> match(s.size());int c = 0;for (int i = 1; i < s.size(); i++){char v = s[i];while (c && s[c] != v)c = match[c - 1];if (s[c] == v)c++;match[i] = c;}return match;}// KMP 模板// 返回 text 中出现了多少次 pattern（允许 pattern 重叠）int kmp_search(string text, string pattern){vector<int> match = calc_max_match(pattern);int match_cnt = 0, c = 0;for (int i = 0; i < text.size(); i++){char v = text[i];while (c && pattern[c] != v)c = match[c - 1];if (pattern[c] == v)c++;if (c == pattern.size()){match_cnt++;c = match[c - 1];}}return match_cnt;}const long long MOD = 1e9 + 7;// 矩阵乘法vector<vector<long long>> multiply(vector<vector<long long>> &a, vector<vector<long long>> &b){vector<vector<long long>> c(2, vector<long long>(2));for (int i = 0; i < 2; i++)for (int j = 0; j < 2; j++)c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % MOD;return c;}// 矩阵快速幂vector<vector<long long>> pow(vector<vector<long long>> &a, long long n){vector<vector<long long>> res = {{1, 0}, {0, 1}};for (; n; n /= 2){if (n % 2)res = multiply(res, a);a = multiply(a, a);}return res;}
};
// @lc code=end

复杂度分析

时间复杂度：O(n+logk)，其中 n 为字符串 s 的长度。

空间复杂度：O(n)，其中 n 为字符串 s 的长度。