字符串和stack的相关题解

今日小结今天学习字符串和stack主要是利用栈的先进后出解决相关问题之前也学过相关知识和题目算是巩固一下之前的学习go go go!!!上期栈的相关题目链接题目力扣859和牛客NC14326,NC14666,NC15029详细解答:1.859. 亲密字符串这道题算是一道入门题比较简单.题意给你两个字符串s和goal只要我们可以通过交换s中的两个字母得到与goal相等的结果就返回true否则返回false。交换字母的定义是取两个下标i和j下标从0开始且满足i ! j接着交换s[i]和s[j]处的字符。代码class Solution { public: bool buddyStrings(string s, string goal) { if(s.size()!goal.size())return false;//长度不同的两个字符串肯定不行 if(sgoal){ //如果两个字符串完全相同同时有重复的字符也可以 setcharst(s.begin(),s.end()); return st.size()s.size(); } vectorintdiff; for(int i0;is.size();i){ //找不同并存储下标 if(s[i]!goal[i])diff.push_back(i); } if(diff.size()!2)return false;//不同之处大于2不符合题意 int xdiff[0],ydiff[1]; if(s[x]goal[y]s[y]goal[x])return true;//交换可以得到 return false; } };2.NC14326题意这道题是模拟火车进站出站问题火车按照1.2.3.4.5…的车厢进站看出站能否按照给定的车厢顺序进行能的话输出Yes,不能输出No,火车的进站出站遵循栈的先进后出原则做题步骤循环读取n读到 n0 直接结束程序。在当前n下不断读取一组排列如果读到第一个数字是 0 退出本轮排列循环当前区块结束。使用栈模拟调度now 1 代表下一个即将进站的车厢编号。依次遍历目标序列中的每个数字 t ① 只要 now ≤ t 持续把 now 压入栈 now ② 查看栈顶栈顶 t栈顶弹出栈顶 ! t标记该序列不合法 okfalse 。遍历完整个序列oktrue 输出 Yes否则输出 No。当前n区块所有排列处理完成输出一个空行。代码#includebits/stdc.h using namespace std; #define endl \n; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; //循环读取n读到 n0 直接结束程序 while(cinnn!0){ vectorinta(n); while(cina[0]){ if(a[0]0)break;//如果读到第一个数字是 0 退出本轮排列循环 for(int i1;in;i){ cina[i]; } int now1;//代表下一个即将进站的车厢编号 stackintst; bool oktrue; for(int t:a){ while(nowt){ st.push(now); now; } if(st.top()!t)okfalse; else st.pop(); } if(okfalse){ coutNoendl; } else coutYesendl; } coutendl;//每个区块结束输出一个空行 } return 0; }3.NC14666这道题需要利用栈差分题意有 n 座高度互不相同的山排成一排。两座山 ij 能互相监视的条件中间所有山的高度 都小于 min(H[i],H[j])。所有满足条件的山对总数 初始防守能力。屏障只能放在两座山中间的间隙一旦放置所有跨越这个间隙的可监视山对都会失效。目标找到一处间隙使得被隔断的可监视山对数量尽可能大防守能力下降最多。输出规则​ 设屏障放在第 X 座山前也就是第 X-1 和 X 之间的间隙​ 多个间隙隔断数量相同时输出更小的X。解题步骤利用栈找到所有相互可见的山对r,j;利用差分数组统计区间覆盖次数对差分求前缀和得到每个间隙j被多少对山跨越遍历找到最大值并记录位置#include bits/stdc.h using namespace std; typedef long long ll; int main() { int t; scanf(%d, t); for (int i 1; i t; i) { ll n; // n代表山的数量 scanf(%lld, n); stackll st; // 单调栈存储山的下标栈内高度单调递增 vectorll H(n 2); vectorll diff(n 2, 0); // 差分数组用来统计区间覆盖次数 for (ll j 1; j n; j)scanf(%lld, H[j]); // 从左到右遍历每一座山j用单调栈找出所有能和j互相看见的山 for (ll j 1; j n; j) { // 栈不为空且栈顶对应的山高度小于当前山j两者可以互相看见 while (!st.empty() H[st.top()] H[j]) { ll r st.top(); // r是栈顶山的下标和j形成可见对(r,j) st.pop(); // 可见对(r,j)会跨越间隙[r, j-1]差分数组区间1 diff[r]; diff[j]--; } // 栈不为空剩余栈顶山比当前山高栈顶r和j也能互相看见 if (!st.empty()) { ll r st.top(); diff[r]; diff[j]--; } // 当前下标j入栈维持栈的单调性 st.push(j); } ll ans 0; // 前缀和代表当前间隙可阻断的哨兵对数 ll s -1; // 记录最大阻断数量 ll b; // 记录最优屏障位置编号 for (ll j 1; j n; j) { ans diff[j]; // 差分求前缀和得到间隙j的阻断数量 // 只有当前阻断数严格大于最大值时才更新相等保留更小位置满足题意要求 if (ans s) { s ans; b j 1; // 间隙j对应题目要求的屏障位置Xj1 } } // 按格式输出Case #组号: 屏障位置 最大减少量 printf(Case #%d: %lld %lld\n, i, b, s); } return 0; }4.NC15029题目意思字符 o 小泡、 O 大泡​ 1两个相邻 小泡o → 合并成 大泡O​ 2两个相邻 大泡O → 互相爆炸全部消失​ 3合并、爆炸持续从左到右反复执行直到不能操作解题思路​ 遍历每个字符压入栈每次压入后循环检查栈顶能否触发规则反复处理连锁反应规则顺序推演栈顶两个都是 o 弹出两个 o 压入 O 合并栈顶两个都是 O 弹出两个 O 爆炸不断循环直到栈顶无法继续操作#includebits/stdc.h using namespace std; #define endl \n; void solve(){ string s; cins; stackcharst; for(char c:s){ st.push(c); //持续处理连锁爆炸或合并 while(st.size()2){ char c1st.top(); st.pop(); char c2st.top(); if(c1oc2o){ //两个小泡合成大泡弹出栈顶的小泡压入大泡 st.pop(); st.push(O); } else if(c1Oc2O)st.pop();//两个大泡只弹出不压入 else {//当无法操作时把刚取出的字符放回栈中并退出循环 st.push(c1); break; } } } //栈反栈输出答案 string ans; while(!st.empty()){ ansst.top(); st.pop(); } reverse(ans.begin(),ans.end()); coutansendl; } int main(){ int t; cint; while(t--)solve(); }今日任务已完成加深了对栈和字符串相关题目的理解和学习