python适合网站开发吗,定州建设厅网站,博览局网站建设,社区网站模版Leetcode 第 130 场双周赛题解 Leetcode 第 130 场双周赛题解题目1#xff1a;3142. 判断矩阵是否满足条件思路代码复杂度分析 题目2#xff1a;3143. 正方形中的最多点数思路代码复杂度分析 题目3#xff1a;3144. 分割字符频率相等的最少子字符串思路代码复杂度分析 题目4… Leetcode 第 130 场双周赛题解 Leetcode 第 130 场双周赛题解题目13142. 判断矩阵是否满足条件思路代码复杂度分析 题目23143. 正方形中的最多点数思路代码复杂度分析 题目33144. 分割字符频率相等的最少子字符串思路代码复杂度分析 题目43145. 大数组元素的乘积思路代码复杂度分析 Leetcode 第 130 场双周赛题解
题目13142. 判断矩阵是否满足条件
思路
两次遍历第一次判断每行相邻元素是否不同第二次判断每列元素是否相同。
代码
class Solution
{
public:bool satisfiesConditions(vectorvectorint grid){int m grid.size(), n m ? grid[0].size() : 0;for (int i 0; i m; i)for (int j 1; j n; j)if (grid[i][j] grid[i][j - 1])return false;for (int j 0; j n; j)for (int i 1; i m; i)if (grid[i][j] ! grid[i - 1][j])return false;return true;}
};复杂度分析
时间复杂度O(m*n)其中 m 和 n 分别是二维数组 grid 的行数和列数。
空间复杂度O(1)。
题目23143. 正方形中的最多点数
思路
基于贪心的思想要使正方形中可以包含最多点数点放在正方形的边界上是最好的。
假设一个点的坐标为 (x, y)要使正方形包含这个点它的边长的一半应该是 max(abs(x), abs(y))。
遍历 points统计 mx max(abs(points[i][0]), abs(points[i][1]))对应字符是 s[i]组成一个 pair插入数组 combined。
对 combined 按 mx 从小到大排序因为要使得正方形内不存在标签相同的两个点我们用一个集合存储当前正方形内字符。
设当前正方形边长的一半为 bound遍历排好序的 combined设当前 pair 为 entry。如果 entry.first bound更新 bound entry.first用一个变量 ans 保存此时集合的大小。
看当前 pair 的字符 entry.second 是否在集合中如果不在就插入 entry.second否则说明边界不能再拓展了不插入返回 ans。
代码
class Solution
{
public:int maxPointsInsideSquare(vectorvectorint points, string s){vectorpairint, char combined;for (int i 0; i points.size(); i){int mx max(abs(points[i][0]), abs(points[i][1]));combined.push_back({mx, s[i]});}sort(combined.begin(), combined.end(),[](const pairint, char p1, const pairint, char p2){return p1.first p2.first;});unordered_setchar set;int bound 0, ans 0;for (auto entry : combined){if (entry.first bound){bound entry.first;ans set.size();}if (set.count(entry.second) 0)set.insert(entry.second);elsereturn ans;}return set.size();}
};复杂度分析
时间复杂度O(nlogn)其中 n 是数组 points 的长度。
空间复杂度O(n)其中 n 是数组 points 的长度。
题目33144. 分割字符频率相等的最少子字符串
思路
设 dp[i] 表示前 i 个字符最少能分割成多少平衡子串。
转移方程为dp[i]min(dp[j]1)
其中第 (j1) 个字符到第 i 个字符需要组成一个平衡字符串。我们可以考虑一边从大到小枚举 j一边维护它是不是一个平衡字符串。
为了检查一个字符串是否平衡我们只要知道字符串里出现过几种字母设出现过 alphaCnt 种以及出现次数最多的字母的频率设出现了 maxFreq 次。只要 alphaCnt*maxFreq 等于字符串长度 i-j这个字符串就是平衡的。
代码
class Solution
{
public:int minimumSubstringsInPartition(string s){int n s.length();// dp[i] 表示前 i 个字符最少能分割成多少平衡子串vectorint dp(n 1, INT_MAX);dp[0] 0;int cnt[26];for (int i 1; i n; i){memset(cnt, 0, 26 * sizeof(int));int alphaCnt 0; // s[j1, i] 出现不同的字符数int maxFreq 0; // s[j1, i] 字符的最大次数for (int j i - 1; j 0; j--){cnt[s[j] - a];if (cnt[s[j] - a] 1)alphaCnt;maxFreq max(maxFreq, cnt[s[j] - a]);if (alphaCnt * maxFreq i - j)dp[i] min(dp[i], dp[j] 1);}}return dp[n];}
};复杂度分析
时间复杂度O(n2)其中 n 是字符串 s 的长度。
空间复杂度O(n)其中 n 是字符串 s 的长度。
题目43145. 大数组元素的乘积
思路
题解O(log) 试填法Python/Java/C/Go
代码
class Solution
{int pow(long long x, long long n, long long mod){long long res 1 % mod;for (; n; n / 2){if (n % 2)res res * x % mod;x x * x % mod;}return res;}long long sum_e(long long k){long long res 0, n 0, cnt1 0, sumI 0;for (long long i 63 - __builtin_clzll(k 1); i; i--){long long c (cnt1 i) (i (i - 1)); // 新增的幂次个数if (c k){k - c;res (sumI i) ((i * (i - 1) / 2) (i - 1));sumI i; // 之前填的 1 的幂次之和cnt1; // 之前填的 1 的个数n | 1LL i; // 填 1}}// 最低位单独计算if (cnt1 k){k - cnt1;res sumI;n; // 填 1}// 剩余的 k 个幂次由 n 的低 k 个 1 补充while (k--){res __builtin_ctzll(n);n n - 1;}return res;}public:vectorint findProductsOfElements(vectorvectorlong long queries){vectorint ans;for (auto q : queries){auto er sum_e(q[1] 1);auto el sum_e(q[0]);ans.push_back(pow(2, er - el, q[2]));}return ans;}
};复杂度分析
时间复杂度O(qlogr)其中 q 为数组 queries 的长度rmax(toi)。
空间复杂度O(1)。
