文章目錄
- 1. 比賽結果
- 2. 題目
- 1. LeetCode 5503. 所有奇數長度子陣列的和 easy
- 2. LeetCode 5505. 所有排列中的最大和 medium
- 3. LeetCode 5504. 使陣列和能被 P 整除 medium
- 4. LeetCode 5506. 奇怪的列印機 II hard
1. 比賽結果
做出來3題，繼續加油！
全國排名： 216 / 2839，7.61%；全球排名： 585 / 8750，6.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 ( n 2 ) O(n^2) O(n2)
class Solution {
public:
int sumOddLengthSubarrays(vector<int>& 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; len+=2)
{
int j = i+len-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(vector<int>& 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 = (i+1)/2;//奇數有這么多種選擇
L_even = i/2;
R_odd = (n-i)/2;
R_even = (n-i-1)/2;
sum += (L_odd*R_odd + (L_even+1)*(R_even+1))*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 ( n log ? n ) O(n\log n) O(nlogn)
class Solution {
public:
int maxSumRangeQuery(vector<int>& nums, vector<vector<int>>& requests) {
int n = nums.size();
vector<long long> f(n+1, 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 = 1e9+7;
for(int i = 0; i < n; i++)
{
sum = (sum+f[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(vector<int>& 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_map<int, int> m;//記錄和求模后的數，及其位置
m[0] = -1;//初始條件，0 在 -1 位置
for(int i = 0; i < nums.size(); i++)
{
s = (s + nums[i])%p;
int target = (s-mod+p)%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阿明），一起加油、一起學習進步！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/99721.html
標籤：其他
上一篇：微信小程式求帶
下一篇：不好！我中了美人計！