制造网站的软件,弹窗视频网站,分类门户网站开发团队,有意义网站#x1f525;博客主页#xff1a; A_SHOWY#x1f3a5;系列专栏#xff1a;力扣刷题总结录 数据结构 云计算 数字图像处理 力扣每日一题_
【1.4】2397.被列覆盖的最多行数
2397. 被列覆盖的最多行数https://leetcode.cn/problems/maximum-rows-covered-by-columns/ 这…博客主页 A_SHOWY系列专栏力扣刷题总结录 数据结构 云计算 数字图像处理 力扣每日一题_
【1.4】2397.被列覆盖的最多行数
2397. 被列覆盖的最多行数https://leetcode.cn/problems/maximum-rows-covered-by-columns/ 这个题目真的太巧妙了运用这种位运算来模拟这个数组然后将数组用位运算以后的二进制和存储然后用位运算设置limit给while循环1个数不够的还得continue了最后按位与整体结构都非常巧妙。 第一部分存储每一行的二进制表示位用一个数组把一个转为二进制存起来。 vectorint mask(m,0);//存储每一行的二进制表示位for(int i 0; i m; i){for(int j 0; j n; j){mask[i] matrix[i][j] (n - j -1);}} 在判断的时候用limit卡住界限维护列变换的区间 while((cur) limit){if(__builtin_popcount(cur) ! numSelect) {continue;} 用了一个内置函数关于一个二进制中1 的个数的函数还有0的个数的函数 __builtin_popcount(cur) //1的个数
__builtin_ctz(cur) //0的个数count trailing zero 最后把每一行遍历一遍与变换后的列的第一行按位与看看能不能覆盖这一行的所有1
class Solution {
public:int maximumRows(vectorvectorint matrix, int numSelect) {if(numSelect matrix[0].size()) return matrix.size();int m matrix.size();int n matrix[0].size();vectorint mask(m,0);//存储每一行的二进制表示位for(int i 0; i m; i){for(int j 0; j n; j){mask[i] matrix[i][j] (n - j -1);}}int res 0;//记录最大行数int cur 0;//最大列数int limit (1 n);while((cur) limit){if(__builtin_popcount(cur) ! numSelect) {continue;}int t 0;for(int j 0; j m; j){//遍历一遍按位与if((mask[j] cur) mask[j]){t;}}res max(res,t);}return res;}
}; 【1.14】83.删除排序链表中的重复元素
83. 删除排序链表中的重复元素https://leetcode.cn/problems/remove-duplicates-from-sorted-list/ 很久没有做到链表题目但是这道确实简单只需要注意一下while循环中除了cur非空还要兼顾cur - next非空。重复时就让指针指向next - next class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {ListNode* cur head;while(cur ! NULL cur -next ! NULL){if(cur - val cur - next - val) {cur - next cur - next - next;}else cur cur - next;}return head;}
};
【1.15】82.删除排序链表中的重复Ⅱ
82. 删除排序链表中的重复元素 IIhttps://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/ 与83题删除排序链表中元素的主要区别为此题要求将出现过的重复元素的所有元素均删除例如1222将所有的2删除。需要引入头结点因为头部可能也会被删除统一操作。 class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {ListNode* dummyhead new ListNode(0); dummyhead - next head;ListNode* cur dummyhead; while(cur - next cur- next - next){if(cur - next- val cur - next - next - val){int x cur - next - val;while(cur - next cur - next - val x){//直到cur - next 为空节点或者cur - next 不为xcur - next cur - next - next;}}else cur cur - next;}head dummyhead - next;delete dummyhead;return head;}
}; 那么本题的总体思路也是比较简单先设置一个虚拟头结点dummyhead其具体步骤为 ListNode* dummyhead new ListNode(0); dummyhead - next head;ListNode* cur dummyhead;
如果节点的下一个等于其下一个的下一个就说明重复把重复的数字记下来统一删除。while中判定条件是删除直到cur的下一个是空节点或者粗人的下一个的值不是x。最后再删除头结点。
【1.17】2744.最大字符串配对数目
2744. 最大字符串配对数目https://leetcode.cn/problems/find-maximum-number-of-string-pairs/ 该题目如果暴力做二重循环思路比较简单但是也可以用哈希法解决。 法一暴力
class Solution {
public:int maximumNumberOfStringPairs(vectorstring words) {int ans 0;for(int i 0; i words.size();i){for(int j i 1; j words.size(); j){if(words[i][0] words[j][1] words[i][1] words[j][0]) ans;}}return ans;}
}; 法二哈希
1.set.count 表示统计元素出现的次数不为0
2.用哈希值来存题目限制是一个两位的字符串同时都是小写字母所以可以用第一位*100第二位作为哈希值来存两位互不影响。
class Solution {
public:int maximumNumberOfStringPairs(vectorstring words) {unordered_setint set;int ans 0;for(int i 0; i words.size(); i){if(set.count(words[i][1] * 100 words[i][0])) ans;set.insert(words[i][0] * 100 words[i][1]);}return ans;}
};
如果把后边两部反过来会出现一些问题先插入后判定那么比如cc、aa、bb这种重叠的字符串就会被多算一次产生错误 for(int i 0; i words.size(); i){set.insert(words[i][0] * 100 words[i][1]);if(set.count(words[i][1] * 100 words[i][0])) ans;}
【1.18】2171.拿出最少数目的魔法豆
2171. 拿出最少数目的魔法豆https://leetcode.cn/problems/removing-minimum-number-of-magic-beans/ 这道题目其实暴力做法非常容易但是不通过数据集太大了。如果想减少复杂度的话可以先排序分段进行处理也就是用排序前缀和来解决 方法一暴力不通过
class Solution {
public:long long minimumRemoval(vectorint beans) {vectorlong long res(beans.size(),0);for(int i 0; i beans.size(); i){for(int j 0; j beans.size(); j){if(beans[j] beans[i]){res[i] beans[j] - beans[i];}else{res[i] beans[j];}}}long long ans 9999999999;for(int i 0; i beans.size();i){if(res[i] ans){ans res[i];}}return ans;}
}; 暴力两个for直接不通过
方法二排序 前缀和
//排序 前缀和
class Solution {
public:long long minimumRemoval(vectorint beans) {sort(beans.begin(),beans.end());//前缀和vectorlong long sum(beans.size() 1,0);//让sum【0】 0for(int i 0; i beans.size(); i){sum[i 1] sum[i] beans[i];}long long res LLONG_MAX/2;int n beans.size();for(int i 0; i n; i){res min(res,sum[i] sum[n] - sum[i 1] - (n -1L -i) * beans[i]);}return res;}
};
先排序以后创建一个数组储存前缀和这时候要注意新数组的个数是size 1,然后循环迭代赋值。 在后边的时候设置res为LLONG_MAX/2,然后看图按照逻辑操作就行比i这个地方的值小的一律置为0比它大的置为beans【i】
【1.20】2788.按分隔符拆分字符串
2788. 按分隔符拆分字符串https://leetcode.cn/problems/split-strings-by-separator/ 该题目是一个比较简单的模拟题主要是积累getline函数的使用方法 1.getline(ss, sub, separator) 的作用是从 std::stringstream 对象 ss 中读取一行以 separator 为分隔符并将结果存储在字符串 sub 中。istream getline(istream is, string str, char delim);is: 输入流str: 存储读取的行的字符串。delim: 指定的分隔符getline 会根据这个分隔符进行拆分。
class Solution {
public:vectorstring splitWordsBySeparator(vectorstring words, char separator) {vectorstring res;for(string word : words){//遍历输入的字符串数组stringstream ss(word);//使用字符串流 stringstream 对每个字符串进行处理后边要用getlinestring str;while(getline(ss,str,separator)){if(!str.empty()) {res.push_back(str);}}}return res;}
};
2.记住在这里是引用的意思函数可以直接调用或者修改传递的字符串而不是对其副本进行操作增加效率。
【1.21】410.分割数组的最大值
410. 分割数组的最大值https://leetcode.cn/problems/split-array-largest-sum/
本题是一个hard题分析题目要求 最大值最小确定思路不是二分就是dp本题我们用二分求解。 先分析 每段和越小——》分出的段越多
假设我分了 一个段落和最大值为sum 对应的段落为——》k1k
代表着 段落分多了减少分的段就要每段和大一点。 所以小于等于sum那一部分就可以删掉了因为要减少段要每段和大一点
这里的k个可以理解为至多。
class Solution {public:int splitArray(vectorint nums, int k) {auto maxElement max_element(nums.begin(), nums.end());int l *maxElement;int sum 0;for(int i 0; i nums.size(); i){sum nums[i];}int r sum;while(l r){int mid l ((r-l) / 2);if(check(nums,mid,k)) r mid - 1;//如果能够分到k段sum给大了else l mid 1;}return l;//当最后lrmid指向同一个点的时候假如满足就是l假如不满足lmid 1所以最后返回l}bool check(vectorint nums, int m, int k){int cnt 1;//段数 int s 0;for(int i 0; i nums.size(); i){if(nums[i] s m) s nums[i];else{if(cnt k) return false;else s nums[i]; } }return true;}
};
这里面有很多值得注意的点第一个是设置l和r在设置r的时候就是最少的分段是一整个所以直接求和在左边的时候最多的分段就是每个一段所以直接找最大值最大值的时候用一个迭代器然后不要忘了求迭代器指向的具体值。
在二分法的时候到了lrmid三个指向同一个点时候考虑假如这时候满足了那么这三个点都能表示满足的最大值如果不满足那么l要mid1最后满足的还是l所以要返回l。
在check函数中注意先循环一手如果小于这个值就加进去s如果不满足先判断段落是不是够k了如果够了直接false否则新加一个cnt
【1.22】670.最大交换
670. 最大交换https://leetcode.cn/problems/maximum-swap/ 该题目主要考察灵活运用to_string 和stoi和swap函数进行一次遍历。看题解以后还有一种贪心的算法可以借鉴 方法一遍历
class Solution {
public:int maximumSwap(int num) {string stringNum to_string(num);//to_string转成字符串int maxnum num;int n stringNum.size();for(int i 0; i n; i){for(int j i 1; j n; j){swap(stringNum[i],stringNum[j]);maxnum max(maxnum , stoi(stringNum));//stoi字符串转成intswap(stringNum[i],stringNum[j]);}} return maxnum;}
};
先把给的num转化成string形式然后对字符串每一个字符进行两两交换取最大值在每一次循环中交换过了要记得交换回来。
方法二贪心
只要让靠近右边的最大的数的索引和左边的比这个数小的数的索引交换位置就能保证换完的数是一个最大。先遍历一遍找到最大的数然后从右到左看数字是否比这个最大的数大。
但是注意保证在求maxId时候尽量保证其靠近右侧。
class Solution {
public:int maximumSwap(int num) {string stringnum to_string(num);int n stringnum.size();int maxId n - 1;int idx1 -1;int idx2 -1;for(int i n - 1; i 0; i--){if(stringnum[i] stringnum[maxId]){maxId i; } else if (stringnum[i] stringnum[maxId]){idx1 i;idx2 maxId;}}if(idx1 0){swap(stringnum[idx1],stringnum[idx2]);return stoi(stringnum);}else return num;}
};
【1.23】2765.最长交替子数组
2765. 最长交替子数组https://leetcode.cn/problems/longest-alternating-subarray/ 这道题目第一思路就是双重循环类似于双指针让后边的指针指向的数减去前面的数根据奇数偶数分为0和1即可。看题解以后发现其实可以降低复杂度为on 方法一 双重循环
class Solution {
public:int alternatingSubarray(vectorint nums) {int res -1;for(int i 0; i nums.size(); i){for(int j i 1; j nums.size();j){int length j - i 1;if(nums[j] - nums[i] (length 1) % 2){res max(res,length);} else {break;}}}return res;}
}; 方法二 单重循环
考虑到当内层循环在第i个不满足条件时不需要从初始1外层循环继续开始因为如果从初始 1开始到第i个一定会断而且长度要比原来的要小。
所以可以直接从i1继续遍历但是要注意第i个断了以后要考虑假如第i个减第i-1个正好是1的时候需要给在新的数组中算上。
class Solution {
public:int alternatingSubarray(vectorint nums) {int res -1;int j 0;//前指针for(int i 1; i nums.size(); i){int length i -j 1;if(nums[i] - nums[j] (length 1) % 2){res max(res,length);} else {if(nums[i] - nums[i-1] 1){j i-1;res max(res,2); }else{j i;}}}return res;}
};
【1.24】2865.美丽塔
【1.24】2866.美丽塔Ⅱ
2865. 美丽塔 Ihttps://leetcode.cn/problems/beautiful-towers-i/ 本题可以直接暴力求解外层遍历让每一个值都当做峰值内层循环从中间向两边都递减。 同时补充了一道美丽塔Ⅱ 方法一暴力枚举
class Solution {
public:long long maximumSumOfHeights(vectorint maxHeights) {long long res 0;int n maxHeights.size();for(int i 0; i n; i){//外层分别设为峰顶int pre maxHeights[i];long long sum pre;for(int j i - 1 ;j 0; j--){pre min(pre,maxHeights[j]);sum pre;}int suf maxHeights[i];for(int j i 1; j n; j){suf min(suf,maxHeights[j]);sum suf;}res max(res,sum);}return res;}
}; 值得注意的点数据类型要匹配在函数种定义的maxheights 的值都是int类型在比较min的过程中要求两个数的定义都是int类型而函数返回的是long long所以定义的sum值是longlong类型。
整体思路是设置每一个值为峰值然后都向左向右递减用最小值。然后对sum求最大值即可。
补充题目2866.美丽塔22866. 美丽塔 IIhttps://leetcode.cn/problems/beautiful-towers-ii/ 题目一模一样唯一的区别就是数据量大不让用枚举了。
这时候就用到第二个方法单调栈。
方法二单调栈
由于题目要求一个峰值然后两边都是单调的而且两边逻辑一样所以我们可以考虑一边每一边都使用单调栈对单调栈的操作首先要进行一个while的pop因为我们要求栈内元素单调递增的当出现下边这种情况的时候为了迁就后边的元素前面的要弹出但是要注意我们栈里存储的是下标index弹出以后如果这个栈是空的就让i以前的数都等于maxHeights【i】即可如果有元素那么把以前的元素加着pre【top -1】让后边的都等于maxHeights【i】即可。最后别忘了把下标push进去。然后右边是同理的最后别忘了峰顶算了两次减去一次。 class Solution {//单调栈解法时间复杂度on
public:long long maximumSumOfHeights(vectorint maxHeights) {int n maxHeights.size();long long res 0;vectorlong longpre(n), suf(n);stackint stk1,stk2;//两个栈存放当前峰值左/右构造的最大值for(int i 0; i n; i){while(!stk1.empty() maxHeights[stk1.top()] maxHeights[i]){ stk1.pop();}if(stk1.empty()){pre[i] (long long )(i 1) * maxHeights[i];}else{pre[i] pre[stk1.top()] (long long )(i - stk1.top()) * maxHeights[i];}stk1.push(i);//把下标push进去}for(int i n -1; i 0; --i){while(!stk2.empty() maxHeights[stk2.top()] maxHeights[i]){stk2.pop();}if(stk2.empty()) {suf[i] (long long )(n - i) * maxHeights[i];}else{suf[i] suf[stk2.top()] ((long long)(stk2.top() - i)) * maxHeights[i];}stk2.push(i);res max(res,suf[i] pre[i] - maxHeights[i]);//maxHeights[i]算了两遍}return res;}
};
【1.25】2859.计算k置下标对应元素的和
2859. 计算 K 置位下标对应元素的和https://leetcode.cn/problems/sum-of-values-at-indices-with-k-set-bits/ 本题其实就是一个求二进制的简单题目大概率会想到用位运算解决 在c中表示的是按位与运算。当计算二进制中有多少个1的时候可以配合位元算
num (1 i);//统计每一位上有1的数
sum;//配合sum可以统计二进制中是1的位的个数 注意一点这个循环的大小因为是int类型最高就是32位直接小于32就行
class Solution {
public:int sumIndicesWithKSetBits(vectorint nums, int k) {int res 0;for(int i 0; i nums.size();i){if(count(i) k){res nums[i];}}return res;}int count(int num){int sum 0;for(int i 0; i 32; i){if(num (1 i)){sum;}} return sum;}
}; 除了位元算还有一种可以求一个数二进制的置为1的个数方法
int count(int num){int sum 0;while(num){sum (num % 2);num / 2;}return sum;}
【1.26】2846.边权重均等查询
2846. 边权重均等查询https://leetcode.cn/problems/minimum-edge-weight-equilibrium-queries-in-a-tree/ 2500分hard题超出水平范围太多暂时跳过。 【1.27】2861.最大合金数
2861. 最大合金数https://leetcode.cn/problems/maximum-number-of-alloys/ 看题目“所有合金都需要由同一台机器制造。”又给了个最大值budget让求取得的最大合金数也满足二段性那就是二分法求解了因为设置这个mid当我们最大数设置为mid那么比mid小的数就都不能取了。 1.设置这个二分第一个点就是最大值可以稍微的小一点我们可以设置为budget/1单价最小就是1 库存的最大量其实根据木桶效应应该是库存的最小量
2.先置为false遍历每一个机器的花费再内层遍历每一个零件求出每个零件加起来总共的spend再和budget比对如果比这个小那么这个mid可以取就进行变换置为true如果不行再改right
3.在内层遍历的时候要考虑if(composition[i][j] * (long)mid - stock[j] 0)这个很关键库存够了就置为0不能是负数我一直卡在这。
//花费小于budget求能创造合金的最大值二分
class Solution {
public:int maxNumberOfAlloys(int n, int k, int budget, vectorvectorint composition, vectorint stock, vectorint cost) {int left 0;
//右侧值不用设置太大考虑最大值 auto max max_element(stock.begin(),stock.end()); int right *max budget;int ans 0;while(left right){int mid left ((right -left) / 2);//设置的最大值当这个满足的时候比他小的都不合适bool flag false;//如果可以制造出就用true//遍历一遍每台机器花费for(int i 0; i k; i){long spend 0;for(int j 0; j n; j){if(composition[i][j] * (long)mid - stock[j] 0){spend (composition[i][j] * (long)mid - stock[j]) * cost[j];}}if(budget spend){flag true;break;//第i类就能搞定了}}if(flag){ans mid;left mid 1;}else{right mid -1;}}return ans;}
};
【1.28】365.水壶问题
365. 水壶问题https://leetcode.cn/problems/water-and-jug-problem/ 这个问题除了用深度优先搜索也是刚会用的还可以用数学方法更好操作贝祖定理解决但是需要考虑的问题比较多。 1.先分析一下这些操作的实质其实这个水的总量变化只能是x或者是y因为首先操作的结果至少有一个桶是空的有一个是满的把一个倒掉或者加满假如说把一个半满的水加满或者倒掉是没有意义的因为等价于一开始就把它置为0或者加满。
2.所以我们的目标变成了找到一堆数组a和b来满足ax by z那么只需满足z x y的情况下 如果a 0,b 0一定ok如果a 0操作就是先给b加满把b到给aa倒掉再把b剩下的到给a如此反复。如果是b 0 把操作反过来就行。
3.贝祖定理表示如果要实现ax by z只需要z整除x和y的最大公约数即可。
class Solution {
public:bool canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {if(jug1Capacity jug2Capacity targetCapacity){return false;}//这里贝组定理用之前考虑x或者y万一是0没有最大公约数if(jug1Capacity 0 ||jug2Capacity 0){return targetCapacity 0 || jug1Capacity jug2Capacity targetCapacity; }else{return targetCapacity % gcd(jug1Capacity,jug2Capacity) 0;}}
};
【1.29】514.自由之路
514. 自由之路https://leetcode.cn/problems/freedom-trail/ 这是一道困难题思路能想到是用dp来解但是解法还是有一定难度的。分为几个步骤逻辑要清晰。 代码主要分为几个步骤首先是对king进行字母到位置的映射然后创建dp初始化然后dp函数的实现。创建位置索引的时候这种映射的构建是为了在后续动态规划的过程中更方便地获取每个字符在环形拨盘上的位置信息。 dp初始化初始值给个最大值 动态规划转移要分类在i0的时候第一个字符不需要考虑前一个字符的位置所以分开对于不是第一个字符要进行一遍循环对上一个字符的位置循环进行dp函数的编写最后输出dp最后一行的最小值 对于这种环形的可以顺时针逆时针转动的函数求最小值这个函数值得记一下加一个len就能完美解决负数问题。 class Solution {
public:int getMin(int len,int a, int b){return min((len a - b) % len ,(len b - a) % len);}int findRotateSteps(string ring, string key) {
//第一步先建立ring中字母的位置索引vectorint pos[26];for(int i 0; i ring.size(); i){pos[ring[i] - a].push_back(i);}//第二步创建dp初始化vectorvectorint dp(key.size(),vectorint(ring.size(),INT_MAX));//第三步 动态规划状态转移for(int i 0; i key.size(); i){//遍历key的每个字符for(auto j : pos[key[i] - a]){//遍历key【i】在圆盘出现的每个位置if(i 0){dp[i][j] min(dp[i][j],0 getMin(ring.size(),0,j) 1);continue;}//如果不是第一个遍历前一个的字符的位置状态for(auto k : pos[key[i - 1] - a]){dp[i][j] min(dp[i][j],dp[i - 1][k] getMin(ring.size(),k,j) 1);} }}return *min_element(dp.back().begin(),dp.back().end());}
}; 【1.30】2808.使循环数组所有元素相等的最少秒数
2808. 使循环数组所有元素相等的最少秒数https://leetcode.cn/problems/minimum-seconds-to-equalize-a-circular-array/ 1900分左右的题目用哈希表解决思路不算难主要是昨天的题给了思路一看题目就知道是一个圆环形状的左右都能走。哈希表存一下出现的元素的索引i用数组存因为可能有多个。按照圆环找mx/2的最小值就行。 先搞个哈希表每个nums【i】对应的i值存到数组里为了后续遍历的时候用按照圆的方案去找相邻最远的值求每个nums【i】的数值里距离最远的值然后找最小值求出来即可。在找个遍历中先n为了找圆环情况两个的距离后边遍历的是相邻的。
class Solution {
public:int minimumSeconds(vectorint nums) {unordered_mapint,vectorint map;int res nums.size();//先搞个哈希表每个nums【i】对应的i值存到数组里for(int i 0; i nums.size(); i){map[nums[i]].push_back(i);}//不要忘了找圈for(auto s : map){int mx s.second[0] nums.size() - s.second.back();for(int i 1; i s.second.size(); i){mx max(mx, s.second[i] - s.second[i - 1]);}res min(res, mx/2);}return res;}
};
【1.31】2760.找出不同元素数目差数组
2670. 找出不同元素数目差数组https://leetcode.cn/problems/find-the-distinct-difference-array/ 哈希表难点在于建立数组的时候的范围还有运用哈希表去统计“从第i个数到最后一个数不同的数的数量”和“从第一个数到第i个数不同数的数量” class Solution {
public:vectorint distinctDifferenceArray(vectorint nums) {int n nums.size();vectorint res;unordered_setint st;vectorint suf(n 1);//为了满足后边运算的时候suf(n -1)for(int i n - 1; i 0; i--){st.insert(nums[i]);suf[i] st.size();//从第i开始到结尾不同值的数量}st.clear();for(int i 0; i n; i){st.insert(nums[i]);//从第一个数开始到第i个数不同值的数量res.push_back(st.size() -suf[i 1]);}return res;}
};
创建suf数组大小是n1的时候是为了后边满足运算的时候sufn - 1.
