每日算法刷题Day32 6.15:leetcode枚举技巧7道题，用时1h10min

2. 2441.与对应负数同时存在的最大正整数(简单)

2441. 与对应负数同时存在的最大正整数 - 力扣（LeetCode）

思想

1.给你一个 不包含 任何零的整数数组 nums ，找出自身与对应的负数都在数组中存在的最大正整数 k 。
返回正整数 k ，如果不存在这样的整数，返回 -1 。
2.满足条件$a_j=-a_i$,相当于两数之和等于0

代码

c++:

class Solution {
public:int findMaxK(vector<int>& nums) {int n = nums.size(), res = -1;unordered_map<int, int> mp;for (int j = 0; j < n; ++j) {auto it = mp.find(-nums[j]);if (it != mp.end()) {res = max(res, abs(nums[j]));}mp[nums[j]] = j;}return res;}
};

3. 1512.好数对的数目(简单)

1512. 好数对的数目 - 力扣（LeetCode）

思想

1.给你一个整数数组 nums 。
如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。
返回好数对的数目。
2.满足条件$a_i=a_j$,但哈希表的值为$nums[i]$的数量，这样res更新加上当前$nums[j]$形成的所有数对

代码

c++:

class Solution {
public:int numIdenticalPairs(vector<int>& nums) {int n = nums.size(), res = 0;unordered_map<int, int> mp;for (int j = 0; j < n; ++j) {auto it = mp.find(nums[j]);if (it != mp.end())res += mp[nums[j]];++mp[nums[j]];}return res;}
};

4. 2001.可互换矩形的组数(中等,学习最简分数)

思想

1.用一个下标从 0 开始的二维整数数组 rectangles 来表示 n 个矩形，其中 rectangles[i] = [widthi, heighti] 表示第 i 个矩形的宽度和高度。
如果两个矩形 i 和 j（i < j）的宽高比相同，则认为这两个矩形 可互换 。更规范的说法是，两个矩形满足 widthi/heighti == widthj/heightj（使用实数除法而非整数除法），则认为这两个矩形 可互换 。
计算并返回 rectangles 中有多少对 可互换 矩形。
2.满足条件i和j的宽高比相同，可以跟3. 1512.好数对的数目一样的做法，只不过键为double类型，但是数据再大就会出错，要用map储存(unordered_map不行) 最简分数的分子和分母(pair<int,int>)

代码

c++:

class Solution {
public:long long interchangeableRectangles(vector<vector<int>>& rectangles) {int n = rectangles.size();long long res = 0;unordered_map<double, int> mp;for (int j = 0; j < n; ++j) {res += mp[1.0 * rectangles[j][0] / rectangles[j][1]]++;}return res;}
};

学习:

class Solution {
public:int gcd(int a, int b) {if (b == 0)return a;return gcd(b, a % b);}long long interchangeableRectangles(vector<vector<int>>& rectangles) {int n = rectangles.size();long long res = 0;map<pair<int, int>, int> mp;for (int j = 0; j < n; ++j) {int w = rectangles[j][0], h = rectangles[j][1];int yue = gcd(w, h);res += mp[{w / yue, h / yue}]++;}return res;}
};

5. 1128.等价多米诺骨牌对的数量(简单)

1128. 等价多米诺骨牌对的数量 - 力扣（LeetCode）

思想

1.给你一组多米诺骨牌 dominoes 。
形式上，dominoes[i] = [a, b] 与 dominoes[j] = [c, d] 等价 当且仅当 (a == c 且 b == d) 或者 (a == d 且 b == c) 。即一张骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌。
在 0 <= i < j < dominoes.length 的前提下，找出满足 dominoes[i] 和 dominoes[j] 等价的骨牌对 (i, j) 的数量。
2.跟3. 1512.好数对的数目类似，但是本题[a,b]和[b,a]是等价的，所以人为的让a<=b,通过交换实现即可

代码

c++:

class Solution {
public:int numEquivDominoPairs(vector<vector<int>>& dominoes) {int n = dominoes.size(), res = 0;map<pair<int, int>, int> mp;for (int j = 0; j < n; ++j) {int c = dominoes[j][0], d = dominoes[j][1];if (c < d)swap(c, d);res += mp[{c, d}]++;}return res;}
};

6. 121.买卖股票的最佳时机(简单)

121. 买卖股票的最佳时机 - 力扣（LeetCode）

思想

1.给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
2.对应当前的$prices[j]$,要找到它左边的最小值，所以可以枚举右侧卖出价格，维护左侧最小买入价格(一个变量即可)

代码

c++:

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size(), res = 0, minval = prices[0];for (int i = 0; i < n; ++i) {if (prices[i] > minval)res = max(res, prices[i] - minval);elseminval = min(minval, prices[i]);}return res;}
};

7. 219.存在重复元素II(简单)

219. 存在重复元素 II - 力扣（LeetCode）

思想

1.给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
2.满足条件nums[i] == nums[j] 且 abs(i - j) <= k(即左右存在关系),即可枚举右，维护左
3.因为有个条件abs(i - j) <= k,即长度小于等于k+1,所以就取极限长度k+1,所以可以用定长滑动窗口做

代码

c++:

class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {int n = nums.size();map<int, int> mp;for (int j = 0; j < n; ++j) {auto it = mp.find(nums[j]);if (it != mp.end() && j - it->second <= k)return true;mp[nums[j]] = j;}return false;}
};

定长滑动窗口:

class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {int n = nums.size();map<int, int> mp;for (int j = 0; j < n; ++j) {++mp[nums[j]];if (mp[nums[j]] > 1)return true;// 长度为k+1if (j >= k - 1 + 1)--mp[nums[j - (k+1) + 1]];}return false;}
};

8. 2260.必须拿起的最小连续卡牌数(中等)

思想

1.给你一个整数数组 cards ，其中 cards[i] 表示第 i 张卡牌的 值 。如果两张卡牌的值相同，则认为这一对卡牌 匹配 。
返回你必须拿起的最小连续卡牌数，以使在拿起的卡牌中有一对匹配的卡牌。如果无法得到一对匹配的卡牌，返回 -1 。
2."如果两张卡牌的值相同，则认为这一对卡牌 匹配“，即满足条件$a_i=a_j$,可以枚举右维护左
3."最小连续卡牌数"说明可以用不定长滑动窗口的最短/最小做

代码

c++:
枚举右，维护左:

class Solution {
public:int minimumCardPickup(vector<int>& cards) {int n = cards.size();map<int, int> mp;int res = INT_MAX;for (int j = 0; j < n; ++j) {auto it = mp.find(cards[j]);if (it != mp.end())res = min(res, j - it->second + 1);mp[cards[j]] = j;}if (res == INT_MAX)return -1;elsereturn res;}
};

不定长滑动窗口求最短/最小:

class Solution {
public:int minimumCardPickup(vector<int>& cards) {int n = cards.size();map<int, int> mp;int res = INT_MAX;int left = 0;for (int right = 0; right < n; ++right) {++mp[cards[right]];while (left <= right && mp[cards[right]] > 1) {res = min(res, right - left + 1);--mp[cards[left]];++left;}}if (res == INT_MAX)return -1;elsereturn res;}
};