FE-ES 刷leedcode一周速记

共计 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]

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

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[]}
*/

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

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

FE-ES 刷leedcode一周速记

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）