持续更新...
338. 比特位计数
- 循环遍历[0, num]，按位与得出1的个数，复杂度是O(n * k)，k是每个数字的二进制位数。
var countBits = function(num) {
const res = []
const getBinaryOne = (n) => {
let sum = 0
while(n) {
sum += n & 1
n >>= 1
}
return sum
}
for(let i=0;i<=num;i++) {
res.push(getBinaryOne(i))
}
return res
};
- 在Leetcode的官方题解中提及到三种动态规划方法，都是利用差不多的状态转移方程进行的，这里记录兼具代码实现简单和思想简洁的动态规划+最低有效位方法。方便在面试之类的情况下快速回忆。这些动态规划代码的复杂度都是O(n)。
算法思想：
十进制 -> 二进制
605 -> 1001011101
302 -> 100101110
非常直观的看出：605的"1"的个数比302多1，而1是605的最低位数字。而且：
605 = 302 * 2 + 1
而且根据二进制特性302 * 2^n，1的个数是不变的，所以可以得出状态转移方程：
P(x) = P(x/2) + x%2
var countBits = function(num) {
const res = [0]
for(let i=1;i<=num;i++) {
res[i] = res[Math.floor(i/2)] + i%2
}
return res
};
46. 全排列
直观的回溯法，没有任何优化，时间复杂度和空间复杂度都是O(N!)
var permute = function(nums) {
const resArr = []
const per = (arr, res) => {
if(!arr.length) {
resArr.push(res)
return
}
for(let i=0;i<arr.length;i++) {
let arrCopy = [...arr]
let resCopy = [...res]
resCopy.push(arrCopy.splice(i,1))
per(arrCopy,resCopy)
}
}
per(nums, [])
return resArr
};
22. 括号生成
- 借助了之前用栈检验括号有效性的思想的回溯法。边想边写的，时间空间复杂度不好，但是容易理解，贴上来给大家看看。
var generateParenthesis = function(n) {
/**
* 回溯剪枝
*/
const resArr = []
const func = (arr, stack, left, right) => {
// 收入条件 - 左右为空
if(left === 0 && right === 0) {
resArr.push(arr.join(''))
return
}
// 左括号进入
if(left > 0) {
func([...arr,'('], [...stack, '('], left-1, right)
}
// 右括号进入
if(right > 0) {
// 栈内为空不能进栈
if(stack.length === 0) return
stack.pop()
func([...arr, ')'], [...stack], left, right-1)
}
}
func([],[],n,n)
return resArr
};
- 用下标来优化的回溯法。并且把上面的进栈出栈操作简化为一个逻辑：只要左括号数量比右括号多就可以进右括号。
var generateParenthesis = function(n) {
const resArr = []
const backtrack = (cur, left, right) => {
if(left===0 && right===0) {
resArr.push(cur)
return
}
if(left>0) {
backtrack(cur+'(', left-1, right)
}
if(right>left){
backtrack(cur+')', left, right-1)
}
}
backtrack('',n,n)
return resArr
}
94. 二叉树的中序遍历
递归
var inorderTraversal = function(root) {
const res = []
const mid = (node) => {
if(!node) {
return
}
node.left && mid(node.left)
res.push(node.val)
node.right && mid(node.right)
}
mid(root)
return res
};
改为迭代法
var inorderTraversal = function(root) {
const res = []
const stack = []
let node = root
while(node !== null || stack.length) {
while(node !== null) {
stack.push(node)
node = node.left
}
node = stack.pop()
res.push(node.val)
node = node.right
}
return res
};
39. 组合总和
var combinationSum = function(candidates, target) {
const res = []
const back = (start, arr, sum) => {
if(sum === target) {
res.push(arr)
return
}
for(let i=start;i<candidates.length;i++) {
if(sum+candidates[i]<=target) {
let arrCopy = [...arr, candidates[i]]
back(i, arrCopy, sum+candidates[i])
}
}
}
back(0, [], 0)
return res
};
114. 二叉树展开为链表
参考的是第一个题解的做法。
var flatten = function(root) {
while(root) {
if(!root.left) {
root = root.right
} else {
let prev = root.left
while(prev.right) {
prev = prev.right
}
prev.right = root.right
root.right = root.left
root.left = null
}
}
};
递归版的采用了后序遍历，以后补充
48. 旋转图像
O(N^2) 时间复杂度的转置+逆序方法。
var rotate = function(matrix) {
// 转置+逆序
const n = matrix.length
for(let i=0;i<n;i++) {
for(let j=i+1;j<n;j++) {
let tmp = matrix[i][j]
matrix[i][j] = matrix[j][i]
matrix[j][i] = tmp
}
}
matrix.forEach(arr => arr.reverse())
};
287. 寻找重复数
第一反应是哈希表，空间O(n)时间O(n)
var findDuplicate = function(nums) {
const map = new Map()
for(let n of nums) {
if(map.get(n)) {
return n
}
map.set(n, true)
}
};
残念的是空间复杂度要求O(1)，时间复杂度小于O(N^2)，并且要求不能更改原数组【排序也被排除O(nlogn)，如果使用了非in-place排序，空间复杂度也不合格】
这里用到的方法其实是之前的环形链表题目！因为数组大小位于区间[1,n]，数组长度为n+1，所以以数组值为数组的下标，可以进行类似链表的跳转。如果存在重复元素，会形成一个环，采用快慢指针来解就很舒服了。
var findDuplicate = function(nums) {
let slow = nums[0]
let fast = nums[nums[0]]
while(slow!==fast) {
slow = nums[slow]
fast = nums[nums[fast]]
}
let prev1 = 0
let prev2 = slow
while(prev1!==prev2) {
prev1 = nums[prev1]
prev2 = nums[prev2]
}
return prev1
};
96. 不同的二叉搜索树
var numTrees = function(n) {
/**
* 非常好的动态规划题，并且可以当卡特兰数的入门题目，详见官方题解
* G(n) = SUM i:0->n (F(i,n))
* F(i,n) = G(i-1) * G(n-i)
* G(n) = SUM i:0->n (G(i-1)*G(n-i))
* G(0) = 1
* G(1) = 1
*/
const dp = Array(n+1).fill(0)
dp[0] = 1
dp[1] = 1
for(let i=2;i<=n;i++) {
// 为什么采用二层循环？由于G(n-i)的结果可能超出动态规划辅助数组，因此我们先限制n的范围，由小到大，从G(2)求到G(n)。
for(let j=1;j<=i;j++) {
dp[i] += dp[j-1]*dp[i-j]
}
}
return dp[n]
};
var numTrees = function(n) {
/**
* 卡特兰数解法
* 有关卡特兰数的题目和适用范围：https://blog.csdn.net/zkp_987/article/details/94565351
* C(n+1) = 2(2n+1)/n+2 * C
* C(0) = 1
*/
let c = 1
for(let i=0;i<n;i++) {
c = 2*(2*i+1)*c /(i+2)
}
return c
};
64. 最小路径和
var minPathSum = function(grid) {
const n = grid.length
const m = grid[0].length
for(let i=n-1;i>=0;i--){
for(let j=m-1;j>=0;j--) {
if(i === n-1 && j !== m-1) {
grid[i][j] = grid[i][j+1] + grid[i][j]
} else if(i !== n-1 && j === m-1) {
grid[i][j] = grid[i+1][j] + grid[i][j]
} else if(i !== n-1 && j !== m-1) {
grid[i][j] = grid[i][j] + Math.min(grid[i+1][j], grid[i][j+1])
}
}
}
return grid[0][0]
}
208. 实现 Trie (前缀树)
class TrieNode {
constructor () {
this.isEnd = false
this.links = Array(26)
}
containsKey(ch) {
return Boolean(this.links[ch.charCodeAt() - 'a'.charCodeAt()])
}
getNode(ch) {
return this.links[ch.charCodeAt() - 'a'.charCodeAt()]
}
putNode(ch, node) {
this.links[ch.charCodeAt() - 'a'.charCodeAt()] = node
}
setEnd() {
this.isEnd = true
}
}
class Trie {
constructor () {
this.root = new TrieNode()
}
insert(word) {
let node = this.root
for(const c of word) {
if(!node.containsKey(c)) {
node.putNode(c, new TrieNode())
}
node = node.getNode(c)
}
node.setEnd()
}
searchPrefix(word) {
let node = this.root
for(const c of word) {
if(node.containsKey(c)) {
node = node.getNode(c)
} else {
return null
}
}
return node
}
search(word) {
let node = this.searchPrefix(word)
return node !== null && node.isEnd
}
startsWith(prefix) {
let node = this.searchPrefix(prefix)
return node !== null
}
}
105. 从前序与中序遍历序列构造二叉树
用了很多数组的API，性能不行，但是方便快速理解和写出代码。
var buildTree = function(preorder, inorder) {
/**
* 先序数组元素 - 中间节点
* 中序数组元素用中序数组元素可以分为两半，左为左子树，右为右子树
*/
const recBuild = (po,io) => {
if(!po.length) {
return null
}
const mid = po.shift()
if(!po.length) {
return new TreeNode(mid)
}
const midPos = io.indexOf(mid)
const leftIo = io.slice(0,midPos)
const rightIo = io.slice(midPos+1)
const leftPo = po.slice(0,midPos)
const rightPo = po.slice(midPos)
delete po
delete io
const node = new TreeNode(mid)
node.left = recBuild(leftPo, leftIo)
node.right = recBuild(rightPo, rightIo)
return node
}
return recBuild(preorder, inorder)
};
使用参数下标，性能较好
var buildTree = function(preorder, inorder) {
/**
* 其实 这个build的过程本身就是一个先序遍历，因此只需要设置一个全局自增的Index就能走先序遍历的过程了
* 所以 目前需要的下标就是中序遍历的left和right部分
*/
let index = 0
const inorderMap = new Map()
for(let i=0;i<inorder.length;i++) {
inorderMap.set(inorder[i], i)
}
const recBuild = (inLeft, inRight) => {
if(inLeft === inRight) {
return null
}
const rootVal = preorder[index]
const root = new TreeNode(rootVal)
const inorderIndex = inorderMap.get(rootVal)
index++
root.left = recBuild(inLeft, inorderIndex)
root.right = recBuild(inorderIndex+1, inRight)
return root
}
return recBuild(0, inorder.length)
};
148. 排序链表
归并排序的用在链表这里刚刚好，因为它只需要中点坐标就可以。
var sortList = function(head) {
if(!head || !head.next) return head
let slow = head, fast = head.next
while(fast && fast.next) {
slow = slow.next
fast = fast.next.next
}
let mid = slow.next // 就是中点的右侧,右部分的头指针
slow.next = null
let left = sortList(head)
let right = sortList(mid)
const h = new ListNode('head')
let p = h
while(left && right) {
if(left.val < right.val) {
p.next = left
left = left.next
} else if(left.val >= right.val) {
p.next = right
right = right.next
}
p = p.next
}
p.next = left?left:right
return h.next
};
406. 根据身高重建队列
题解的思路挺巧妙的，可以直接看下
var reconstructQueue = function(people) {
const res = []
// 先按height逆序排列 相等则按照k进行顺序排列
people = people.sort((a,b)=>{
const v = b[0]-a[0]
if(v===0) {
return a[1] - b[1]
}
return v
})
// 再根据k进行插入
for(const p of people) {
res.splice(p[1],0,p)
}
return res
};
11. 盛最多水的容器
var maxArea = function(height) {
let maxArea = 0
let left = 0, right = height.length-1
/**
* 两条边长中最短的那一条总是限制住矩形的高，为了寻求突破，最短那一条需要往内移动。
*/
while(left !== right) {
let area = Math.min(height[left],height[right]) * (right - left)
maxArea = Math.max(area, maxArea)
height[left] > height[right] ? right-- : left++
}
return maxArea
};
102. 二叉树的层次遍历
var levelOrder = function(root) {
/**
* 队列实现层次遍历
*/
const res = []
if(!root) {
return res
}
let q = [root]
while(q.length) {
res.push(q.map(item=>item.val))
let nextQ = []
while(q.length) {
let node = q.shift()
node.left && nextQ.push(node.left)
node.right && nextQ.push(node.right)
}
if(!nextQ.length) {
break
}
q = nextQ
}
return res
};
215. 数组中的第K个最大元素
有三种经典做法：（1）排序 - O(nlogn)（2）topK小根堆 - O(nlogk)（3）快速选择算法 - O(n)
排序
var findKthLargest = function(nums, k) {
return nums.sort((a,b)=>b-a)[k-1]
};
小根堆
这个topk算法从大二的时候老师就叫我们学了，非常经典的算法，建议背熟，可以和堆排序一起记忆。
var findKthLargest = function(nums, k) {
// 维护一个k大小的小根堆，从K开始到len-1结束，如果比堆顶大就进入堆，再调整堆，类似堆排序的变形
const arr = nums
const len = arr.length
const swap = (i, j) => {
let tmp = arr[i]
arr[i] = arr[j]
arr[j] = tmp
}
const minHeapify = (start, end) => {
let dad = start
let son = dad * 2 + 1
if (son >= end) return
if (son + 1 < end && arr[son] > arr[son + 1]) son++
if (arr[dad] > arr[son]) {
swap(dad, son)
minHeapify(son, end)
}
}
const maintainK = () => {
for (let i = (k >> 1) - 1; i >= 0; i--) minHeapify(i, k) // 维护这个k堆
}
maintainK() // 初始化K堆
for (let i = k; i < len; i++) {
if (arr[i] > arr[0]) {
swap(i, 0)
maintainK()
}
}
return arr[0]
};
快速选择算法
择日补充
49. 字母异位词分组
const groupAnagrams = function(strs) {
const map = new Map()
const hashStr = (str) => {
const arr = Array(26).fill(0)
const aIdx = 'a'.charCodeAt()
for(const c of str) {
arr[c.charCodeAt()-aIdx]++
}
return arr.join(',')
}
for(const str of strs) {
const hash = hashStr(str)
!map.has(hash) && map.set(hash, [])
map.get(hash).push(str)
}
return Array.from(map.values())
};
347. 前 K 个高频元素
这不，小根堆适用的算法又来来
var topKFrequent = function(nums, k) {
// 先整一个哈希表
const map = new Map()
for(const n of nums) {
!map.has(n) && map.set(n, 0)
map.set(n, map.get(n)+1)
}
// 小根堆，比较标准是哈希表的值
const arr = Array.from(map.keys())
const len = arr.length
const swap = (i, j) => {
let tmp = arr[i]
arr[i] = arr[j]
arr[j] = tmp
}
const minHeapify = (start, end) => {
let dad = start
let son = dad * 2 + 1
if (son >= end) return
if (son + 1 < end && map.get(arr[son]) > map.get(arr[son + 1])) son++
if (map.get(arr[dad]) > map.get(arr[son])) {
swap(dad, son)
minHeapify(son, end)
}
}
const maintainK = () => {
for (let i = (k >> 1) - 1; i >= 0; i--) minHeapify(i, k) // 维护这个k堆
}
maintainK()
for (let i = k; i < len; i++) {
if (map.get(arr[i]) > map.get(arr[0])) {
swap(i, 0)
maintainK()
}
}
for (let i = k - 1; i >= 0; i--) {
swap(0, i)
minHeapify(0, i)
}
return arr.slice(0, k)
};
236. 二叉树的最近公共祖先
- 哈希表存储祖先节点。
var lowestCommonAncestor = function(root, p, q) {
/**
* 哈希表存储祖先节点
* 1. 先用哈希表存储祖先节点
* 2. 每个节点的祖先搭配哈希表可以形成一个链表类似物。
* 3. 最近公共祖先 = 链表的交点，可以使用双指针进行查找
*/
const map = new Map()
// 哈希表存储祖先节点
const travel = (node) => {
if(!node) {
return
}
if(node.left) {
map.set(node.left, node)
travel(node.left)
}
if(node.right) {
map.set(node.right, node)
travel(node.right)
}
}
travel(root)
// 双指针找链表的交点
let np = p, nq = q
while(np !== nq) {
np = map.get(np) ? map.get(np) : q
nq = map.get(nq) ? map.get(nq) : p
}
return np
};
- 递归方法
const lowestCommonAncestor = function(root, p, q) {
if (!root || root===p || root===q) {
return root
}
const left = lowestCommonAncestor(root.left, p, q)
if(left !== null && left !== p && left !== q) {
return left
}
const right = lowestCommonAncestor(root.right, p, q)
if(right !== null && right !== p && right !==q) {
return right
}
if(right && left) return root
return left ? left : right
};
62. 不同路径
var uniquePaths = function(m, n) {
/**
* 每个格子的值取决于 dp[i+1][j] + dp[i][j+1]
* j=0:m-1 dp[n-1][j] = 1
* i=0:n-1 dp[i][m-1] = 1
* [10,6,3,1]
* [4,3,2,1]
* [1,1,1,0/1没关系]
*/
// init
if(n === 0 || m === 0) return 0
if(n === 1 || m === 1) return 1
const dp = Array(n).fill(Array(m).fill(0))
for(let j=0;j<m;j++) dp[n-1][j]=1
for(let i=0;i<n;i++) dp[i][m-1]=1
for(let i=n-2;i>=0;i--) {
for(let j=m-2;j>=0;j--) {
dp[i][j] = dp[i+1][j] + dp[i][j+1]
}
}
return dp[0][0]
};
739. 每日温度
const dailyTemperatures = function(T) {
const stack = []
const len = T.length
const res = Array(len).fill(0)
for(let i=len-1;i>=0;i--) {
while(stack.length && T[i] >= T[stack[stack.length-1]]) stack.pop()
if(stack.length) res[i] = stack[stack.length-1] - i
stack.push(i)
}
return res
};
337. 打家劫舍 III
const map = new Map()
var rob = function(root) {
if(!root) return 0
if(map.has(root)) return map.get(root)
let doIt = root.val + (root.left?rob(root.left.left)+rob(root.left.right):0) + (root.right?rob(root.right.right)+rob(root.right.left):0)
let notDo = rob(root.left) + rob(root.right)
let res = Math.max(doIt, notDo)
map.set(root, res)
return res
}
75. 颜色分类
var sortColors = function(nums) {
/**
* 初始化0的最右边界：p0 = 0。在整个算法执行过程中 nums[idx < p0] = 0.
*
* 初始化2的最左边界 ：p2 = n - 1。在整个算法执行过程中 nums[idx > p2] = 2.
*
* 初始化当前考虑的元素序号 ：curr = 0.
*
* While curr <= p2 :
*
* 若 nums[curr] = 0 ：交换第 curr个 和 第p0个 元素，并将指针都向右移。
*
* 若 nums[curr] = 2 ：交换第 curr个和第 p2个元素，并将 p2指针左移 。
*
* 若 nums[curr] = 1 ：将指针curr右移。
*/
const n = nums.length
let p0 = 0, p2 = n - 1, curr = 0
const swap = (i,j) => {
let tmp = nums[i]
nums[i] = nums[j]
nums[j] = tmp
}
while(curr <= p2) {
// curr所在的为0时，为什么curr可以+1呢？因为此时的curr与之交换的是curr扫描过的位置，如果是0or2都已经被发配到正确的位置了
if(nums[curr] === 0) {
swap(curr, p0)
p0++
curr++
}
// curr所在的为2时，为什么curr可以不增加呢？因为此时的curr与之交换的是curr没扫描过的位置，需要再规划一下。
else if(nums[curr] === 2) {
swap(curr, p2)
p2--
}
else if(nums[curr] === 1) {
curr++
}
}
};
279. 完全平方数
var numSquares = function(n) {
const dp = Array(n+1).fill(0)
for(let i=1;i<=n;i++) {
dp[i] = i
for(let j=1;j*j<=i;j++) {
dp[i] = Math.min(dp[i], dp[i-j*j]+1)
}
}
return dp[n]
};
17. 电话号码的字母组合
var letterCombinations = function(digits) {
/**
* 类似全排列
* 2 -> ['a','b','c']
*/
if(digits.length===0) {
return []
}
const res = []
const letterGroup = [
['a','b','c'],
['d','e','f'],
['g','h','i'],
['j','k','l'],
['m','n','o'],
['p','q','r','s'],
['t','u','v'],
['w','x','y','z']
]
const getCombinations = (arr, i) => {
if(i === digits.length) {
res.push(arr.join(''))
return
}
for(let c of letterGroup[Number(digits[i])-2]) {
getCombinations([...arr, c], i+1)
}
}
getCombinations([],0)
return res
};
394. 字符串解码
var decodeString = function(s) {
let stack = []
let res = ''
let time = 0
for(let c of s) {
if(c === '[') {
stack.push([time, res])
res = ''
time = 0
} else if(c === ']') {
let [curr_time, last_res] = stack.pop()
res = last_res + res.repeat(curr_time)
} else if(c >= '0' && c <= '9') {
time = time * 10 + Number(c)
} else {
res += c
}
}
return res
};
