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) }
  }
}