什么网站做任务的q币,广州网站备案方案,wordpress去除标志,手机视频网站怎么做1、题目描述
【题目链接】 标签#xff1a;栈 、字符串、模拟 难度#xff1a;简单 给你一个仅由 大写 英文字符组成的字符串 s 。 你可以对此字符串执行一些操作#xff0c;在每一步操作中#xff0c;你可以从 s 中删除 任一个 “AB” 或 “CD” 子字符串。 通过执行操作…1、题目描述
【题目链接】 标签栈 、字符串、模拟 难度简单 给你一个仅由 大写 英文字符组成的字符串 s 。 你可以对此字符串执行一些操作在每一步操作中你可以从 s 中删除 任一个 “AB” 或 “CD” 子字符串。 通过执行操作删除所有 “AB” 和 “CD” 子串返回可获得的最终字符串的 最小 可能长度。 注意删除子串后重新连接出的字符串可能会产生新的 “AB” 或 “CD” 子串。
示例 1 输入s “ABFCACDB” 输出2 解释你可以执行下述操作
从 “ABFCACDB” 中删除子串 “AB”得到 s “FCACDB” 。从 “FCACDB” 中删除子串 “CD”得到 s “FCAB” 。从 “FCAB” 中删除子串 “AB”得到 s “FC” 。 最终字符串的长度为 2 。 可以证明 2 是可获得的最小长度。
示例 2 输入s “ACBBD” 输出5 解释无法执行操作字符串长度不变。
提示 1 s.length 100 s 仅由大写英文字母组成
2、基本思路 这是一道简单的字符串处理的题目可以用栈模型上述的删除的过程即可值得注意的是删除子串后重新连接出的字符串可能会产生新的 “AB” 或 “CD” 子串。
下面是利用栈对示例 1 模拟的过程
初始化栈空栈空A入栈当前元素B与栈顶元素A构成子串ABA出栈栈空F入栈当前元素C栈顶元素F构不成子串C入栈当前元素A栈顶元素C构不成子串A入栈当前元素C栈顶元素A构不成子串C入栈当前元素D栈顶元素C构成子串CDC出栈当前元素B栈顶元素A构成子串ABA出栈字符串元素遍历完毕栈中元素的长度即为答案
3、代码实现 int minLength(string s) {stackchar st;for(int i 0;is.length();i){char c s[i];if(st.empty())st.push(c);else{if(cDst.top()C)st.pop();else if(cBst.top()A)st.pop();elsest.push(c);}}return st.size();
}
