Open fxxqq opened 5 years ago
栈是一个线性结构,在计算机中是一个相当常见的数据结构。
栈的特点是只能在某一端添加或删除数据,遵循先进后出的原则
每种数据结构都可以用很多种方式来实现,其实可以把栈看成是数组的一个子集,所以这里使用数组来实现
class Stack { constructor() { this.stack = [] } push(item) { this.stack.push(item) } pop() { this.stack.pop() } peek() { return this.stack[this.getCount() - 1] } getCount() { return this.stack.length } isEmpty() { return this.getCount() === 0 } }
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。
示例 1:
输入: "()" 输出: true
示例 2:
输入: "()[]{}" 输出: true
示例 3:
输入: "(]" 输出: false
示例 4:
输入: "([)]" 输出: false
示例 5:
输入: "{[]}" 输出: true
题意是匹配括号,可以通过栈的特性来完成这道题目
var isValid = function (s) { let map = { '(': -1, ')': 1, '[': -2, ']': 2, '{': -3, '}': 3 } let stack = [] for (let i = 0; i < s.length; i++) { if (map[s[i]] < 0) { stack.push(s[i]) } else { let last = stack.pop() if (map[last] + map[s[i]] != 0) return false } } if (stack.length > 0) return false return true };
概念
栈是一个线性结构,在计算机中是一个相当常见的数据结构。
栈的特点是只能在某一端添加或删除数据,遵循先进后出的原则![image](https://user-images.githubusercontent.com/22697565/46580791-35042200-ca5e-11e8-80ad-520abd166d3c.png)
实现
每种数据结构都可以用很多种方式来实现,其实可以把栈看成是数组的一个子集,所以这里使用数组来实现
应用
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。
示例 1:
示例 2:
示例 3:
示例 4:
示例 5:
题意是匹配括号,可以通过栈的特性来完成这道题目