leetcode 32 longest valid parentheses (最长有效括号)
给定一个只包含
'('
和')'
的字符串,找出最长的包含有效括号的子串的长度。示例 1:
输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()"示例 2:
输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"
这道题可以用动态规划来做,也能用简洁明了的栈来解决。
栈是一种先进后出(lifo)的有序集合,新添加的元素在栈顶,旧元素在栈底。
以下图为例,1、2、3、4、5、6、7先后进栈:
创建一个类来表示栈:
class stack { // 初始化类,创建数组 items 存放入栈元素 constructor() { this.items = []; } // push 方法进行元素入栈(可同时入栈一或多个元素),无返回值 push() { this.items.push(...arguments); } // pop 方法出栈一个元素,返回出栈元素 pop() { return this.items.pop(); } // peek 方法返回栈顶元素,不对栈本身做任何操作 peek() { return this.items[this.items.length-1]; } // size 方法返回栈内元素个数 size() { return this.items.length; } // isempty 方法查看栈是否为空,返回布尔值 isempty() { return this.items.length == 0; } // clear 方法清空栈,无返回值 clear() { this.items = []; } // print 方法打印栈内元素 print() { console.log(this.items.tostring()); } } // 测试 let stack = new stack(); stack.push(1,2,3,4); stack.print(); // 1,2,3,4 stack.isempty(); // false stack.size(); // 4 stack.pop(); // 4 stack.peek(); // 3 stack.clear();
因为 javascript 的类内暂时无法定义静态成员,所以可以在类外访问到存储栈元素的数组 items,这个操作是很危险的。
stack.items; // [1, 2, 3, 4]
这时可以使用闭包和iife
进行避免,这是一个很无奈的办法:
let stack = (function () { // 使用 weakmap 存储数组(数组存放进栈元素) let items = new weakmap(); class stack { constructor() { items.set(this, []); } push() { items.get(this).push(...arguments); } // 其他方法 } return stack; })(); let s = new stack(); // 无法访问到 items s.items; // undefined
weakmap: weakmap
是类似map
的键值对集合,但weakmap
的键是弱引用的,只要不存在引用,垃圾回收机制就会回收掉占用的内存,相当于自动删除,而不用手动删除。
思路:
start
存放有效括号起始下标,maxlen
存放最大长度;start
;若栈不为空,则栈顶元素出栈;start
的距离,并更新maxlen
;maxlen
;function test(str) { let stack = new stack(); let start = 0; let maxlen = 0; for(let i=0; i<str.length; i++) { // 如果是左括号,下标入栈 if (str[i] == '(') { stack.push(i); } else { // 如果是右括号 /* 栈内为空,说明本次有效括号匹配已结束,跳过本次循环并更新 start */ if (stack.isempty()) { start = i+1; continue; } else { // 栈内不为空,则出栈一个左括号进行匹配 stack.pop(); // 栈顶元素出栈后,栈为空 if (stack.isempty()) { // 根据当前下标和 start 去更新 maxlen maxlen = math.max(maxlen, i-start+1); } else { // 栈不为空,根据当前下标和栈顶存放的下标去更新 maxlen maxlen = math.max(maxlen, i-stack.peek()); } } } } return maxlen; } test('(()'); // 2 test(')()())'); // 4
终于从大半个月的考试和课设中解放出来了,每天早起晚睡,还是很累的。
如对本文有疑问, 点击进行留言回复!!
轻松解决 org.apache.taglibs.standard.tlv.JstlCoreTLV 困惑
vert实践五——Json?Protocol Buffer?FlatBuffers?
[基于tensorflow的人脸检测] 基于神经网络的人脸检测8——验证训练好的神经网络
selenium + ajax抓取英雄联盟全部英雄的详细信息及多线程保存全部皮肤图片到本地
网友评论