算法學習記錄

題目來源leetcode，持續(xù)更新

學習文檔

動態(tài)規(guī)劃

動態(tài)規(guī)劃詳解

https://juejin.im/post/5e86d0ad6fb9a03c387f3342#heading-3

遞歸與動態(tài)規(guī)劃

https://leetcode-solution.cn/solutionDetail?url=https%3A%2F%2Fapi.github.com%2Frepos%2Fazl397985856%2Fleetcode%2Fcontents%2Fthinkings%2Fdynamic-programming.md

常用算法

遞歸和動態(tài)規(guī)劃

純粹的函數(shù)式編程中沒有循環(huán)，只有遞歸亡鼠。

遞歸

遞歸三要素

一個問題的解可以分解為幾個子問題的解
子問題的求解思路除了規(guī)模之外铁坎，沒有任何區(qū)別
有遞歸終止條件

時間復雜度

……

動態(tài)規(guī)劃

如果說遞歸是從問題的結(jié)果倒推凿掂，直到問題的規(guī)囊挪ぃ縮小到尋常痴荐。那么動態(tài)規(guī)劃就是從尋常入手列肢，逐步擴大規(guī)模到最優(yōu)子結(jié)構(gòu)恰画。

動態(tài)規(guī)劃兩要素

狀態(tài)轉(zhuǎn)移方程
臨界條件

動態(tài)規(guī)劃本質(zhì)上是將大問題轉(zhuǎn)化為小問題，然后大問題的解是和小問題有關(guān)聯(lián)的瓷马，換句話說大問題可以由小問題進行計算得到拴还。

這一點是和遞歸一樣的，但是動態(tài)規(guī)劃是一種類似查表的方法來縮短時間復雜度和空間復雜度欧聘。

解題記錄

前序遍歷

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */

var preorderTraversal = function(root) {
    if (!root) return []
    const stack = [root]
    const result = []
    while(stack.length) {
        const node = stack.pop()
        result.push(node.val) 
        if (node.right) {
            stack.push(node.right)
        }
        if (node.left) {
            stack.push(node.left)
        }
    }
    return result
};

中序遍歷

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    let node = root
    const stack = []
    const result = []
    while(stack.length || node != null) {
        while(node) {
            stack.push(node)
            node = node.left
        }
        node = stack.pop()
        result.push(node.val)
        node = node.right
    }
    return result
};

后序遍歷

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */

// 兩個棧的寫法
var postorderTraversal = function(root) {
    if (!root) return []
    let node = root
    // 任務執(zhí)行棧
    const stack1 = [node];
    // 節(jié)點棧
    const stack2 = [];
    const result = [];
    while (stack1.length) {
        node = stack1.pop();
        stack2.push(node);
        if (node.left !== null) stack1.push(node.left); 
        if (node.right !== null) stack1.push(node.right); 
    }
    while (stack2.length) {
        node = stack2.pop();
        result.push(node.val)
    }
    return result
};

二叉樹最大深度

遞歸

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
// 遞歸
var maxDepth = function(root) {
    if (!root) return 0
    let result = 0
    function getDepth(node, tempDepth) {
        let temp = tempDepth + 1
        if (node.left == null && node.right == null) result = Math.max(temp, result)
        if (node.left !== null) getDepth(node.left, temp)
        if (node.right !== null) getDepth(node.right, temp)
    }
    getDepth(root, 0)
    return result
};

對稱二叉樹

// recursion
// var isSymmetric = function(root) {
//   if (!root) return true
//   function isEqual(left, right) {
//     if (!left || !right) {
//       return left == null && right == null
//     }
//     if (left.val == right.val) {
//       return isEqual(left.left, right.right) && isEqual(left.right, right.left) 
//     }
//     return false
//   }
//   return isEqual(root.left, root.right)
// }

// iteration
var isSymmetric = function(root) {
  if (!root) return true
  const queue = []
  queue.push(root)
  queue.push(root)
  while(queue.length) {
    let n1 = queue.shift()
    let n2 = queue.shift()
    if (n1 === null && n2 === null) continue
    if (n1 === null || n2 === null) return false
    if (n1.val !== n2.val) return false
    queue.push(n1.left)
    queue.push(n2.right)
    queue.push(n1.right)
    queue.push(n2.left)
  }
  return true
}

路徑總和

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */

// recursion
var hasPathSum = function(root, sum) {
  if (!root) return false
  if (root.left === null && root.right === null) {
    return Boolean(sum - root.val == 0)
  }
  return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val)
};

// iteration
var hasPathSum = function(root, sum) {
  if (!root) return false
  cosnt stack = [root]
  while (stack.length) {
    if (root.left === null && root.right === null) {
      return Boolean(sum - root.val == 0)
    }
    if (root.right !== null) {
      stack.push(root.right, sum - root.val)
    }
    
    if (root.left !== null) {
      stack.push(root.left, sum - root.val)
    }
  }
  return false
}

中序與后序遍歷構(gòu)造二叉樹

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */

// recursion
var buildTree = function(inorder, postorder) {
  const helper = (inorder) => {
    if(!inorder.length || !postorder.length) return null
    const value = postorder.pop()
    let index = inorder.indexOf(value)
    let node = new TreeNode(value)
    node.right = helper(inorder.slice(index + 1))
    if (index < 0) {
      node.left = null
    } else {
      node.left = helper(inorder.slice(0, index))
    }
    return node
  }
  return helper(inorder)
};

前序與中序遍歷構(gòu)造二叉樹

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
// recursion
var buildTree = function(preorder, inorder) {
  const helper = (inorder) => {
    if (!inorder.length || !preorder.length) return null
    const value = preorder.shift()
    const index = inorder.indexOf(value)
    if (index < 0) return null
    let node = new TreeNode(value)
    node.left = helper(inorder.slice(0, index))
    node.right = helper(inorder.slice(index + 1))
    return node
  }
  return helper(inorder)
};

填充每個節(jié)點的下一個右側(cè)節(jié)點指針

/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */

/**
 * @param {Node} root
 * @return {Node}
 */
// BFS O(N) O(N)
var connect = function(root) {
  if (!root) return root
  const queue = [root]
  while (queue.length) {
    let pre = null
    let size = queue.length
    for (let i = 0; i < size; i++) {
      let node = queue.shift()
      if (i > 0) pre.next = node
      if (i == size - 1) node.next = null
      pre = node
      if (node.left !== null) queue.push(node.left)
      if (node.right !== null) queue.push(node.right)
    }  
  }
  return root
};

// recursion 遞歸每個子樹寫next; 每個根節(jié)點的LR -> RL; 右側(cè)節(jié)點 -> null
// O(N) O(1)