力扣算法JS LC [20. 有效的括号] LC [1047. 删除字符串中的所有相邻重复项]

本文主要是介绍力扣算法JS LC [20. 有效的括号] LC [1047. 删除字符串中的所有相邻重复项]，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

LC 20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([)]"
输出：false

示例 5：

输入：s = "{[]}"
输出：true

解题思路：判断值有没有在哈希表中，没有写入栈中。有就判断栈中的值与哈希表所映射的值一不一样。

代码：

var isValid = function(s) {
    if(s.length % 2 === 1) {
        return false;
    };
    const map = new Map([
        [')', '('],
        [']', '['],
        ['}', '{']
    ]);
    const arr = [];
    for(let i of s) {
        if(map.has(i)) { //判断是否在哈希表出现
            if(!arr.length || arr[arr.length - 1] !== map.get(i)) {//查看栈中有没有值，如果有，判断 等不等于当前值在哈希表所映射的值
                return false
            }
            arr.pop();
        } else {
            arr.push(i);
        }
    }
    return !arr.length; //判断最后链表有没有剩下值
};

LC 1047. 删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

解题思路：利用栈先进后出，判断栈顶元素与当前元素是否相同，相同时移出栈顶元素，不同时压入当前元素

代码：

var removeDuplicates = function(s) {
    const stack = []
    for(let x of s) {
        // 栈里面有元素且栈顶元素等于当前值 x 时，移除栈顶元素
        if(stack.length && stack[stack.length - 1] === x) {
            stack.pop();
        } else { //不然就将当前元素压进栈中
            stack.push(x);
        }
    }
    return stack.join("")
};

这篇关于力扣算法JS LC [20. 有效的括号] LC [1047. 删除字符串中的所有相邻重复项]的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！