复活的刷题复盘- 4月限定回

备战算法面刷刷力扣本期封面原图3474.字典序最小的生成字符串注意到数据范围不大可以进行一个暴力的贪心检查是T就先放上去然后空位先放a如果有F位置检测到字符串相同就把最右边的一个可变的a变为b注意check没有可变a的情况//// Created by Swan416 on 2026-03-31 10:50.//classSolution{public:stringgenerateString(string str1,string str2){intnstr1.size(),mstr2.size();vectorcharans(nm-1,0);for(inti0;in;i){if(str1[i]T){for(intj0;jm;j){if(ans[ij]0)ans[ij]str2[j];elseif(ans[ij]!str2[j])return;}}}vectorboolchangable(nm-1,false);for(inti0;inm-1;i){if(ans[i]0){ans[i]a;changable[i]true;}}for(inti0;in;i){if(str1[i]F){// 此时需要判断ans[i...im-1]是否与str2相同boolflagtrue;for(intj0;jm;j){if(ans[ij]!str2[j]){flagfalse;break;}}if(flag){// 如果相同就要把最右边的能改动的a变为bboolchangedfalse;for(intjm-1;j0;j--){if(changable[ij]){ans[ij]b;changedtrue;break;}}if(!changed)return;}}}returnstring(all(ans));}};128.最长连续序列题目要求O(n)所以肯定不能sort我们直接把所有数字加进一个set自动排序好然后直接从小到大遍历后面就很好理解了上一个数字没有就数一遍更新答案//// Created by Swan416 on 2026-03-31 11:23.//classSolution{public:intlongestConsecutive(vectorintnums){unordered_setints(nums.begin(),nums.end());intlongest0;for(intnum:s){if(!s.count(num-1)){// Only start counting if its the start of a sequenceintcurrentNumnum;intcurrentStreak1;while(s.count(currentNum1)){currentNum;currentStreak;}longestmax(longest,currentStreak);}}returnlongest;}};2751.机器人碰撞不需要知道结束时的位置那其实就是括号匹配多维护几个数据压栈里面然后删删删就行注意中间的处理//// Created by Swan416 on 2026-04-01 13:15.//classSolution{public:vectorintsurvivedRobotsHealths(vectorintpositions,vectorinthealths,string directions){structRobot{intposition;inthealth;chardirection;intindex;// To keep track of the original index};intnpositions.size();vectorRobotrobots(n);for(inti0;in;i){robots[i]{positions[i],healths[i],directions[i],i};}sort(robots.begin(),robots.end(),[](constRobota,constRobotb){returna.positionb.position;});stackRobotst;for(Robotrobot:robots){if(robot.directionRorst.empty()orst.top().directionL){st.push(robot);}else{while(!st.empty()st.top().directionRst.top().positionrobot.position){Robot topRobotst.top();st.pop();if(topRobot.healthrobot.health){topRobot.health-1;robot.health0;// Robot is destroyedst.push(topRobot);break;}elseif(topRobot.healthrobot.health){robot.health-1;}else{robot.health0;break;// Both robots are destroyed}}if(robot.health0){st.push(robot);}}}vectorRobotsurvived;while(!st.empty()){survived.push_back(st.top());st.pop();}sort(survived.begin(),survived.end(),[](constRobota,constRobotb){returna.indexb.index;});vectorintresult;for(constRobotrobot:survived){result.push_back(robot.health);}returnresult;}};