每日算法刷题Day34 6.17:leetcode枚举技巧6道题，用时2h

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.统计坏数对的数目(中等)

2364. 统计坏数对的数目 - 力扣（LeetCode）

思想

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_{m1}^2-C_{m2}^2-...$
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.最佳观光组合(中等)

1014. 最佳观光组合 - 力扣（LeetCode）

思想

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.length
• nums[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_MINint 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;}
};