Js算法与数据结构拾萃（2）

2020 年 2 月 25 日
筆記

关于栈

补白

这是笔者一年前的笔记。在此文中，我们无非是说明了栈的特征：先进后出，后进先出。

尝试使用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/