怎么上网做网站,亚马逊推广,微信小程序源码免费,用js做的网站代码Leetcode 第 362 场周赛题解 Leetcode 第 362 场周赛题解题目1#xff1a;2848. 与车相交的点思路代码复杂度分析 题目2#xff1a;2849. 判断能否在给定时间到达单元格思路代码复杂度分析 题目3#xff1a;2850. 将石头分散到网格图的最少移动次数思路代码复杂度分析 题目4… Leetcode 第 362 场周赛题解 Leetcode 第 362 场周赛题解题目12848. 与车相交的点思路代码复杂度分析 题目22849. 判断能否在给定时间到达单元格思路代码复杂度分析 题目32850. 将石头分散到网格图的最少移动次数思路代码复杂度分析 题目42851. 字符串转换思路代码复杂度分析 Leetcode 第 362 场周赛题解
题目12848. 与车相交的点
思路
哈希。
代码
/** lc appleetcode.cn id2848 langcpp** [2848] 与车相交的点*/// lc codestart
class Solution
{
public:int numberOfPoints(vectorvectorint nums){vectorbool seat(101, false);for (const vectorint 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 codeend复杂度分析
时间复杂度O(n)其中 n 为数组 nums 的长度。
空间复杂度O(L)辅助数组的长度据题意 L 100。
题目22849. 判断能否在给定时间到达单元格
思路
脑筋急转弯。
带点贪心的思想。
代码
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)没有辅助变量。
题目32850. 将石头分散到网格图的最少移动次数
思路
暴力列举全排列每次计算出一个曼哈顿距离更新最小值即为最小移动次数。
代码
/** lc appleetcode.cn id2850 langcpp** [2850] 将石头分散到网格图的最少移动次数*/// lc codestart
class Solution
{
public:int minimumMoves(vectorvectorint grid){int m grid.size(), n m ? grid[0].size() : 0; // m n 3// 所有移走的石子个数 所有移入的石子个数grid[i][j] 0vectorpairint, int from; // 移走石子坐标数组vectorpairint, 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 codeend复杂度分析
时间复杂度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。
题目42851. 字符串转换
超出能力范围。
思路
矩阵快速幂优化 DP矩阵快速幂 动态规划 KMP
视频讲解
https://www.bilibili.com/video/BV1U34y1N7Pe/?vd_sourcedf165d34990cd0aa2cacb2c452e99aad
代码
/** lc appleetcode.cn id2851 langcpp** [2851] 字符串转换*/// lc codestart// 矩阵快速幂优化 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);vectorvectorlong long m {{c - 1, c},{n - c, n - 1 - c}};m pow(m, k);return m[0][s ! t];}private:// KMP 模板vectorint calc_max_match(string s){vectorint 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){vectorint 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;// 矩阵乘法vectorvectorlong long multiply(vectorvectorlong long a, vectorvectorlong long b){vectorvectorlong long c(2, vectorlong 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;}// 矩阵快速幂vectorvectorlong long pow(vectorvectorlong long a, long long n){vectorvectorlong long res {{1, 0}, {0, 1}};for (; n; n / 2){if (n % 2)res multiply(res, a);a multiply(a, a);}return res;}
};
// lc codeend复杂度分析
时间复杂度O(nlogk)其中 n 为字符串 s 的长度。
空间复杂度O(n)其中 n 为字符串 s 的长度。
