每日算法刷题Day38 6.25:leetcode前缀和3道题，用时1h40min
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;}
};