共计 18523 个字符，预计需要花费 47 分钟才能阅读完成。
本人基于《算法面试通关 40 讲》所练习，通篇代码示例皆为 javascript 语言。
无关知识点
1. 精通一个领域：
切碎知识点
刻意练习
反馈
2. 切题四件套
审题
所有解法
比较 (时间 / 空间复杂度)
加强
编码
测试用例
http://www.bigocheatsheet.com/
数组，链表
数组 查询：O(1) 插入 O(n) 删除 O(n) 链表 查询：O(n) 插入 O(1) 删除 O(1)
206. 翻转链表 reverse-linked-list
/**
* @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
};
24. 两两翻转链表 Swap Nodes in Pairs
/**
* 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
};
141. 判断链表是否有环 Linked List Cycle
/**
* 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
};
栈，队列
20. 判断合法括号 Valid Parentheses
/**
* @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
};
232. 栈模拟队列 Implement Queue using Stacks
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
}
}
225. 队列模拟栈 Implement Stack using Queues
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}
}
703. 找第 K 大的元素 Kth Largest Element in a Stream
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.length<this.size){
this.data.push(v)
this.minHeap()
}
else if(v>this.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<this.data.length-1){
n= this.n(i)
max=n.v
i=(n.l>=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()
};
239. 滑动窗口最大值 Sliding Window Maximum
/**
* @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.length;$right++,$left++){
if(nums[$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
};
Map Set 哈希表
1. 两数之和 Two Sum
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let res = {}
for (let i=0; i<nums.length; i++) {
let tmp = target – nums[i]
if (nums[i] in res)
return [res[nums[i]] , i]
res[tmp] = i
}
return null
}
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<nums.length-3; i++) {
if (i > 0 && nums[i] === nums[i-1])continue
for (let j=i+1; j<nums.length-2; j++) {
if (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&&lmax<node.val,lmin,node.val]
}
else if(isEmpty(node.left)&!isEmpty(node.right)){
[r,rmin,rmax]=bst(node.right)
return [r&&rmin>node.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&&lmax<node.val&&rmin>node.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]<target:
left=mid+1
else:
right=mid-1
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<n){
str+=’)’
r++
}
ans.push(str)
return
}
get(str,'(‘,l,r,n,ans)
get(str,’)’,l,r,n,ans)
}
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;q<n;q++)
if(!lie.includes(q)&&!pie.includes(p-q)&&!na.includes(p+q))
DFS(lie.concat(q),pie.concat(p-q),na.concat(p+q))
}
DFS([],[],[])
return result.map(o=>o.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<n;q++)
if(!lie.includes(q)&&!pie.includes(p-q)&&!na.includes(p+q))
DFS(lie.concat(q),pie.concat(p-q),na.concat(p+q))
}
DFS([],[],[])
return result
};
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={}
node=node
}
node[‘$’]=true
};
Trie.prototype.search = function(word) {
var node=this.root
for(var c of word)
if(c in node) node=node
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
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<board.length;i++){
for(var j=0;j<board[0].length;j++){
if(!tree.startsWith(board[i][j]))continue
check(board,i,j,tree.root,new Set())
}
}
return Array.from(ans)
};
function check(board,i,j,node,last){
node=node[board[i][j]]
if(!node)return
if(‘$’ in node){ans.add(node[‘$’])}
last.add(`${i},${j}`)
;[[i-1,j],[i,j-1],[i+1,j],[i,j+1]].forEach(v=>{
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<<n)-1)
while(bits>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][1]=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;i<triangle.length;i++){
if(dp[i]===undefined)dp[i]=[]
for(j=0;j<triangle[i].length;j++){
var l=j>0?(+dp[i-1][j-1]+triangle[i][j]):Infinity
var r=(j<triangle[i-1].length)?(+dp[i-1][j]+triangle[i][j]):Infinity
dp[i][j]=Math.min(l,r)
}
}
return Math.min(…dp[i-1])
};
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<nums.length;i++){
var t1=dp[i-1].max*nums[i]
var t2=dp[i-1].min*nums[i]
dp[i]={
min:Math.min(t1,t2,nums[i]),
max:Math.max(t1,t2,nums[i])
}
ans=Math.max(ans,dp[i].max)
}
return ans
};
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<D;i++){
min=Math.min(min,prices[i])
mp[i]=[[0,-min]]
for(k=1;k<(i+1)/2+1&&k<=K;k++)
mp[i][k]=[-Infinity,-Infinity]
}
for(i=1;i<D;i++){
for(k=1;k<=K&&k<=(i+1)/2;k++){
mp[i][k]=[Math.max(mp[i-1][k][0],mp[i-1][k-1][32]+prices[i]),
Math.max(mp[i-1][k][33],mp[i-1][k][0]-prices[i])]
max=Math.max(max,mp[i][k][0])
}
delete mp[i-1]
}
return Math.max(max,0)
};
/**
* @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()
};
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]<this.rank[rooty])
this.parent[rootx]=rooty
else{
this.parent[rooty]=rootx
this.rank[rootx]++
}
this.count–
}
}
}
var numIslands=function(grid){
if (grid.length===0||grid[0].length===0)return 0
let uf=new UnionFind(grid),
directions=[[0,1],[0,-1],[-1,0],[1,0]],
[m,n]=[grid.length,grid[0].length]
for(let i of Array(m).keys())
for(let j of Array(n).keys()){
if(grid[i][j]==0)continue
directions.forEach((d)=>{
let [nr,nc]=[i+d[0],j+d[1]]
if(nr>=0&&nc>=0&&nr<m&&nc<n&&grid[nr][nc]==1)
uf.union(i*n+j,nr*n+nc)
})
}
return uf.count
}
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) }
}
}
