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/