Js算法与数据结构拾萃（2）
补白
准备阅读： 《javascript数据结构和算法》读书笔记：栈[1]
这是笔者一年前的笔记。在此文中，我们无非是说明了栈的特征：先进后出，后进先出。
尝试使用JavaScript创建一个栈（stack）：
class Stack{
constructor(array=[]){
this.array=array;
}
// 入栈
push(item){
this.array.push(item);
}
// 出栈并返回出栈元素
pop(){
return this.array.pop();
}
// 查看栈顶
peek(){
return this.array[this.array.length-1];
}
// 是否为空
isEmpty(){
return this.array.length==0;
}
// 清栈
clear(){
this.array=[];
}
// 返回栈元素个数
size(){
return this.array.length;
}
// 打印
print(){
console.log(this.array)
}
}【案例1】有效的括号
对应leetcode第20题 难度：简单 https://leetcode.com/problems/valid-parentheses/
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
•Open brackets must be closed by the same type of brackets.•Open brackets must be closed in the correct order.•Note that an empty string is also considered valid.
# Example 1:
Input: "()"
Output: true
# Example 2:
Input: "()[]{}"
Output: true
# Example 3:
Input: "(]"
Output: false
# Example 4:
Input: "([)]"
Output: false
# Example 5:
Input: "{[]}"
Output: true题解：运用栈来解决问题
考虑遍历此字符串，每次遍历做如下判断：
•如果是左开头，入栈•否则：•如果栈不为空，返回false•否则判断栈顶和当前字符是否配对，配对则出栈，不配对则入栈
最后返回的栈是否为空。
/**
* @param {string} s
* @return {boolean}
*/
// Stack
const isValid = (s) => {
const stack=new Stack([]);
// 定义字典
const isCouple=(l,r)=>{
if((l=='('&&r==')')||(l=='['&&r==']')||(l=='{'&&r=='}')){
return true;
}
return false
}
for(let i=0;i<s.length;i++){
if(s[i]=='('||s[i]=='['||s[i]=='{'){
stack.push(s[i]);
}else{
if(stack.isEmpty()){
return false;
}else{
if(isCouple(stack.peek(),s[i])){
stack.pop();
}else{
stack.push(s[i]);
} }
}
}
return stack.isEmpty();
};
变化图
运行效率还有可以调优的地方。主要在于减少无谓的if else判读。
如果不显式声明栈，这种方法来判断或是比较优雅很多
const isValid = (s) => {
const stack = [];
// 定义字典
const couple = {
'(': ')',
'[': ']',
'{': '}'
}
for (let i = 0; i < s.length; i++) {
if (s[i] in couple) {
stack.push(s[i]);
} else {
if (couple[stack.pop()]!=s[i]) {
return false;
}
}
}
return !stack.length;
};
【案例2】简单路径
对应leetcode 71题 难度：中等 https://leetcode.com/problems/simplify-path/
Given an absolute path for a file (Unix-style), simplify it. Or in other words, convert it to the canonical path.
In a UNIX-style file system, a period . refers to the current directory. Furthermore, a double period .. moves the directory up a level. For more information, see: Absolute path vs relative path in Linux/Unix[2]
Note that the returned canonical path must always begin with a slash /, and there must be only a single slash / between two directory names. The last directory name (if it exists) must not end with a trailing /. Also, the canonical path must be the shortest string representing the absolute path.
以 Unix 风格给出一个文件的绝对路径，简化它——也就是说，将其转换为规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。
请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。
示例 1：
输入："/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。示例 2：
输入："/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。示例 3：
输入："/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。示例 4：
输入："/a/./b/../../c/"
输出："/c"示例 5：
输入："/a/../../b/../c//.//"
输出："/c"示例 6：
输入："/a//b////c/d//././/.."
输出："/a/b/c"经常用nodeJs的话，会对unix路径比较熟悉。简单说：
•/开头代表跟路径•../，..表示当前目录向上•./表示当前目录
在node环境下，可以使用
const path = require('path');
const simplifyPath = (path) => {
return Path.resolve(path)
};但是测试环境并不支持node，需要你自己来做。
题解
先把字符用/生成数组考虑出栈和入栈的时机。..表示向上，.和空字符串都不操作。其它入栈即可。
/**
* @param {string} path
* @return {string}
*/
const simplifyPath = (path) => {
let pathArr = path.split('/');
const stack = [];
for (let i = 0; i < pathArr.length; i++) {
switch (pathArr[i]) {
case '..':
// 向上一级
if (stack.length!=0) {
stack.pop();
}
break;
case '.':
// 当前目录
case '':
break;
default:
stack.push(pathArr[i].replace(/\//g,''))
break;
}
}
return '/'+stack.join('/');
};
References
[1] 《javascript数据结构和算法》读书笔记：栈: http://mp.weixin.qq.com/s?__biz=MzIxMDQ2NjUwNg==&mid=2247483810&idx=1&sn=40d27b7c8e20b9820f69022e9ccc3ee4&chksm=97656207a012eb11e276094cd6c8cd8b2fdca9eb80a4ba00c16ede69b58e2a30bc3ce29b2c0a&token=1334209442&lang=zh_CN#rd
[2] Absolute path vs relative path in Linux/Unix: https://www.linuxnix.com/abslute-path-vs-relative-path-in-linuxunix/