FE-ES 前端数据结构与算法leedcode训练合集40题

摘要：无关知识点精通一个领域切碎知识点刻意练习反馈切题四件套审题所有解法比较时间空间复杂度加强编码测试用例数组，链表数组查询插入删除链表查询插入删除翻转链表两两翻转链表判断链表是否有环栈，队列判断合法括号栈模拟队列队列模拟栈找第大的元素

1.精通一个领域：

切碎知识点

刻意练习

反馈

2.切题四件套

审题

所有解法

比较(时间/空间复杂度)

加强

编码

测试用例

http://www.bigocheatsheet.com/

数组 查询：O(1)插入 O(n) 删除O(n)
链表 查询：O(n)插入 O(1) 删除O(1)

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    var [prev,curr]=[null,head]
    while(curr){
        [curr.next,curr,prev]=[prev,curr.next,curr]
    }
    return prev
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    if(!head||!head.next)return head
    var c,a=head,$head=b=head.next
    while(a&&b){
        c=b.next
        a.next=(c&&c.next)||c
        b.next=a
        a=c
        b=a&&a.next
    }
    return $head
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
if (!head || !head.next) return false
    var slow = head,fast = head.next
    while(fast.next && fast.next.next) {
        slow = slow.next
        fast = fast.next.next
        if (slow == fast) return true
    }
    return false
};

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    var arr=[],s=s.split(""),t
    while(t=s.shift())
        if(["{","[","("].includes(t))
            arr.push(t)
        else if(!["[]","()","{}"].includes(arr.pop()+t))
            return false
    return arr.length==0
};

class MyQueue{
    constructor(){
        this.stackIn=[]
        this.stackOut=[]   
    }
    push(x){
        this.stackIn.push(x)
    }
    pop(){
        var t,$r
        while(t=this.stackIn.pop())this.stackOut.push(t)
        $r=this.stackOut.pop()
        while(t=this.stackOut.pop())this.stackIn.push(t)
        return $r
    }
    peek() {
        var t,$r
        while(t=this.stackIn.pop())this.stackOut.push(t)
        $r=this.stackOut.pop()
        this.stackOut.push($r)
        while(t=this.stackOut.pop())this.stackIn.push(t)
        return $r
    }
    empty() {
        return this.stackIn.length==0
    }
}

class MyStack {
    constructor(){
        this.qIn=[]
        this.qOut=[]   
    }
    push(x){this.qIn.push(x)}
    pop() {
        var t
        while(this.qIn.length>1){
            t=this.qIn.shift()
            this.qOut.push(t)
        }
        var $r=this.qIn.shift()
        while(this.qOut.length){
            t=this.qOut.shift()
            this.qIn.push(t)
        }
        return $r
    }
    top() {
        var t
        while(this.qIn.length>1){
            t=this.qIn.shift()
            this.qOut.push(t)
        }
        var $r=this.qIn.shift()
        this.qOut.push($r)
        while(this.qOut.length){
            t=this.qOut.shift()
            this.qIn.push(t)
        }
        return $r
    }
    empty() {return this.qIn.length===0}
}

class tree{
    constructor(data,k){this.data=data;this.size=k}
    n(i,v){
        if(v!==undefined)this.data[i]=v;return;
        return {
            $i:i,           $l:2*i+1,           $r:2*i+2,
            v:this.data[i], l:this.data[2*i+1], r:this.data[2*i+2]}
    }
    add(v){
        if(this.data.lengththis.min()){
            this.n(0,v)
            this.sort(0)
        }
    }
    min(){return this.data[0]!==undefined?this.data[0]:null}
    max(){
        var i=0,n,max;
        while(i=n.r)?n.$l:n.$r
        }
        return max
    }
    minHeap(){
        var i=parseInt(this.data.length/2)
        for(;i>=0;i--)this.sort(i)
    }
    sort(i){
        var n=this.n(i)
        if(n.l===undefined)return
        var min=Math.min(n.v,n.l,n.r!==undefined?n.r:Infinity)
        switch(min){
            case n.l:
                this.n(n.$i,n.l);this.n(n.$l,n.v);this.sort(n.$l);break;
            case n.r:
                this.n(n.$i,n.r);this.n(n.$r,n.v);this.sort(n.$r);break;
        }
    }
}
/**
 * @param {number} k
 * @param {number[]} nums
 */
var KthLargest = function(k, nums) {
    this.tree=new tree(nums.splice(0,k),k)
    this.tree.minHeap()
    while(nums.length)
        this.tree.add(nums.pop())
}

KthLargest.prototype.add = function(val) {
    this.tree.add(val)
    return this.tree.min()
};

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    if(!nums.length){return nums}
    var tmp=nums.slice(0,k),    res=[nums[$max]],
        $max=tmp.lastIndexOf(Math.max(...tmp)),
        $left=1,    $right=k
    for(;$right=nums[$max])
            $max=$right
        else if($max===$left-1){
            tmp=nums.slice($left,$right+1)
            $max=$left+tmp.lastIndexOf(Math.max(...tmp))
        }
        res.push(nums[$max])
    }
    return res
};

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let res = {}
    for (let i=0; i
15. 三数之和 3Sum
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    var result = []
    nums.sort((a, b)=>a - b)
    var end, middle, sum, tripplet, set = new Set()
    for (var start = 0; start < nums.length - 2; start++) {
        if (start > 0 && nums[start] == nums[start-1])continue
        end = nums.length - 1
        middle = start + 1
        while (middle < end) {
            sum = nums[start] + nums[middle] + nums[end]
            if (sum === 0) {
                tripplet = [nums[start], nums[middle], nums[end]];
                trippletKey = nums[start]+ ":" +nums[middle]+ ":" +nums[end]
                if (!set.has(trippletKey)) {
                    set.add(trippletKey)
                    result.push(tripplet)
                }
                while (middle < end && nums[middle] === nums[middle+1])middle++
                while (middle < end && nums[end] === nums[end-1])end--
                middle++
                end--
            }
            else (sum > 0) ? end-- : middle++
        }
    }
    return result
};
18. 四数之和 4Sum
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
    const result = [];
    nums.sort((a, b) => a - b);
    for (let i=0; i 0 && nums[i] === nums[i-1])continue
        for (let j=i+1; j i + 1 && nums[j] === nums[j-1])continue
            if (nums[i] + nums[j] + nums[j+1] + nums[j+2] > target)break
            if (nums[i] + nums[j] + nums[nums.length-2] + nums[nums.length-1] < target)continue
            let left = j + 1, right = nums.length - 1
            while (left < right) {
                const sum = nums[i] + nums[j] + nums[left] + nums[right]
                if (sum === target) {
                    result.push([ nums[i], nums[j], nums[left], nums[right] ])
                    while (nums[left] === nums[left+1] && left < right)left++
                    while (nums[right] === nums[right-1] && left < right)right--
                    left++
                    right--
                }
                else if (sum < target) left++
                else right--
            }
        }
    }
    return result
}
树
98. 验证二叉搜索树 Validate Binary Search Tree
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isEmpty=(node)=>node===null||node.val===null
var isValidBST = (root) =>isEmpty(root)?true:(bst(root))[0]

function bst(node){
    var l,r,lmin,lmax,rmin,rmax
    if(isEmpty(node.right)&&!isEmpty(node.left)){
        [l,lmin,lmax]=bst(node.left)
        return  [l&&lmaxnode.val,node.val,rmax]
    }
    else if((!isEmpty(node.left))&&(!isEmpty(node.right))){
        [l,lmin,lmax]=bst(node.left)
        [r,rmin,rmax]=bst(node.right)
        return [l&&r&&lmaxnode.val,lmin,rmax]
    }
    else return [true,node.val,node.val]
}
235. 二叉搜索树最近公共祖先 Lowest Common Ancestor of a Binary Search Tree
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    if(root===null||root===p||root===q)return root
    var l=lowestCommonAncestor(root.left,p,q)
    var r=lowestCommonAncestor(root.right,p,q)
    return l&&r&&root||l||r
};
236. 二叉树最近公共祖先 Lowest Common Ancestor of a Binary Tree
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var empty=node=>node===null||node.val===null
var lowestCommonAncestor = function(root, p, q) {
    var l,r
    if(empty(root)||root===p||root===q)return root
    l=lowestCommonAncestor(root.left,p,q)
    r=lowestCommonAncestor(root.right,p,q)
    return l&&r&&root||l||r
}
二叉树遍历&递归分治
递归四步
function recursion(level,data){
//recursion termonator
    if level>MAX_LEVEL
        return result
//process logic in current level
    process_data(level,data)
//drill down
    recursion(level+1,data1)
//reverse the current level
    reverse_state(level)
}
DFS
visited=set()
def dfs(node,visited):
    visited.add(node)
    #...
    for next_node in node.children():
        if not next_ndoe in visited:
            dfs(next_node,visited)
BFS
def BFS(graph,start,end)
    queue=[]
    queue.append([start])
    visited.add(start)

    while queue:
        node=queue.pop()
        visited.add(node)

        process(node)
        nodes=genertate_related_nodes(node)
        queue.push(nodes)
二分查找
let,right=0,len(array)-1
while left<=right:
    mid=left+(right-left)/2
    if array[mid]==target:
        #find the target!!
        break or return result
    elif array[mid]
50. 次方 Pow(x, n)
/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    if(!n)return 1
    if(n<0)return 1/myPow(x,-n)
    if(n%2)return x*myPow(x,n-1)
    return myPow(x*x,n/2)
};
var myPow = function(x, n) {
    if(n<0){
        x=1/x
        n=-n
    }
    var pow=1
    while(n){
        if(n&1)pow*=x
        x*=x
        n=parseInt(n/2)
    }
    return pow
};
169. 求众数 Majority Element
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let major = nums[0],count = 1
    for (let i = 1; i < nums.length; i++) {
        if (major === nums[i]) count++
        else count--
        if (count === 0) {
            major = nums[i]
            count = 1
        }
    }
    return major
};
102. 二叉树层次遍历 Binary Tree Level Order Traversal
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if(isEmpty(root))return []
    var h=0,isEnd=false,ans=[[root.val]]
    print(root,h,ans)
    return ans
};

var isEmpty=root=>root===null||root.val===null

function print(root,h,ans){
    h++
    if(!isEmpty(root.left)){
        ans[h]=ans[h]||[],ans[h].push(root.left.val)
        print(root.left,h,ans)
    }
    if(!isEmpty(root.right)){
        ans[h]=ans[h]||[],ans[h].push(root.right.val)
        print(root.right,h,ans)
    }
}
var levelOrder = function(root) {
    if (!root) return []
    const queue = [[root,0]]
    const result = []
    while (queue.length !== 0) {
        const [node, level] = queue.shift()
        if (level >= result.length) result.push([])
        result[level].push(node.val)
        if (node.left){
            const left = [node.left,level + 1]
            queue.push(left)}
        if (node.right){
            const right = [node.right,level + 1]
            queue.push(right)}
    }
    return result
}
104. 二叉树最大深度 Maximum Depth of Binary Tree
/**
 * 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,h=0) {
    if(!root)return h
    h++
    return Math.max(maxDepth(root.left,h),maxDepth(root.right,h))
};
var maxDepth = function(root,h=0) {
    var h=0,nodes=[[null,0]]
    while(root&&root.val){
        h++
        if(root.right) nodes.push([root.right,h+1])
        if(root.left){
            root=root.left
            h++
        }
        else [root,h]=nodes.pop()
    }
    return h
};
111. 二叉树最小深度 Minimum Depth of Binary Tree
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {
    if(root===null)return 0
    if(root.right===null){
        return minDepth(root.left)+1
    }
    if(root.left==null){
        return minDepth(root.right)+1
    }
    return Math.min(minDepth(root.left),minDepth(root.right))+1
};
const currentNode = (node, depth) => ({node,depth})

var minDepth = function(root){
  if(root === null)return 0
  const q = []
  q.push(currentNode(root, 1))
  while(q.length){
    let { node, depth } = q.shift()
    if(!node.left && !node.right) return depth
    else {
      node.left && q.push(currentNode(node.left, depth + 1))
      node.right && q.push(currentNode(node.right, depth + 1))
    }
  }
}
剪枝
22. 生成括号 Generate Parentheses
var generateParenthesis = function(n) {
    if(n===1)return ["()"]
    var l=1,r=0,ans=[],str="("
    get(str,"(",l,r,n,ans)
    get(str,")",l,r,n,ans)
    return ans
}
function get(str,char,l,r,n,ans){
    if(char===")"&&l===r)return
    str+=char
    if(char==="(")l++ 
    else r++
    if(l===n){
        while(r
51.N皇后 N-Queens
/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {
    var result=[]
    function DFS(lie,pie,na){
        var p=lie.length
        if(p===n){result.push(lie);return}
        for(var q=0;qo.map(v=>{
        var s=".".repeat(n).split("")
        s[v]="Q"
        return s.join("")
    }))
}
52. N皇后II N-Queens II
/**
 * @param {number} n
 * @return {number}
 */
var totalNQueens = function(n) {
    var result=0
    function DFS(lie,pie,na){
        var p=lie.length
        if(p===n){result++;return}
        for(var q=0;q
37. 数独 Sudoku Solver
/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function(board) {
    if(board===null||board.length===0)return
    return solve(board)
}

function solve(board){
    for(var i=0;i<9;i++){
        for(var j=0;j<9;j++){
            if(board[i][j]=="."){
                for(var c=1;c<=9;c++){
                    if(isValid(board,i,j,c)){
                        board[i][j]=""+c
                        if(solve(board))return true
                        else board[i][j]="."
                    }
                }
                return false
            }
        }
    }
    return board
}

function isValid(board,row,col,c){
    var _col=parseInt(col/3)
    var _row=parseInt(row/3)
    for(var i=0;i<9;i++){
        var _i=parseInt(i/3)
        if( [board[i][col],
             board[row][i],
             board[3*_row+_i][3*_col+i%3]
            ].some(v=>v!="."&&v==c))return false
    }
    return true
}
208. 字典树 Implement Trie (Prefix Tree)
var Trie = function() {
    this.root={}
};

Trie.prototype.insert = function(word) {
    var node=this.root
    for(var c of word){
        if(!(c in node))
            node[c]={}
        node=node[c]
    }
    node["$"]=true
};

Trie.prototype.search = function(word) {
    var node=this.root
    for(var c of word)
        if(c in node) node=node[c]
        else return false
    return node["$"]===true
};

Trie.prototype.startsWith = function(prefix) {
    var node=this.root
    for(var c of prefix)
        if(c in node) node=node[c]
        else return false
    return true
};
212. 单词搜索 Word Search II
/**
 * @param {character[][]} board
 * @param {string[]} words
 * @return {string[]}
 */

var findWords = function(board, words) {
    var tree=new Trie()
    global.ans=new Set()
    words.forEach(v=>{tree.insert(v)})
    for(var i=0;i{
        if(v[0]<0||v[0]>=board.length||v[1]<0||v[1]>=board[0].length)return
        var index=v.join(",")
        if(!last.has(index)){
            check(board,v[0],v[1],node,new Set(last))
        }
    })
}
位运算
概要

X&1==1 or 0 判断奇偶
X=X&(X-1) 清零最低位的1
X&-X 得到最低位的1

191. 1的个数 Number of 1 Bits
/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function(n) {
    var count=0
    while(n){
        n=n&(n-1)
        count++
    }
    return count
};
231.二的次方 Power of Two
/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfTwo = (n)=>n > 0 && !(n & (n - 1))
52.N皇后位运算 N-Queens II
/**
 * @param {number} n
 * @return {number}
 */
var totalNQueens = function(n) {
    var result=0
    function DFS(hang,lie,pie,na){
        if(hang>=n){result++;return}
        var bits=(~(lie|pie|na))&((1<0){
            var p=bits&-bits
            DFS(hang+1,lie|p,(pie|p)<<1,(na|p)>>1)
            bits&=bits-1
        }
    }
    DFS(0,0,0,0)
    return result
}
动态规划
模板
dp=new init [m+1][n+1]
dp[0][0]=x
dp[0][28]=y

for i=0;i<=n;++i
    for j=0;j<=m;++j
        #...
        dp[i][j]=min(dp[i-1][j],dp[i][j-1])
return dp[m][n]
70. 爬楼梯 Climbing Stairs
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    dp=[0,1,2]
    for(var i=3;i<=n;i++){
        dp[i]=dp[i-1]+dp[i-2]
    }
    return dp[n]
};
120. 三角形最小路径和 Triangle
/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
    var dp=[[+triangle[0][0]]]
    var i,j
    for(i=1;i0?(+dp[i-1][j-1]+triangle[i][j]):Infinity
            var r=(j
152. 乘积最大子序列 Maximum Product Subarray
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function(nums) {
    var i,dp=[{min:nums[0],max:nums[0]}],ans=nums[0]
    for(i=1;i
188. 股票交易最优决策 Best Time to Buy and Sell Stock IV
var maxProfit = function(K, prices) {
    var D=prices.length,mp=[],k,i
        max=-Infinity,min=prices[0]
    if(!D||!K)return 0
    if(K>=D/2){
        max=0
        for(i = 1; i < prices.length; i++)
            if(prices[i] > prices[i-1])
                max += (prices[i] - prices[i-1])
        return max
    }
    for(i=0;i
/**
 * @param {number} k
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(k, prices) {
    var n=prices.length
    var k = Math.min(k,n)
    if (!k)return 0
    if(k>=n/2){
        let max=0
        for(i = 1; i < n; i++)
            if(prices[i] > prices[i-1])
                max += (prices[i] - prices[i-1])
        return max
    }
    let dp = Array(n).fill(0)
    while (k) {
        dp[0] = -prices[0]
        for (let i = 1; i < n; i++) 
            dp[i] = Math.max(dp[i - 1], dp[i] - prices[i])
        dp[0] = 0
        for (let i = 1; i < n; i++) 
            dp[i] = Math.max(dp[i - 1], prices[i] + dp[i])
        k--
    }
    return dp.pop()
};
300.最大上升子序列 Longest Increasing Subsequence
/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    if(!nums||!nums.length)return 0
    var res=1
    var dp=new Array(nums.length-1)
    for(var i=0;i
322.零钱兑换 Coin Change
/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    var i,j,dp=[0]
    if(amount===0)return 0
    for(var i=1;i<=amount;i++){
        var res=[]
        for(var j=0;j0)
            dp[i]=Math.min(...res)+1
    }
    return dp[amount]||-1

};
72. 编辑距离 Edit Distance
/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function(word1, word2) {
    if(!word1.length)return word2.length
    if(!word2.length)return word1.length
    var dp=Array.from(Array(word1.length+1), () =>
                      Array(word2.length+1).fill(0))
    for(i of Array(word1.length+1).keys())
        dp[i][0]=i
    for(j of Array(word2.length+1).keys())
        dp[0][j]=j
    
    for(var i=1;i<=word1.length;i++)
        for(var j=1;j<=word2.length;j++)
            dp[i][j]=Math.min(dp[i-1][j]+1,
                              dp[i][j-1]+1,
                              dp[i-1][j-1]+(word1[i-1]===word2[j-1]?0:1))
    return dp.pop().pop()
};
并查集
200 岛屿个数 Number of Islands
/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    let count = 0,
        h = grid.length,
        w = h && grid[0].length
    for(let i of Array(h).keys())
        for(let j of Array(w).keys()){
            if(grid[i][j] === "0") continue
            count ++
            dfs(i, j)
        }
    return count
    
    function dfs(n, m){
        if(n < 0 || m < 0 || n >= h || m >= w) return;
        if(grid[n][m] === "1"){
            grid[n][m] = "0";
            dfs(n + 1, m);
            dfs(n - 1, m);
            dfs(n, m + 1);
            dfs(n, m - 1);
        }
    }
}
class UnionFind{
    constructor(grid){
        let [m,n]=[grid.length,grid[0].length]
        this.count=0
        this.parent=Array(m*n).fill(-1)
        this.rank=Array(m*n).fill(0)
        for(let i of Array(m).keys())
            for(let j of Array(n).keys())
                if(grid[i][j]=="1"){
                    this.parent[i*n+j]=i*n+j
                    this.count++
                }
    }
    find(i){
        if (this.parent[i]!=i)
            this.parent[i]=this.find(this.parent[i])
        return this.parent[i]
    }
    union(x,y){
        let rootx=this.find(x)
        let rooty=this.find(y)
        if(rootx!=rooty){
            if(this.rank[rootx]>this.rank[rooty])
                this.parent[rooty]=rootx
            else if(this.rank[rootx]{
                let [nr,nc]=[i+d[0],j+d[1]]
                if(nr>=0&&nc>=0&&nr
547. 朋友圈 Friend Circles
/**
 * @param {number[][]} M
 * @return {number}
 */
var findCircleNum=function(M){
    const n = M.length
    const roots = Array.from(Array(n).keys())

    for (let i = 0; i < n; i++) 
        for (let j = i+1; j < n; j++) 
            if (M[i][j] === 1) {
                const [x, y] = [find(i), find(j)]
                if (x !== y) roots[y] = x
            }
    let result = new Set()
    for (let i = 0; i < roots.length; i++) result.add(find(roots[i]))
    return result.size

    function find(x) {
        while(roots[x] !== x) x = roots[x]
        return x
    }
}
146.最近最少使用缓存 LRU Cache
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
  }

  get(key) {
    let val = this.map.get(key);
    if (typeof val === "undefined") { return -1 }
    this.map.delete(key);
    this.map.set(key, val);
    return val;
  }

  put(key, value) {
    if (this.map.has(key)) { this.map.delete(key) }
    this.map.set(key, value);
    let keys = this.map.keys();
    while (this.map.size > this.capacity) { this.map.delete(keys.next().value) }
  }
}