下载掌阅APP，畅读海量书库
立即打开
【问题描述】 给定一个由大/小写英文字母组成的字符串s，整理该字符串。一个整理好的字符串中的两个相邻字符s[ i ]和s[ i +1]（0≤ i ≤s.length-2）要满足以下条件：
（1）若s[ i ]是小写字母，则s[ i +1]不可以是相同的大写字母。
（2）若s[ i ]是大写字母，则s[ i +1]不可以是相同的小写字母。
每次都可以从字符串中选出满足上述条件的两个相邻字符并删除，直到将字符串整理好为止。返回整理好的字符串，题目保证在给出的约束条件下测试样例对应的答案是唯一的。注意，空字符串也属于整理好的字符串，尽管其中没有任何字符。
例如，s=＂abBAcC＂，一种整理过程是＂a bB AcC＂→＂ aA cC＂→＂cC＂→＂＂，答案为＂＂。
【限制】 1≤s.length≤100，s只包含小写英文字母和大写英文字母。
【解题思路】 使用栈模拟求解 。设计一个字符栈st，用 i 遍历s，若栈不为空，当s[ i ]与栈顶字符满足题目中给定的任意一个条件时出栈栈顶字符（相当于删除s[ i ]和栈顶一对字符），否则将s[ i ]进栈。s遍历完毕，将栈中的所有字符按从栈顶到栈底的顺序合并起来得到答案。对应的算法如下。
C++：
提交运行：
另外，也可以直接用字符串ans模拟栈操作，这样在s遍历完毕，ans中剩下的字符串就是答案。对应的算法如下。
C++：
提交运行：
采用后一种方法对应的Python算法如下。
Python：
提交运行：
【问题描述】 给定一个字符串path，表示指向某一文件或目录的UNIX风格绝对路径（以'/'开头），请将其转换为更加简洁的规范路径并返回得到的规范路径。在UNIX风格的文件系统中，一个点（.）表示当前目录本身；两个点（..）表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜线（即'//'）都被视为单个斜线'/'。对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。注意，返回的规范路径必须遵循以下格式：
（1）始终以斜线'/'开头。
（2）两个目录名之间只有一个斜线'/'。
（3）最后一个目录名（如果存在）不能以'/'结尾。
（4）路径仅包含从根目录到目标文件或目录的路径上的目录（即不含'.'或'..'）。
例如，path=＂/../＂，答案为＂/＂，从根目录向上一级是不可行的，因为根目录是可以到达的最高级。path=＂/a/./b/../../c/＂，答案为＂/c＂。
【限制】 1≤path.length≤3000，path由英文字母、数字、'.'、'/'或'_'组成，并且是一个有效的UNIX风格绝对路径。
【解题思路】 用栈模拟进入下一级目录 （ 前进 ） 和上一级目录 （ 回退 ） 操作 。先将path按'/'分隔符提取出对应的字符串序列，例如，path=＂/a/./b/../../c/＂时对应的字符串序列为＂＂，＂a＂，＂.＂，＂b＂，＂..＂，＂..＂，＂c＂。然后定义一个字符串栈st，用word遍历所有字符串，若word=＂.＂，则跳过；若word=＂..＂，则回退，即出栈一次；若word为其他非空字符串，则将其进栈。遍历前面字符串序列的结果如图3.8所示。
遍历完毕将栈中的所有字符串按从栈底到栈顶的顺序加上＂\＂并连接起来构成ans，这里ans=＂/c＂，最后返回ans。
图3.8 遍历字符串序列的结果
【问题描述】 给定一个目标数组target和一个整数 n ，每次迭代，需要从list={1，2，3，…， n }中依次读取一个数字，请使用下述操作构建目标数组target。
（1）Push：从list中读取一个新元素，并将其推入数组中。
（2）Pop：删除数组中的最后一个元素。
如果目标数组构建完成，停止读取更多元素。题目数据保证目标数组严格递增，并且只包含1～ n 的数字。请返回构建目标数组所用的操作序列。题目数据保证答案是唯一的。
例如，输入target=[1，3]，
n
=3，输出为[＂Push＂，＂Push＂，＂Pop＂，＂Push＂]。读取1并自动推入数组-
[1]，读取2并自动推入数组，然后删除它-
[1]，读取3并自动推入数组-
[1，3]。
【限制】 1≤target.length≤100，1≤target[ i ]≤100，1≤ n ≤100。target是严格递增的。
【解题思路】 使用栈实现两个序列的简单匹配 。用 j 从0开始遍历target，用 i 从1到 n 循环：先将 i 进栈（每个 i 总是要进栈的，这里并没有真正设计一个栈，栈操作是通过＂Push＂和＂Pop＂表示的，存放在结果数组ans中），若当前进栈的元素 i 不等于target[ j ]，则将 i 出栈，否则 j 加1继续比较，如图3.9所示。若target中的所有元素处理完毕，退出循环。最后返回ans。
图3.9 栈操作过程
对应的算法如下。
C++：
提交运行：
Python：
提交运行：
【问题描述】 给定pushed和popped两个序列，每个序列中的值都不重复，只有当它们可能是在最初空栈上进行的推入push和弹出pop操作序列的结果时返回true，否则返回false。
例如，pushed=[1，2，3，4，5]，popped=[4，5，3，2，1]，输出为true；pushed=[1，2，3，4，5]，popped=[4，3，5，1，2]，输出为false。
【限制】 0≤pushed.length=popped.length≤1000，0≤pushed[ i ]，popped[ i ]＜1000，并且pushed是popped的一个排列。
【解题思路】 使用栈实现两个序列的简单匹配 。先考虑这样的情况，假设 a 和 b 序列中均含 n （ n ≥1）个整数，都是1～ n 的某个排列，现在要判断 b 是否为以 a 作为输入序列的一个合法的出栈序列，即 a 序列经过一个栈是否得到了 b 的出栈序列。求解思路是先建立一个st，用 j 遍历 b 序列（初始为0）， i 从0开始遍历 a 序列：
（1）将 a [ i ]进栈。
（2）栈不为空并且栈顶元素与 b [ j ]相同时循环：出栈一个元素同时执行 j ++。
在上述过程结束后，如果栈为空，返回true表示 b 序列是 a 序列的出栈序列，否则返回false表示 b 序列不是 a 序列的出栈序列。
例如 a ={1，2，3，4，5}， b ={3，2，4，5，1}，由 a 产生 b 的过程如图3.10所示，所以返回true。对应的算法如下。
C++：
图3.10 由 a ={1,2,3,4,5}产生 b ={3,2,4,5,1}的过程
提交运行：
Python：
提交运行：
【问题描述】 给定一个只包含'（'、'）'、'{'、'}'、'['、']'的字符串s，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合，左括号必须以正确的顺序闭合，每个右括号都有一个对应的相同类型的左括号。
例如，s=＂（）[]{}＂时答案为true，s=＂（]＂时答案为false。
【限制】 1≤s.length≤10 4 ，s仅由'（'、'）'、['、']'、{'、'}'组成。
图3.11 括号的匹配
【解题思路】 使用栈实现括号的最近匹配 。字符串s中各种括号的匹配如图3.11所示，也就是说每个右括号总是与前面最接近的尚未匹配的左括号进行匹配，即满足最近匹配原则，所以用一个栈求解。
先建立仅存放左括号的栈st， i 从0开始遍历s：
（1）s[ i ]为任一左括号时将其进栈。
（2）若s[ i ]='）'，如果栈st为空，说明该'）'无法匹配，返回false；若栈顶不是'（'，同样说明该'）'无法匹配，返回false；否则出栈'（'继续判断。
（3）若s[ i ]=']'，如果栈st为空，说明该']'无法匹配，返回false；若栈顶不是'['，同样说明该']'无法匹配，返回false；否则出栈'['继续判断。
（4）若s[ i ]='}'，如果栈st为空，说明该'}'无法匹配，返回false；若栈顶不是'{'，同样说明该'}'无法匹配，返回false；否则出栈'{'继续判断。
s遍历完毕，若栈为空，说明s是有效的，返回true；否则说明s是无效的，返回false。
【问题描述】 给定一个由'（'、'）'和小写字母组成的字符串s，从该字符串中删除最少数目的'（'或者'）'（可以删除任意位置的括号），使得剩下的括号字符串有效，请返回任意一个有效括号字符串。有效括号字符串应当符合以下任意一条要求：
（1）空字符串或者只包含小写字母的字符串。
（2）可以被写成AB（A连接B）的字符串，其中A和B都是有效括号字符串。
（3）可以被写成（A）的字符串，其中A是一个有效括号字符串。
例如，s=＂lee（t（c）o）de）＂，答案为＂lee（t（c）o）de＂、＂lee（t（co）de）＂或者＂lee（t（c）ode）＂；s=＂））（（＂，答案为＂＂。
【限制】 1≤s.length≤10 5 ，s[ i ]可能是'（'、'）'或者英文小写字母。
【解题思路】 使用栈实现括号的最近匹配 。定义一个栈st（保存所有无效的括号），循环处理s中的每个字符ch=s[ i ]：如果ch为'（'，将其序号 i 进栈；如果ch为右括号'）'，且栈顶为'（'，出栈栈顶元素（说明这一对括号是匹配的）；否则将其序号 i 进栈，其他字符直接跳过。最后从栈顶到栈底处理栈中的所有序号，依次删除其相应的无效括号。例如，s=＂lee（t（c）o）de）＂，通过栈st找到两对匹配的括号，遍历完毕栈中只含有最后一个右括号的下标，即st=[12]，删除该无效括号后s=＂lee（t（c）o）de＂，如图3.12所示。
对应的算法如下。
C++：
图3.12 删除无效的括号
提交运行：
Python：
提交运行：
【问题描述】 给定一个只包含'（'和'）'的字符串s，找出最长有效（格式正确且连续）括号子串的长度。
例如，s=＂）（）（））＂，答案为4，其中最长有效括号子串是＂（）（）＂；s=＂＂时答案为0。
【限制】 0≤s.length≤3×10 4 ，s[ i ]为'（'或者'）'。
【解题思路】 使用栈实现括号的最近匹配 。使用一个栈在遍历字符串s的过程中判断到目前为止扫描的子串的有效性，同时得到最长有效括号子串的长度。具体做法是始终保持栈底元素为当前最后一个没有被匹配的右括号的下标，这样主要是考虑了边界条件的处理，栈中的其他元素维护左括号的下标，用 i 从0开始遍历字符串s：
（1）若s[ i ]='（'，将下标 i 进栈。
（2）若s[ i ]='）'，出栈栈顶元素，表示匹配了当前的右括号。如果栈为空，说明当前的右括号为没有被匹配的右括号，将其下标进栈，以更新最后一个没有被匹配的右括号的下标；如果栈不为空，当前右括号的下标减去栈顶元素即为以该右括号为结尾的最长有效括号子串的长度，在所有这样的长度中求最大值ans，最后返回ans即可。需要注意的是，如果一开始栈为空，当第一个字符为'（'时会将其下标进栈，这样栈底就不满足是最后一个没有被匹配的右括号的下标，为了保持统一，初始时往栈中进栈一个值-1。
例如，s=＂）（）（））＂，ans=0，st=[-1]，遍历s如下：
（1）s[0]='）'，出栈-1，栈为空，说明该'）'没有被匹配，将其下标0进栈，st=[0]。
（2）s[1]='（'，将其下标1进栈，st=[0，1]。
（3）s[2]='）'，出栈1，此时栈st=[0]，栈不为空，说明找到匹配的子串＂（）＂，其长度为2-st.top（）=2-0=2，ans=max（ans，2）=2。
（4）s[3]='（'，将其下标3进栈，st=[0，3]。
（5）s[4]='）'，出栈3，此时栈st=[0]，栈不为空，说明找到匹配的子串＂（）（）＂，其长度为4-st.top（）=4-0=4，ans=max（ans，4）=4。
（6）s[5]='）'，出栈0，栈为空，说明该'）'没有被匹配，将其下标5进栈，st=[5]。
s遍历完毕，最后答案为ans=4。对应的算法如下。
C++：
提交运行：
Python：
提交运行：
