5.2

230. 二叉搜索树中第K小的

/**
 * Definition for b binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(root, k) {
    // 1、递归放在数组，排序即可
    // 2、构建一个大顶堆
    // 然后最后个元素和最顶的交换，维持大顶堆，持续N次。
    var res = []
    var dfs = (root) => {
        if (root === null) return;
        res.push(root.val)
        dfs(root.left)
        dfs(root.right)
    }
    dfs(root)
    res = res.sort((a, b) => a - b)
    return res[k - 1]
};

103. 二叉树的锯齿形层次

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
 // 奇数层往右边，偶数层往左
 // 层次遍历
var zigzagLevelOrder = function(root) {
    let q = [root]
    let res = []
    let level = 1
    if (root === null) {
        return []
    }
    // 当前层
    while(q.length) {
        const len = q.length
        res.push([])
        // 下一层
        for (let j = 0; j < len; j++) {
            const tmp = q.shift()
            res[level - 1] = res[level - 1] || []
            if (level % 2 === 1) {
                res[level - 1].push(tmp.val)
            } else {
                res[level - 1].unshift(tmp.val)
            }
            if (tmp.left) {
                q.push(tmp.left)
            }
            if (tmp.right) {
                q.push(tmp.right)
            }
        }
        level++
    }
    return res
};

剑指 Offer 62. 圆圈中最后剩下的数字

// f(n, m) = (m % n + x) % n = (m + x) % n。?s

62. 不同路径

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
 // 类似爬楼梯
 // dp为从左上角到i，j的数量
 // dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
var uniquePaths = function(m, n) {
    let dp = new Array(m).fill(0).map(_ => new Array(n).fill(0))
    for (let i = 0; i < m; i++) {
        dp[i][0] = 1
    }
    for (let i = 0; i < n; i++) {
        dp[0][i] = 1
    }
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        }
    }
    return dp[m - 1][n - 1]
};

22. 括号生成

146. LRU缓存机制

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.capacity = capacity;
    this.map = new Map();
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
     if(this.map.has(key)){
        let value = this.map.get(key);
        this.map.delete(key); // 删除后，再 set ，相当于更新到 map 最后一位
        this.map.set(key, value);
        return value
    } else {
        return -1
    }
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    // 如果已有，那就要更新，即要先删了再进行后面的 set
    if(this.map.has(key)){
        this.map.delete(key);
    }
    this.map.set(key, value);
    // put 后判断是否超载
    if(this.map.size > this.capacity){
        this.map.delete(this.map.keys().next().value);// 删除最久未使用的key-value（this.map.keys().next().value表示按顺序插入map的第一个key值）
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

2248. 多个数组求交集

// map存数字出现过的次数，，但是要避免单个数组重复
var itersectArray = (args) => {
    var mapData = {}
    var res = []
    args.map((j, index1) => {
        j.map((k, index2) => {
            if (k in mapData) {
                mapData[k]++
            } else {
                mapData[k] = 1
            }  
        })

    })
    for (let j in mapData) {
        if (mapData[j] >= args.length) {
            res.push(j)
        }
    }
    return res;

}
itersectArray([[3,1,2,4,5],[1,2,3,4],[3,4,5,6]])