如何建立个人免费网站,店面设计薪酬,建材做哪些网站,电子商务网站推广案例2. 2441.与对应负数同时存在的最大正整数(简单)
2441. 与对应负数同时存在的最大正整数 - 力扣#xff08;LeetCode#xff09;
思想
1.给你一个 不包含 任何零的整数数组 nums #xff0c;找出自身与对应的负数都在数组中存在的最大正整数 k 。 返回正整数 k #xff0…2. 2441.与对应负数同时存在的最大正整数(简单)
2441. 与对应负数同时存在的最大正整数 - 力扣LeetCode
思想
1.给你一个 不包含 任何零的整数数组 nums 找出自身与对应的负数都在数组中存在的最大正整数 k 。 返回正整数 k 如果不存在这样的整数返回 -1 。 2.满足条件 a j − a i a_j-a_i aj−ai,相当于两数之和等于0
代码
c:
class Solution {
public:int findMaxK(vectorint nums) {int n nums.size(), res -1;unordered_mapint, 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 a_ia_j aiaj,但哈希表的值为 n u m s [ i ] nums[i] nums[i]的数量这样res更新加上当前 n u m s [ j ] nums[j] nums[j]形成的所有数对
代码
c:
class Solution {
public:int numIdenticalPairs(vectorint nums) {int n nums.size(), res 0;unordered_mapint, 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 和 ji j的宽高比相同则认为这两个矩形 可互换 。更规范的说法是两个矩形满足 widthi/heighti widthj/heightj使用实数除法而非整数除法则认为这两个矩形 可互换 。 计算并返回 rectangles 中有多少对 可互换 矩形。 2.满足条件i和j的宽高比相同可以跟3. 1512.好数对的数目一样的做法只不过键为double类型但是数据再大就会出错要用map储存(unordered_map不行) 最简分数的分子和分母(pairint,int)
代码
c:
class Solution {
public:long long interchangeableRectangles(vectorvectorint rectangles) {int n rectangles.size();long long res 0;unordered_mapdouble, 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(vectorvectorint rectangles) {int n rectangles.size();long long res 0;mappairint, 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]是等价的所以人为的让ab,通过交换实现即可
代码
c:
class Solution {
public:int numEquivDominoPairs(vectorvectorint dominoes) {int n dominoes.size(), res 0;mappairint, 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.对应当前的 p r i c e s [ j ] prices[j] prices[j],要找到它左边的最小值所以可以枚举右侧卖出价格维护左侧最小买入价格(一个变量即可)
代码
c:
class Solution {
public:int maxProfit(vectorint 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,即长度小于等于k1,所以就取极限长度k1,所以可以用定长滑动窗口做
代码
c:
class Solution {
public:bool containsNearbyDuplicate(vectorint nums, int k) {int n nums.size();mapint, 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(vectorint nums, int k) {int n nums.size();mapint, int mp;for (int j 0; j n; j) {mp[nums[j]];if (mp[nums[j]] 1)return true;// 长度为k1if (j k - 1 1)--mp[nums[j - (k1) 1]];}return false;}
};8. 2260.必须拿起的最小连续卡牌数(中等)
思想
1.给你一个整数数组 cards 其中 cards[i] 表示第 i 张卡牌的 值 。如果两张卡牌的值相同则认为这一对卡牌 匹配 。 返回你必须拿起的最小连续卡牌数以使在拿起的卡牌中有一对匹配的卡牌。如果无法得到一对匹配的卡牌返回 -1 。 2.如果两张卡牌的值相同则认为这一对卡牌 匹配“即满足条件 a i a j a_ia_j aiaj,可以枚举右维护左 3.最小连续卡牌数说明可以用不定长滑动窗口的最短/最小做
代码
c: 枚举右维护左:
class Solution {
public:int minimumCardPickup(vectorint cards) {int n cards.size();mapint, 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(vectorint cards) {int n cards.size();mapint, 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;}
};
