男女做暧昧试看网站,哪个网站学seo是免费的,做网站前台和后台是什么,微信营销平台源码下载LeetCode第373场周赛 目录 循环移位后的矩阵相似检查统计美丽子字符串 I交换得到字典序最小的数组统计美丽子字符串 II 循环移位后的矩阵相似检查
循环移位后的矩阵相似检查 分析#xff1a; 简单模拟 这道题目就是一个简单的模拟题#xff0c;直接按照题目意思进行判断即可…LeetCode第373场周赛 目录 循环移位后的矩阵相似检查统计美丽子字符串 I交换得到字典序最小的数组统计美丽子字符串 II 循环移位后的矩阵相似检查
循环移位后的矩阵相似检查 分析 简单模拟 这道题目就是一个简单的模拟题直接按照题目意思进行判断即可。不难发现其实左移右移后如果初始矩阵和最终矩阵完全相同那么左移右移是等价的比如对于下标为j的数右移后相等即 m a t [ i ] [ j ] m a t [ i ] [ j k ] mat[i][j] mat[i][jk] mat[i][j]mat[i][jk]对于下标为jk的数左移后相等即 m a t [ i ] [ j k ] m a t [ i ] [ j ] mat[i][j k] mat[i][j] mat[i][jk]mat[i][j]。所以二者等价。
代码
class Solution {
public:bool areSimilar(vectorvectorint mat, int k) {bool flag true;int n mat.size(), m mat[0].size();k % m;for(int i 0; i n; i){for(int j 0; j m; j){int v (j k) % m;if(mat[i][v] mat[i][j])continue;flag false;}}return flag;}
};时间复杂度: O ( n ) O(n) O(n) 空间复杂度: O ( 1 ) O(1) O(1)
统计美丽子字符串 I
统计美丽子字符串 I 分析 维护前缀和 对于这个题目因为数据范围较小所以可以使用 O ( n 2 ) O(n^2) O(n2)的算法。如果直接暴力枚举每一个子字符串再来判断是否是美丽子字符串的话时间复杂度为 O ( n 3 ) O(n^3) O(n3)那么我们可以在判断是否是美丽子字符串上来优化。 如何判断一个字符串是美丽的呢我们可以提前维护一个前缀的元音辅音字母的数量那么可以在 O ( 1 ) O(1) O(1)的时间复杂度下得到一个区间的元音辅音数量再按照题目意思进行判断即可
代码
class Solution {
public:int beautifulSubstrings(string s, int k) {int n s.size();//预处理一个前缀的元音辅音数量vectorintpre1(n 1, 0), pre2(n 1, 0);for(int i 0; i n ; i){if(s[i] a || s[i] e || s[i] i || s[i] o || s[i] u)pre1[i 1] pre1[i] 1, pre2[i 1] pre2[i];else pre2[i 1] pre2[i] 1, pre1[i 1] pre1[i];}int cnt 0;for(int l 0; l n ; l){for(int r l 1; r n; r ){int a pre1[r 1] - pre1[l];int b pre2[r 1] - pre2[l];if(a b (a * b) % k 0)cnt;}}return cnt;}
};时间复杂度: O ( n 2 ) O(n^2) O(n2) 空间复杂度: O ( n 2 ) O(n^2) O(n2)
交换得到字典序最小的数组
交换得到字典序最小的数组 分析 排序分组维护 分析题意我们可以知道对于两两之间距离在limit范围内的两个数我们将它们添加进一个组里面最终可以得到若干两两相距在limit范围内的数。比如 l i m i t 2 limit2 limit2对数组 [ 1 , 5 , 3 , 9 , 8 ] [1,5,3,9,8] [1,5,3,9,8] [ 1 , 3 , 5 ] [1,3,5] [1,3,5] [ 8 , 9 ] [8,9] [8,9]分别为一组。这样的每一组里面的所有数字都是可以任意交换位置的(不能直接交换的数也可以间接的交换)。所以本题我们的目的就是要得到若干个这样的组对每个组里面按照从小到大的顺序排序就是最终的结果。 具体要怎么做呢 首先我们可以维护一个 q q q数组它代表的是 n u m s nums nums数组的值从小到大排序后原来的下标的序列。 然后我们遍历这个序列每一次处理一段数字这一段数字要求满足相邻两个数之间的距离 ≤ l i m i t \le limit ≤limit。 比如对于数组 [ 1 , 7 , 6 , 18 , 2 , 1 ] [1,7,6,18,2,1] [1,7,6,18,2,1]其 q q q数组为 [ 0 , 5 , 4 , 2 , 1 , 3 ] [0,5,4,2,1,3] [0,5,4,2,1,3]。处理的第一段数字为 [ 0 , 5 , 4 ] [0,5,4] [0,5,4]即下标为054的三个数。那么对这三个数直接按照从小到大的顺序放在0,4,5的三个位置即可。因为只有这一段数字里面的位置可以任意交换。可以用set来存下来这几个下标存入后是按照顺序排列的然后直接放入这几个数字即可。
代码
class Solution {
public:vectorint lexicographicallySmallestArray(vectorint nums, int limit) {//在limit范围内可以构成多个闭环每一个闭环按照顺序排序即可int n nums.size();vectorintq(n);iota(q.begin(), q.end(), 0);sort(q.begin(), q.end(),[](int i, int j){return nums[i] nums[j] ;});//处理每一个limit范围vectorintans(n);for(int l 0; l n; ){int r l 1;setintp;p.insert(q[l]);while(r n nums[q[r]] - nums[q[r - 1]] limit){p.insert(q[r]);r;}// coutl rendl;//l~r是一个limit范围内的一些数字这里面的数字可以随意交换位置auto it p.begin();for(int i l; i r; i, it)ans[*it] nums[q[i]];l r;}return ans;}
};时间复杂度: O ( n log n ) O(n \log n) O(nlogn) 空间复杂度: O ( n ) O(n) O(n)
统计美丽子字符串 II
统计美丽子字符串 II
分析 前缀和分解质因数哈希表 这道题是I的加强版数据范围变大了所以在I中使用的前缀和的 O ( n 2 ) O(n^2) O(n2)算法不适用了。 那么我们要考虑更加快速的方法。 前缀和 首先我们换一种维护前缀和的思路不妨令元音为1辅音为-1。则元音字母和辅音字母的数量相等即找到一个和为0的连续子数组。 则任何一个满足条件的子数组 ( j , i ] (j,i] (j,i]中有 s u m [ i ] − s u m [ j ] 0 sum[i] - sum[j] 0 sum[i]−sum[j]0。 分解质因数 设子数组的长度为L由于元音辅音数量相等所以元音辅音数量都等于 L 2 \frac{L}{2} 2L 所以元音字母和辅音字母的数量的乘积能被k整除等价于 ( L 2 ) 2 m o d k 0 (\frac{L}{2})^2\ mod \ k 0 (2L)2 mod k0 即 L 2 m o d ( 4 k ) 0 L^2\ mod \ (4k) 0 L2 mod (4k)0 再来考虑如果 L 2 m o d k ′ 0 L^2 mod \ k 0 L2mod k′0时 L L L满足什么条件呢 假设 k ’ k’ k’是一个质数假如是 3 3 3那么 L L L只要满足是 3 3 3的倍数就行了此时平方被我们去掉了。 如果 k ′ k k′是一个指数 p p p的 v v v次幂呢
如果v是偶数比如 3 4 3^4 34那么L只要是 3 2 3^2 32的倍数就行了如果v是奇数比如 3 5 3^5 35那么L只要是 3 3 3^3 33的倍数就行了。
综上L中至少要包含 p r p^r pr其中 r ⌈ e 2 ⌉ r\left \lceil \dfrac{e}{2} \right \rceil r⌈2e⌉ 如果 k ′ k k′中包含多个质因数则对每个质因数都按照上述方法求解即可这样我们就可以得到 L L L至少是一个数的倍数的条件了去掉了平方。 哈希表 在得到了上面的条件后 L L L必须是 k ′ k k′的倍数那么会有什么情况出现呢 现在的问题是有多少个和为0的子数组其长度是k’的倍数。 对于一个子数组下标为 ( j , i ] (j,i] (j,i]长度 L i − j L i-j Li−j若满足上述条件有 ( i − j ) m o d k ′ 0 (i-j) \ mod\ k 0 (i−j) mod k′0 则有 i m o d k ′ j m o d k ′ i \ mod\ k j \ mod\ k i mod k′j mod k′ 对前缀和来说则有 s u m [ i ] − s u m [ j ] 0 sum[i]-sum[j]0 sum[i]−sum[j]0 即 s u m [ i ] s u m [ j ] sum[i]sum[j] sum[i]sum[j] 当我们同时满足 i m o d k ′ j m o d k ′ i \ mod\ k j \ mod\ k i mod k′j mod k′和 s u m [ i ] s u m [ j ] sum[i]sum[j] sum[i]sum[j]的条件时则这个子数组是美丽子数组那么我们可以一起用哈希表维护这两个值。 哈希表的key就是一个pair: i m o d k ′ i \ mod\ k i mod k′和 s u m [ i ] sum[i] sum[i]哈希表的 value 是这个 pair 的出现次数。 注意在最一开始需要加入一个pair: k ‘ − 1 , 0 {k‘-1,0} k‘−1,0因为我们的前缀维护时下标为 0 0 0时计算的是第二个前缀和第一个前缀和(就是什么都没有的时候和为 0 0 0)。相当于在下标为 − 1 -1 −1的时候计算 − 1 -1 −1和 k ’ − 1 k’-1 k’−1同余则最开始加入其中。 代码
class Solution {
public:int get_base(int k){//分解质因子int ans 1;for(int i 2; i * i k; i){int cnt 0;while(k % i 0){cnt;k / i;}ans * pow(i, (cnt 1)/ 2);}if(k 1)ans * k;return ans;}long long beautifulSubstrings(string s, int k) {//根据条件(L/2)^2 % k 0 即 L^2 %(4k) 0 先判断L要满足什么样的条件k get_base(4 * k);mappairint, int, intcnt;int n s.size();long long ans 0;int sum 0;//计算前缀 sum[-1] 0 下标-1就是表示没有数字的时候的前缀和int flag 1 | (1 (e - a)) | (1 (i - a)) | (1 (o - a)) | (1 (u - a));cnt[{k - 1, 0}]; //加入和-1同余的k-1-1下标相当于前缀和数组中什么都没有的情况此时前缀和为0for(int i 0; i n; i){sum ((1 (s[i] - a)) flag) 0 ? 1 : -1;ans cnt[{i % k, sum}];}return ans;}
};时间复杂度: O ( n k ) O(n\sqrt k) O(nk ) 空间复杂度: O ( n ) O(n) O(n)
