怎么把网站做火,wordpress创建编辑器可视化按钮,网站之间如何做视频交换,长沙人才市场招聘文章目录1. 比赛结果2. 题目1. LeetCode 5503. 所有奇数长度子数组的和 easy2. LeetCode 5505. 所有排列中的最大和 medium3. LeetCode 5504. 使数组和能被 P 整除 medium4. LeetCode 5506. 奇怪的打印机 II hard1. 比赛结果
做出来3题。继续加油#xff01;
全国排名#…
文章目录1. 比赛结果2. 题目1. LeetCode 5503. 所有奇数长度子数组的和 easy2. LeetCode 5505. 所有排列中的最大和 medium3. LeetCode 5504. 使数组和能被 P 整除 medium4. LeetCode 5506. 奇怪的打印机 II hard1. 比赛结果
做出来3题。继续加油
全国排名 216 / 28397.61%全球排名 585 / 87506.70%
2. 题目
1. LeetCode 5503. 所有奇数长度子数组的和 easy
题目链接
给你一个正整数数组 arr 请你计算所有可能的奇数长度子数组的和。
子数组 定义为原数组中的一个连续子序列。
请你返回 arr 中 所有奇数长度子数组的和 。
示例 1
输入arr [1,4,2,5,3]
输出58
解释所有奇数长度子数组和它们的和为
[1] 1
[4] 4
[2] 2
[5] 5
[3] 3
[1,4,2] 7
[4,2,5] 11
[2,5,3] 10
[1,4,2,5,3] 15
我们将所有值求和得到
1 4 2 5 3 7 11 10 15 58示例 2
输入arr [1,2]
输出3
解释总共只有 2 个长度为奇数的子数组
[1] 和 [2]。它们的和为 3 。示例 3
输入arr [10,11,12]
输出66提示
1 arr.length 100
1 arr[i] 1000解题
先计算前缀和再枚举子数组开始位置和奇数长度时间复杂度 O(n2)O(n^2)O(n2)
class Solution {
public:int sumOddLengthSubarrays(vectorint arr) {int n arr.size(), sum 0;for(int i 1; i n; i) {arr[i] arr[i-1] arr[i];}for(int i 0; i n; i){for(int len 1; len n; len2){int j ilen-1;if(j n)break;sum arr[j]- (i 0 ? arr[i-1] : 0);}}return sum;}
};4 ms 8 MB
参考大佬的思路对每个数字考虑前后的奇偶数字的长度有多少种前后同奇同偶的方案数相乘时间复杂度 O(n)O(n)O(n)
class Solution {
public:int sumOddLengthSubarrays(vectorint arr) {int n arr.size(), sum 0;int L_odd, L_even, R_odd, R_even, L, R;for(int i 0; i n; i){//对每个数字进行考察 1个数字//它的左边右边有的数字个数必须是同奇同偶//这样子数组才会是奇数个长度//有多少种组合L_odd (i1)/2;//奇数有这么多种选择L_even i/2;R_odd (n-i)/2;R_even (n-i-1)/2;sum (L_odd*R_odd (L_even1)*(R_even1))*arr[i];// 1 为前后偶数个数为0的情况}return sum;}
};0 ms 8.1 MB
2. LeetCode 5505. 所有排列中的最大和 medium
题目链接
有一个整数数组 nums 和一个查询数组 requests 其中 requests[i] [starti, endi] 。第 i 个查询求 nums[starti] nums[starti 1] ... nums[endi - 1] nums[endi] 的结果 starti 和 endi 数组索引都是 从 0 开始 的。
你可以任意排列 nums 中的数字请你返回所有查询结果之和的最大值。
由于答案可能会很大请你将它对 10^9 7 取余 后返回。
示例 1
输入nums [1,2,3,4,5], requests [[1,3],[0,1]]
输出19
解释一个可行的 nums 排列为 [2,1,3,4,5]并有如下结果
requests[0] - nums[1] nums[2] nums[3] 1 3 4 8
requests[1] - nums[0] nums[1] 2 1 3
总和为8 3 11。
一个总和更大的排列为 [3,5,4,2,1]并有如下结果
requests[0] - nums[1] nums[2] nums[3] 5 4 2 11
requests[1] - nums[0] nums[1] 3 5 8
总和为 11 8 19这个方案是所有排列中查询之和最大的结果。示例 2
输入nums [1,2,3,4,5,6], requests [[0,1]]
输出11
解释一个总和最大的排列为 [6,5,4,3,2,1] 查询和为 [11]。示例 3
输入nums [1,2,3,4,5,10], requests [[0,2],[1,3],[1,1]]
输出47
解释一个和最大的排列为 [4,10,5,3,2,1] 查询结果分别为 [19,18,10]。提示
n nums.length
1 n 105
0 nums[i] 105
1 requests.length 105
requests[i].length 2
0 starti endi n解题
计算频数频数大的乘以大数这样总和才能最大频数计算要采用差分方法模拟会超时 类似题目 LeetCode 1109. 航班预订统计差分思想时间复杂度为排序的复杂度 O(nlogn)O(n\log n)O(nlogn)
class Solution {
public:int maxSumRangeQuery(vectorint nums, vectorvectorint requests) {int n nums.size();vectorlong long f(n1, 0);for(auto re : requests){f[re[0]];f[re[1]1]--;}for(int i 1; i n; i){f[i] f[i-1];}sort(f.rbegin(), f.rend());sort(nums.rbegin(), nums.rend());long long sum 0, mod 1e97;for(int i 0; i n; i){sum (sumf[i]*nums[i])%mod;}return sum;}
};1240 ms 95.9 MB
3. LeetCode 5504. 使数组和能被 P 整除 medium
题目链接
给你一个正整数数组 nums请你移除 最短 子数组可以为 空使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。
请你返回你需要移除的最短子数组如果无法满足题目要求返回 -1 。
子数组 定义为原数组中连续的一组元素。
示例 1
输入nums [3,1,4,2], p 6
输出1
解释nums 中元素和为 10不能被 p 整除。
我们可以移除子数组 [4] 剩余元素的和为 6 。示例 2
输入nums [6,3,5,2], p 9
输出2
解释我们无法移除任何一个元素使得和被 9 整除
最优方案是移除子数组 [5,2] 剩余元素为 [6,3]和为 9 。示例 3
输入nums [1,2,3], p 3
输出0
解释和恰好为 6 已经能被 3 整除了。
所以我们不需要移除任何元素。示例 4
输入nums [1,2,3], p 7
输出-1
解释没有任何方案使得移除子数组后剩余元素的和被 7 整除。示例 5
输入nums [1000000000,1000000000,1000000000], p 3
输出0提示
1 nums.length 10^5
1 nums[i] 10^9
1 p 10^9解题
哈希记录最近的 前缀和求模后的时间复杂度 O(n)O(n)O(n) 类似题目LeetCode 930. 和相同的二元子数组哈希前缀和
class Solution {
public:int minSubarray(vectorint nums, int p) {long long mod 0, sum 0;for(int i 0; i nums.size(); i){mod (mod nums[i])%p;sum nums[i];}if(mod 0)//余数为0不需要操作return 0;if(sum p)//和小于p, 做不到return -1;int s 0, minlen INT_MAX;// s 是求模后的和unordered_mapint, int m;//记录和求模后的数及其位置m[0] -1;//初始条件0 在 -1 位置for(int i 0; i nums.size(); i){s (s nums[i])%p;int target (s-modp)%p;//检查跟 s 相差 需要的余数mod 的余数存在吗if(m.find(target) ! m.end()){minlen min(minlen, i-m[target]);}m[s] i;//更新位置}return minlen nums.size() ? -1 : minlen;}
};420 ms 65.4 MB
4. LeetCode 5506. 奇怪的打印机 II hard
题目链接
给你一个奇怪的打印机它有如下两个特殊的打印规则
每一次操作时打印机会用同一种颜色打印一个矩形的形状每次打印会覆盖矩形对应格子里原本的颜色。一旦矩形根据上面的规则使用了一种颜色那么 相同的颜色不能再被使用 。
给你一个初始没有颜色的 m x n 的矩形 targetGrid 其中 targetGrid[row][col] 是位置 (row, col) 的颜色。
如果你能按照上述规则打印出矩形 targetGrid 请你返回 true 否则返回 false 。
示例 1
输入targetGrid [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]
输出true示例 2
输入targetGrid [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]]
输出true示例 3
输入targetGrid [[1,2,1],[2,1,2],[1,2,1]]
输出false
解释没有办法得到 targetGrid 因为每一轮操作使用的颜色互不相同。示例 4
输入targetGrid [[1,1,1],[3,1,3]]
输出false提示
m targetGrid.length
n targetGrid[i].length
1 m, n 60
1 targetGrid[row][col] 60解题
待学习。 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
