5. 1749.任意子數組和的絕對值的最大值(中等,學習)
1749. 任意子數組和的絕對值的最大值 - 力扣（LeetCode）
思想
1.給你一個整數數組 nums 。一個子數組 [numsl, numsl+1, ..., numsr-1, numsr] 的 和的絕對值 為 abs(numsl + numsl+1 + ... + numsr-1 + numsr) 。
請你找出 nums 中 和的絕對值 最大的任意子數組（可能為空），并返回該 最大值 。
abs(x) 定義如下：
- 如果
x是負整數，那么abs(x) = -x。 - 如果
x是非負整數，那么abs(x) = x。
2.此題**abs(numsl + numsl+1 + ... + numsr-1 + numsr)轉化為abs(s[r+1]-s[l])的最大值，即一個s數組，選取兩個元素，讓他們兩個差的絕對值最大，所以為s數組的最大值mx減去s數組的最小值mn**,因為子數組可能為空(即s[0]=0),所以mx,mn初始化為0
3.此題轉化的含義為: - 變成一條曲線，表示和的累計值，然后mx,mn就是最大值點和最小值點，他們直接的區間就是這個子數組和的累計值，表示他們的變化量最大(絕對值)
- mx的坐標>mn的坐標,表示正的和的最大值
- mx的坐標<mn的坐標,表示負的和的最小值，絕對值變成最大值
代碼
c++:
class Solution {
public:int maxAbsoluteSum(vector<int>& nums) {int n = nums.size();int s = 0, mx = 0,mn = 0; // s[0]=0,所以mx,mn初始值為0,因為子數組可能為空for (int i = 0; i < n; ++i) {s += nums[i];mx = max(mx, s);mn = min(mn, s);}return mx - mn;}
};
6. 2389.和有限的最長子序列(簡單，想到二分查找優化)
2389. 和有限的最長子序列 - 力扣（LeetCode）
思想
1.給你一個長度為 n 的整數數組 nums ，和一個長度為 m 的整數數組 queries 。
返回一個長度為 m 的數組 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 長度 。
子序列 是由一個數組刪除某些元素（也可以不刪除）但不改變剩余元素順序得到的一個數組。
2.因為是子序列，所以是任意選取的，不要求連續，只要找到一個子序列能夠滿足條件就可以更新長度，所以貪心思想元素越小越好，所以先對nums數組排序，然后求得前綴和s數組，接下來就是尋找最后一個滿足s[tmp]<=queries[i]的下標tmp，因為s數組是有序的，所以可以將順序查找優化為二分查找,因為s[tmp]對應nums[0...tmp-1]數組和，長度就為tmp
代碼
c++:
class Solution {
public:vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {int n = nums.size(), m = queries.size();sort(nums.begin(), nums.end());vector<int> s(n + 1);s[0] = 0;for (int i = 0; i < n; ++i) {s[i + 1] = s[i] + nums[i];}vector<int> res;for (int i = 0; i < m; ++i) {int j = 0;while (j + 1 < n + 1 && s[j + 1] <= queries[i])++j;res.emplace_back(j);}return res;}
};
二分優化:
class Solution {
public:vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {int n = nums.size(), m = queries.size();sort(nums.begin(), nums.end());vector<int> s(n + 1);s[0] = 0;for (int i = 0; i < n; ++i) {s[i + 1] = s[i] + nums[i];}vector<int> res;for (int i = 0; i < m; ++i) {int left = 0, right = n, tmp = 0;while (left <= right) {int mid = left + ((right - left) >> 1);// 找到滿足條件的，更新答案，找更大的if (s[mid] <= queries[i]) {tmp = mid;left = mid + 1;} elseright = mid - 1;}// s[tmp]:nums[0...tmp-1]長度為tmpres.emplace_back(tmp);}return res;}
};
7. 3361.兩個字符串的切換距離(中等,學習環形延長一倍變成非環形)
3361. 兩個字符串的切換距離 - 力扣（LeetCode）
思想
1.給你兩個長度相同的字符串 s 和 t ，以及兩個整數數組 nextCost 和 previousCost 。
一次操作中，你可以選擇 s 中的一個下標 i ，執行以下操作 之一 ：
- 將
s[i]切換為字母表中的下一個字母，如果s[i] == 'z'，切換后得到'a'。操作的代價為nextCost[j]，其中j表示s[i]在字母表中的下標。 - 將
s[i]切換為字母表中的上一個字母，如果s[i] == 'a'，切換后得到'z'。操作的代價為previousCost[j]，其中j是s[i]在字母表中的下標。
切換距離 指的是將字符串s變為字符串t的 最少 操作代價總和。
請你返回從s到t的 切換距離 。
2.就是提前計算出nextCost和previousCost的前綴和數組，然后分類討論考慮時要考慮清楚區間范圍是什么，然后決定前綴和數組的下標
3.字母表是環形的，可以把前綴和數組延長一倍，可以大大簡化討論
代碼
c++:
class Solution {
public:long long shiftDistance(string s, string t, vector<int>& nextCost,vector<int>& previousCost) {long long res = 0;int n = s.size();vector<long long> sNext(27);vector<long long> sPre(27);sNext[0] = 0;sPre[0] = 0;for (int i = 0; i < 26; ++i) {sNext[i + 1] = sNext[i] + nextCost[i];sPre[i + 1] = sPre[i] + previousCost[i];}for (int i = 0; i < n; ++i) {int ids = s[i] - 'a', idt = t[i] - 'a';long long mn = 0;if (ids < idt) {// 向后:nextCost[ids...idt-1],向前排除:preCost[ids+1...idt]mn = min(sNext[idt] - sNext[ids],sPre[26] - (sPre[idt + 1] - sPre[ids + 1]));}// 向前:PreCost[idt+1..ids],向后排除:nextCost[idt...ids-1]elsemn = min(sPre[ids + 1] - sPre[idt + 1],sNext[26] - (sNext[ids] - sNext[idt]));res += mn;}return res;}
};
延長一倍優化循環數組:
class Solution {
public:long long shiftDistance(string s, string t, vector<int>& nextCost,vector<int>& previousCost) {long long res = 0;int n = s.size();const int SIGMA = 26;vector<long long> sNext(2 * SIGMA + 1, 0);vector<long long> sPre(2 * SIGMA + 1, 0);sNext[0] = 0;sPre[0] = 0;for (int i = 0; i < 2 * SIGMA; ++i) {sNext[i + 1] = sNext[i] + nextCost[i % SIGMA];sPre[i + 1] = sPre[i] + previousCost[i % SIGMA];}for (int i = 0; i < n; ++i) {int x = s[i] - 'a', y = t[i] - 'a';// 向后是ids->idt-1,所以s數組是ids->idt,向前是idt+1->ids,所以s數組是idt+1->ids+1// sNext只有y<x時，y才加；sPre只有x<y時，x才加res += min(sNext[y < x ? y + SIGMA : y] - sNext[x],sPre[(x < y ? x + SIGMA : x) + 1] - sPre[y + 1]);}return res;}
};
