14. 624.数组列表中的最大距离(中等）
624. 数组列表中的最大距离 - 力扣（LeetCode）
思想
1.给定 m 个数组，每个数组都已经按照升序排好序了。
现在你需要从两个不同的数组中选择两个整数（每个数组选一个）并且计算它们的距离。两个整数 a 和 b 之间的距离定义为它们差的绝对值 |a-b| 。
返回最大距离。
2.对于当前遍历的数组j，需要知道之前所有数组的最小值和最大值，所以就是维护这个最小值和最大值即可,然后枚举当前遍历数组j
代码
c++:
class Solution {
public:
int maxDistance(vector<vector<int>>& arrays) {
int n = arrays.size(), minval = arrays[0][0],
maxval = arrays[0][arrays[0].size() - 1], res = INT_MIN;
// 可以写arrays[0].back()
for (int j = 1; j < n; ++j) {
int m = arrays[j].size();
// 可以写arrays[j].back()
res = max({res, abs(arrays[j][m - 1] - minval),
abs(maxval - arrays[j][0])});
minval = min(minval, arrays[j][0]);
maxval = max(maxval, arrays[j][m - 1]);
}
return res;
}
};
15. 2364.统计坏数对的数目(中等)
思想
1.给你一个下标从 0 开始的整数数组 nums 。如果 i < j 且 j - i != nums[j] - nums[i] ，那么我们称 (i, j) 是一个 坏数对 。
请你返回 nums 中 坏数对 的总数目。
2.我的思想:观察到j-i!=nums[j]-nums[i]不好判断，而j-i==nums[j]-nums[i]可以化成nums[j]-j==nums[i]-i具有同一种形式，所以可以统计nums[i]-i的次数,如果有次数大于2的则说明不满足条件，需要减去，假设次数大于2的数为m1,m2…,所以最终答案就是 C n 2 − C m 1 2 − C m 2 2 − . . . C_n^2-C_{m1}^2-C_{m2}^2-... Cn2−Cm12−Cm22−...
3.但是我的写法是先map遍历nums统计，再遍历map更新答案，可以直接用枚举右维护左的思路，维护nums[i]-i的数对个数，类似于3. 1512.好数对的数目
代码
c++:
class Solution {
public:
long long f(int a) { return 1LL * a * (a - 1) / 2; }
long long countBadPairs(vector<int>& nums) {
int n = nums.size();
long long res = f(n);
map<int, int> mp; // (nums[i]-i)-次数
for (int i = 0; i < n; ++i) {
++mp[nums[i] - i];
}
for (auto t : mp) {
if (t.second > 1)
res -= f(t.second);
}
return res;
}
};
枚举右维护左优化:
class Solution {
public:
long long countBadPairs(vector<int>& nums) {
int n = nums.size();
long long res = 1LL * n * (n - 1) / 2;
map<int, int> mp; // (nums[i]-i)-次数
for (int j = 0; j < n; ++j) {
res -= mp[nums[j] - j]++;
}
return res;
}
};
16. 1014.最佳观光组合(中等)
思想
1.给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。
一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。
返回一对观光景点能取得的最高分。
2.可以把values[i] + values[j] + i - j 变成values[j]-j和values[i]+i两个部分，对于枚举j，得到的values[j]-j一定，所以只需维护values[i]+i为最大值即可
代码
c++:
class Solution {
public:
int maxScoreSightseeingPair(vector<int>& values) {
int n = values.size();
int maxval = values[0] + 0, res = INT_MIN;
for (int j = 1; j < n; ++j) {
res = max(res, maxval + values[j] - j);
maxval = max(maxval, values[j] + j);
}
return res;
}
};
17. 1814.统计一个数组中好对子的数目(中等,学习反转数字)
1814. 统计一个数组中好对子的数目 - 力扣（LeetCode）
思想
1.给你一个数组 nums ，数组中只包含非负整数。定义 rev(x) 的值为将整数 x 各个数字位反转得到的结果。比方说 rev(123) = 321 ， rev(120) = 21 。我们称满足下面条件的下标对 (i, j) 是 好的 ：
0 <= i < j < nums.lengthnums[i] + rev(nums[j]) == nums[j] + rev(nums[i])
请你返回好下标对的数目。由于结果可能会很大，请将结果对109 + 7取余 后返回。
2.跟3. 1512.好数对的数目类似，只不过这题计算rev(nums[i])复杂一点,学习一下简单的反转数字写法
代码
c++:
class Solution {
public:
int mod = 1e9 + 7;
long long rev(int x) {
stack<int> st;
while (x) {
st.push(x % 10);
x /= 10;
}
long long res = 0, pow = 1;
while (!st.empty()) {
int t = st.top();
st.pop();
res += t * pow;
pow *= 10;
}
return res;
}
int countNicePairs(vector<int>& nums) {
int n = nums.size(), res = 0;
map<long long, long long> mp;
for (int i = 0; i < n; ++i) {
res = (res + mp[1LL * nums[i] - rev(nums[i])]++) % mod;
}
return res % mod;
}
};
优化rev函数:
int rev(int x) {
int res = 0;
while (x) {
res = res * 10 + x % 10;
x /= 10;
}
return res;
}
18. 2905.找出满足差值条件的下标II(中等,学习)
2905. 找出满足差值条件的下标 II - 力扣（LeetCode）
思想
1.给你一个下标从 0 开始、长度为 n 的整数数组 nums ，以及整数 indexDifference 和整数 valueDifference 。
你的任务是从范围 [0, n - 1] 内找出 2 个满足下述所有条件的下标 i 和 j ：
abs(i - j) >= indexDifference且abs(nums[i] - nums[j]) >= valueDifference
返回整数数组answer。如果存在满足题目要求的两个下标，则answer = [i, j]；否则，answer = [-1, -1]。如果存在多组可供选择的下标对，只需要返回其中任意一组即可。
注意：i和j可能 相等 。
2.根据条件"abs(i - j) >= indexDifference",不妨设i<j,所以得到i<=j-indexDifference,从而枚举j，寻找左边的i，满足abs(nums[i] - nums[j]) >= valueDifference，所以要让nums[i]尽可能大或者尽可能小，所以要维护nums[0]-nums[j-indexDifference]的最大值下标maxIdx和最小值下标minIdx,从而得到最大值mx和最小值mn,且mx>=mn得到abs(mx-nums[j])>=valueDifference- 若
mx>=nums[j],则mx-nums[j]>=valueDifference - 若
mx<nums[j],则nums[j]-mn>=nums[j]-mx>=valueDifference
- 若
abs(mn-nums[j])>=valueDifference- 若
mn>=nums[j],则mx-nums[j]>=mn-nums[j]>=valueDifference - 若
mn<nums[j],则nums[j]-mn>=valueDifference
- 若
- 所以综上，
mx-nums[j]>=valueDifference和nums[j]-mn>=valueDifference二者满足其一即可
代码
c++:
class Solution {
public:
vector<int> findIndices(vector<int>& nums, int indexDifference,
int valueDifference) {
int n = nums.size();
int minIdx = 0, maxIdx = 0;
for (int j = indexDifference; j < n; ++j) {
int i = j - indexDifference;
if (nums[i] < nums[minIdx])
minIdx = i;
if (nums[i] > nums[maxIdx])
maxIdx = i;
if (nums[maxIdx] - nums[j] >= valueDifference)
return {maxIdx, j};
if (nums[j] - nums[minIdx] >= valueDifference)
return {minIdx, j};
}
return {-1, -1};
}
};
19. 3584.子序列首尾元素的最大乘积(中等)
3584. 子序列首尾元素的最大乘积 - 力扣（LeetCode）
思想
1.给你一个整数数组 nums 和一个整数 m。
返回任意大小为 m 的 子序列 中首尾元素乘积的最大值。
子序列 是可以通过删除原数组中的一些元素（或不删除任何元素），且不改变剩余元素顺序而得到的数组。
2.跟18. 2905.找出满足差值条件的下标II很像，此题可以转化为j-i>=m条件下找nums[j]nums[i]的最大值,所以可以枚举j，为了保证区间长度大于等于m,所以i=j-m+1,所以维护nums[0]-nums[j-m+1]的最小值下标和最大值下标(因为nums[j]正负未知),为了让i从0开始，j从m-1开始即可
代码
c++:
class Solution {
public:
long long maximumProduct(vector<int>& nums, int m) {
int n = nums.size();
long long res = LONG_MIN; // LONG_MIN,而不是INT_MIN
int maxIdx = 0, minIdx = 0;
// [i,j]长度>=m,即j-i+1>=m,i从0开始,j从m-1开始
for (int j = m - 1; j < n; ++j) {
int i = j + 1 - m;
if (nums[i] < nums[minIdx])
minIdx = i;
if (nums[i] > nums[maxIdx])
maxIdx = i;
res = max({res, 1LL * nums[j] * nums[minIdx],
1LL * nums[j] * nums[maxIdx]});
}
return res;
}
};