theme: cyanosis
highlight: atom-one-dark
开启掘金成长之旅！这是我参与「掘金日新计划 · 12 月更文挑战」的第7天，点击查看活动详情
- 20.有效的括号
- 1047.删除字符串中的素有相邻重复项
- 150.逆波兰表达式求值
20.有效的括号
给定一个只包括
'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
我的解法（通过部分）
思路：因为包括的是固定的括号，所以先放进map里面。Map(6) { ‘(‘ => 0, ‘)’ => 0, ‘[‘ => 0, ‘]’ => 0, ‘{‘ => 0, ‘}’ => 0 } 然后更新所出现的字符的键值。
我的解题思路中出现的一个问题是，如果当前的字符在map表中能查询到，那么怎么让对应的符号的键值加 1 ？
后来的想法就是通过
if (map.has(i)) map.set(i, map.get(i) + 1);来实现。
在有效字母异位词里面，由于字母的ASCII码是连续的，所以可以让a-z对应到数组下标0-25。
var isValid = function(s) {
// 因为包括的是固定的括号，所以先放进map里面
let map = new Map();
let all = ['(', ')', '[', ']', '{', '}'];
all.forEach(item => map.set(item, 0));
// 更新map中的数值
for (const i of s) {
if (map.has(i)) map.set(i, map.get(i) + 1);
}
let oneRes = (map.get('(') + map.get(')')) % 2;
let twoRes = (map.get('{') + map.get('}') ) % 2;
let threeRes = (map.get('[') + map.get(']') ) % 2;
// 如果上面的结果都为0，说明成双出现。
if ((oneRes + twoRes + threeRes) == 0) {
return true
} else {
return false
}
};
通过率 76/92。其中遇到例子"([)]"就报错了。不满足左括号必须以正确的顺序闭合。
卡神解法
这道题目是用栈来解决的经典题目。栈在计算机系统中应用的场景还是挺多的，包括编译器做词法分析、linux系统的命令进哪一个目录。
那么这题主要就是考虑返回false的几种情况。对字符串 s 的处理就是，遇到左括号就把对应的右括号压入栈中，遇到右括号就从栈中消除。那么这样就会有三种不匹配的情况出现：
- 字符串里左方向的括号多余了 ，所以不匹配。
- 括号没有多余，但是 括号的类型没有匹配上。
- 字符串里右方向的括号多余了，所以不匹配。
借用一下carl老师《代码随想录》中的动图
var isValid = function (s) {
const stack = [];
for (let i = 0; i < s.length; i++) {
let c = s[i];
switch (c) {
case '(':
stack.push(')');
break;
case '[':
stack.push(']');
break;
case '{':
stack.push('}');
break;
default:
if (c !== stack.pop()) {
return false;
}
}
}
return stack.length === 0;
};
- 利用switch将右括号压入栈中。
// 简化版本
var isValid = function(s) {
const stack = [],
map = {
"(":")",
"{":"}",
"[":"]"
};
for(const x of s) {
if(x in map) {
stack.push(x);
continue;
};
if(map[stack.pop()] !== x) return false;
}
return !stack.length;
};
for(const x of s)代码中用的是 map 的思想，map是一个对象，所以没有用 map.has() 方法。还有要注意的就是')'in map返回的是false- 简化版本中是把左边的括号压入栈中，当遇到右括号时，就判断栈顶的弹出来的这个左括号，其对应的键值和当前右括号是否相等。
1047.删除字符串中的素有相邻重复项
题目链接：1047. 删除字符串中的所有相邻重复项 – 力扣（LeetCode）
给出由小写字母组成的字符串
S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
例如：输入：”abbaca”，输出：”ca”
补充知识点：for-of循环也支持字符串遍历
我的解法
思路：还是利用栈的思想，在理解前一题的基础上
- 定义好一个空的栈和用来返回栈顶元素的
top()函数 - 遍历字符串中的每一个字符，当栈顶不存在这个字符的时候，直接压入。否则，如果存在，就对比消除
var removeDuplicates = function(s) {
// 定义一个栈
let stack = [];
// 该函数用于返回栈顶元素
var top = function () {
if (stack.length !== 0) {
let x = stack.pop();
stack.push(x);
return x
}
return stack;
}
for (let i of s) {
if (i == top()) {
stack.pop()
continue;
}
stack.push(i)
}
return stack.join('')
};
卡神解法
法一：使用栈
var removeDuplicates = function(s) {
const stack = [];
for(const x of s) {
let c = null;
if(stack.length && x === (c = stack.pop())) continue;
c && stack.push(c);
stack.push(x);
}
return stack.join("");
};
法二：双指针（模拟栈）
// 原地解法（双指针模拟栈）
var removeDuplicates = function(s) {
s = [...s];
let top = -1; // 指向栈顶元素的下标
for(let i = 0; i < s.length; i++) {
if(top === -1 || s[top] !== s[i]) { // top === -1 即空栈
s[++top] = s[i]; // 入栈
} else {
top--; // 推出栈
}
}
s.length = top + 1; // 栈顶元素下标 + 1 为栈的长度
return s.join('');
};
150.逆波兰表达式求值
题目链接：150. 逆波兰表达式求值 – 力扣（LeetCode）
根据 逆波兰表示法，求表达式的值。
有效的算符包括
+、-、*、/。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
这题没有思路，只能看大神代码，然后分析学习了。
卡神解法
例如：12+34+*
先1、2入栈，然后遇到 + 就把 1、2 弹出来相加，得到的结果 3 继续放回栈中。继续在栈中放入 3、4，同理相加得 7 然后放回栈中，这时栈中有两个元素 7、3 。遇到 * 继续进行上述操作。
var evalRPN = function(tokens) {
const s = new Map([
["+", (a, b) => a * 1 + b * 1],
["-", (a, b) => b - a],
["*", (a, b) => b * a],
["/", (a, b) => (b / a) | 0]
]);
const stack = [];
for (const i of tokens) {
if(!s.has(i)) {
stack.push(i);
continue;
}
stack.push(s.get(i)(stack.pop(),stack.pop()))
}
return stack.pop();
};
if(!s.has(i))当前遍历的 tokens 的子元素如果不是 加减乘除 ，那么就将元素压入栈中。s.get(i)得到运算符对应的函数，函数还需要两个参数，参数就是从栈中依次弹出的两个数(stack.pop(),stack.pop())，然后完成运算操作。- 最后通过
push()把结果压入栈中。
暂无评论内容