[失業前端惡補算法]JavaScript leetcode刷題top100（一）

專欄聲明：隻求用最簡單的，容易了解的方法通過，不求優化，不喜勿噴

今天更新五個 easy 難度題目：

兩數之和

• 題面

  給定一個整數數組 nums 和一個整數目标值 target，請你在該數組中找出 和為目标值 target 的那 兩個 整數，并傳回它們的數組下标。你可以假設每種輸入隻會對應一個答案。但是，數組中同一個元素在答案裡不能重複出現。你可以按任意順序傳回答案。

• 知識點：

  哈希表

• 思路

  周遊整個數組，對于每個值，如果 target - x 已經出現過，那麼傳回這組解，否則就把這個目前值存到哈希表中，使用 [ 值：下标 ] 的形式進行存儲

• 代碼

var twoSum = function (nums, target) {

    let hash = {};

    for (var i = 0; i < nums.length; i++) {
        if(typeof hash[target - nums[i]] !== 'undefined'){
            return [hash[target - nums[i]],i];
        }
        hash[nums[i]] = i;
    }

};
           

有效的括号

• 題面

  給定一個隻包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字元串 s ，判斷字元串是否有效。

  有效字元串需滿足：

  左括号必須用相同類型的右括号閉合。

  左括号必須以正确的順序閉合。

  每個右括号都有一個對應的相同類型的左括号。

• 知識點

  棧

• 思路

  遇到左一半的括号就壓入棧中，遇到右一半的括号就判定棧頂元素是不是比對，比對就抛出棧頂元素，根據根據棧中有沒有剩餘沒有比對的元素判定是不是比對

• 代碼

var isValid = function (s) {


    let stack = [];
    for (var i = 0; i < s.length; i++) {
        if(s[i] == ')' && stack[stack.length-1] == '('){
            stack.pop();
        }
        else if(s[i] == '}' && stack[stack.length-1] == '{'){
            stack.pop();
        }
        else if(s[i] == ']' && stack[stack.length-1] == '['){
            stack.pop();
        }else{
            stack.push(s[i]);
        }

    }

    return stack.length == 0;
};
           

合并兩個有序連結清單

• 題面

  将兩個升序連結清單合并為一個新的 升序 連結清單并傳回。新連結清單是通過拼接給定的兩個連結清單的所有節點組成的。

• 知識點

  連結清單操作

• 思路

  建立一個連結清單作為傳回需要，兩個連結清單從頭開始周遊，如果每次将兩個連結清單目前值較大的一個放到新連結清單中，之後放入新連結清單的那一連結清單指向下一個值，直到一個連結清單全部周遊完成，之後将還沒有操作完畢的連結清單連結在新連結清單的尾部。

• 代碼

var mergeTwoLists = function (list1, list2) {
    var a = new ListNode(0, null);
    b = a;

    while (list1 != null && list2 != null) {
        if (list1.val < list2.val) {
            a.next = list1;
            a = a.next;
            list1 = list1.next;
        } else {
            a.next = list2;
            a = a.next;
            list2 = list2.next;
        }
    }

    if( list1 ){
        a.next = list1
    }
    else if( list2 ){
        a.next = list2
    }
    return b.next;
};
           

爬樓梯

• 題面

  假設你正在爬樓梯。需要 n 階你才能到達樓頂。每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？

• 知識點

  動态規劃

• 思路

  對于每一步，他可能從 n-1 到來，或者從 n-2 到來，是以第 n 步的可能方案是第 n-1 和第 n-2 的方案數的和，從 2 開始周遊到 n 步即可

• 代碼

var climbStairs = function (n) {
    let dp = [1, 1];
    for (var i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};
           

二叉樹的中序周遊

• 題面

  給定一個二叉樹的根節點 root ，傳回 它的 中序 周遊 。

• 知識點

  二叉樹，中序周遊

• 思路

  dfs 實作中序周遊，對于每一個節點，如果有左孩子就一直搜尋左孩子，沒有左孩子就輸出節點内容，最後再搜尋二叉樹的右孩子

• 代碼

var inorderTraversal = function (root) {
    let re = [];
    let dfs = (node) => {
        if (!node) {
            return;
        }
        if (node.left) {
            dfs(node.left);
        }
        re.push(node.val);
        if (node.right) {
            dfs(node.right);
        }
    }
    dfs(root);
    return re;
};