1. 力扣1441：用栈操作构建数组
1.1 题目：
给你一个数组 target 和一个整数 n。每次迭代，需要从 list = { 1 , 2 , 3 ..., n } 中依次读取一个数字。
请使用下述操作来构建目标数组 target ：
"Push"：从list中读取一个新元素， 并将其推入数组中。"Pop"：删除数组中的最后一个元素。- 如果目标数组构建完成，就停止读取更多元素。
题目数据保证目标数组严格递增，并且只包含 1 到 n 之间的数字。
请返回构建目标数组所用的操作序列。如果存在多个可行方案，返回任一即可。
示例 1：
输入：target = [1,3], n = 3 输出：["Push","Push","Pop","Push"] 解释： 读取 1 并自动推入数组 -> [1] 读取 2 并自动推入数组，然后删除它 -> [1] 读取 3 并自动推入数组 -> [1,3]
示例 2：
输入：target = [1,2,3], n = 3 输出：["Push","Push","Push"]
示例 3：
输入：target = [1,2], n = 4 输出：["Push","Push"] 解释：只需要读取前 2 个数字就可以停止。
提示：
1 <= target.length <= 1001 <= n <= 1001 <= target[i] <= ntarget严格递增
1.2 思路：
哈希表记录target数组的值，分遇见了和没遇见两种情况讨论。
1.3 题解：
class Solution {
public List<String> buildArray(int[] target, int n) {
List<String> list = new LinkedList<>();
// 用哈希表将数组中的值存起来
// 如果遇到了，就加入push，否则加入push和pop
HashSet<Integer> hashset = new HashSet<>();
for(int i : target){
hashset.add(i);
}
//target[target.length-1]肯定是小于等于n的
// 所以条件范围用target[target.length-1]限定
for(int i = 1; i <= target[target.length-1]; i++){
if(!hashset.contains(i)){
list.add("Push");
list.add("Pop");
}else{
list.add("Push");
}
}
return list;
}
}2. 力扣844：比较含退格的字符串
2.1 题目：
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
示例 1：
输入：s = "ab#c", t = "ad#c" 输出：true 解释：s 和 t 都会变成 "ac"。
示例 2：
输入：s = "ab##", t = "c#d#" 输出：true 解释：s 和 t 都会变成 ""。
示例 3：
输入：s = "a#c", t = "b" 输出：false 解释：s 会变成 "c"，但 t 仍然是 "b"。
提示：
1 <= s.length, t.length <= 200s和t只含有小写字母以及字符'#'
进阶：
- 你可以用
O(n)的时间复杂度和O(1)的空间复杂度解决该问题吗？
2.2 思路：
用栈也可以，我用的是StringBuffer的api，主要是equals可以省去了最后的比较过程比较方便和操作都可以调用api来完成。
2.3 题解：
class Solution {
public boolean backspaceCompare(String s, String t) {
StringBuffer sb1 = new StringBuffer();
StringBuffer sb2 = new StringBuffer();
for(int i = 0; i < s.length(); i++){
char ch1 = s.charAt(i);
if(ch1 != '#'){
sb1.append(ch1);
}else{
// 这里防止当sb为空的时候遇见#，deleteCharAt会报错
if(sb1.length()-1 >= 0){
sb1.deleteCharAt(sb1.length()-1);
}
}
}
for(int i = 0; i < t.length(); i++){
char ch2 = t.charAt(i);
if(ch2 != '#'){
sb2.append(ch2);
}else{
if(sb2.length()-1 >= 0){
sb2.deleteCharAt(sb2.length()-1);
}
}
}
return sb1.toString().equals(sb2.toString());
}
}3. 力扣682：棒球比赛
3.1 题目：
你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。
比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表 ops，其中 ops[i] 是你需要记录的第 i 项操作，ops 遵循下述规则：
- 整数
x- 表示本回合新获得分数x "+"- 表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。"D"- 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。"C"- 表示前一次得分无效，将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。
请你返回记录中所有得分的总和。
示例 1：
输入：ops = ["5","2","C","D","+"] 输出：30 解释： "5" - 记录加 5 ，记录现在是 [5] "2" - 记录加 2 ，记录现在是 [5, 2] "C" - 使前一次得分的记录无效并将其移除，记录现在是 [5]. "D" - 记录加 2 * 5 = 10 ，记录现在是 [5, 10]. "+" - 记录加 5 + 10 = 15 ，记录现在是 [5, 10, 15]. 所有得分的总和 5 + 10 + 15 = 30
示例 2：
输入：ops = ["5","-2","4","C","D","9","+","+"] 输出：27 解释： "5" - 记录加 5 ，记录现在是 [5] "-2" - 记录加 -2 ，记录现在是 [5, -2] "4" - 记录加 4 ，记录现在是 [5, -2, 4] "C" - 使前一次得分的记录无效并将其移除，记录现在是 [5, -2] "D" - 记录加 2 * -2 = -4 ，记录现在是 [5, -2, -4] "9" - 记录加 9 ，记录现在是 [5, -2, -4, 9] "+" - 记录加 -4 + 9 = 5 ，记录现在是 [5, -2, -4, 9, 5] "+" - 记录加 9 + 5 = 14 ，记录现在是 [5, -2, -4, 9, 5, 14] 所有得分的总和 5 + -2 + -4 + 9 + 5 + 14 = 27
示例 3：
输入：ops = ["1"] 输出：1
提示：
1 <= ops.length <= 1000ops[i]为"C"、"D"、"+"，或者一个表示整数的字符串。整数范围是[-3 * 104, 3 * 104]- 对于
"+"操作，题目数据保证记录此操作时前面总是存在两个有效的分数 - 对于
"C"和"D"操作，题目数据保证记录此操作时前面总是存在一个有效的分数
3.2 思路：
典型的栈的问题，用栈记录合适的数字，然后依据题目判断即可。
3.3 题解：
class Solution {
public int calPoints(String[] operations) {
Deque<Integer> stack = new LinkedList<>();
for(String s : operations){
if (s.equals("C")){
stack.pop();
}else if (s.equals("D")){
stack.push(stack.peek()*2);
}else if (s.equals("+")){
int i = stack.pop();
int sum = i + stack.peek();
stack.push(i);
stack.push(sum);
}else{
// 如果是数字就加入
stack.push(Integer.parseInt(s));
}
}
int sums = 0;
for(int i : stack){
sums += i;
}
return sums;
}
}