看了这篇 LeetCode 的刷题心得，再也不用抄别人代码了
原文：《LeetCode 算法题刷题心得》https://www.jianshu.com/p/8876704ea9c8
花了十几天，把《算法》看了一遍然后重新 AC 了一遍 LeetCode 的题，收获颇丰。这次好好记录下心得。
我把所有做题的代码都放在 github 上以供参考。
-
看题不懂方法论，理解他人方案困难。 -
解题方法通过看别人的方案去归纳，照着抄。（其实都是有系统的算法写法的） -
很多题目看了答案只是知其然而不知其所以然。 -
很多答案（讨论区的方案）是有错误的，却把它当正确答案来发。
各类题的解决方案
二叉树
二叉树大多使用递归的方式左右两个元素向下递归。比如：
var maxDepth = function (root) {
if (root == null) return 0
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right))
};将二叉树以二维数组形式表现：
var levelOrder = function(root) {
let ans = []
helper(root, ans, 0)
return ans
};
function helper(node, ans, i){
if (node == null) return
if (i == ans.length) ans.push([])
ans[i].push(node.val)
helper(node.left, ans, i + 1)
helper(node.right, ans, i + 1)
}可能性问题
这类题一般是告诉你一组数据，然后求出可能性、最小值或最大值。比如：
给定几种面额的硬币和一个总额，使用最少的硬币凑成这个总额。
var coinChange = function (coins, amount) {
let max = amount + 1
let dp = new Array(amount + 1)
dp.fill(max)
dp[0] = 0
for (let i = 1; i < max; i++) {
for (let j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1)
}
}
}
return dp[amount] > amount ? -1 : dp[amount]
};var uniquePaths = function (m, n) {
const pos = new Array(m)
for (let i = 0; i < m; i++) {
pos[i] = new Array(n)
}
for (let i = 0; i < n; i++) {
pos[0][i] = 1
}
for (let i = 0; i < m; i++) {
pos[i][0] = 1
}
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
pos[i][j] = pos[i - 1][j] + pos[i][j - 1]
}
}
return pos[m - 1][n - 1]
};var maxSubArray = function (nums) {
let count = nums[0], maxCount = nums[0]
for (let i = 1; i < nums.length; i++) {
count = Math.max(count + nums[i], nums[i])
maxCount = Math.max(maxCount, count)
}
return maxCount
};查找
-
排序算法（排序便于查找） -
二分查找 -
索引移动查找（这个方法名自己想的，大概就这个意思~）
var searchMatrix = function (matrix, target) {
if (matrix.length == 0) return false
let row = 0, col = matrix[0].length - 1
while (true) {
if (matrix[row][col] > target && col > 0) {
col--
} else if (matrix[row][col] < target && row < matrix.length - 1) {
row++
} else if (matrix[row][col] == target) {
return true
} else {
break
}
}
return false
};先将位置定位在右上角，通过改变位置坐标来找到目标值。使用了索引移动查找法来找到结果。
找到数组中最左边和最右边的某个数字所在位置：
var searchRange = function (nums, target) {
let targetIndex = binarySearch(nums, target, 0, nums.length - 1)
if (targetIndex == -1) return [-1, -1]
let l = targetIndex, r = targetIndex
while(l > 0 && nums[l - 1] == target){
l--
}
while(r < nums.length - 1 && nums[r + 1] == target){
r++
}
return [l, r]
};
function binarySearch(arr, val, lo, hi) {
if (hi < lo) return -1
let mid = lo + parseInt((hi - lo) / 2)
if (val < arr[mid]) {
return binarySearch(arr, val, lo, mid - 1)
} else if (val > arr[mid]) {
return binarySearch(arr, val, mid + 1, hi)
} else {
return mid
}
}回文
所谓回文，就是正着读反着读是一样的。使用索引两边向中间移动的方式来判断是否为回文。
找到给定字符串中某段最长的回文：
var longestPalindrome = function (s) {
let maxLength = 0, left = 0, right = 0
for (let i = 0; i < s.length; i++) {
let singleCharLength = getPalLenByCenterChar(s, i, i)
let doubleCharLength = getPalLenByCenterChar(s, i, i + 1)
let max = Math.max(singleCharLength, doubleCharLength)
if (max > maxLength) {
maxLength = max
left = i - parseInt((max - 1) / 2)
right = i + parseInt(max / 2)
}
}
return s.slice(left, right + 1)
};
function getPalLenByCenterChar(s, left, right) {
// 中间值为两个字符，确保两个字符相等
if (s[left] != s[right]){
return right - left
}
while (left > 0 && right < s.length - 1) {
left--
right++
if (s[left] != s[right]){
return right - left - 1
}
}
return right - left + 1
}路径题
let hasWord = false
var findWords = function (board, words) {
var ans = []
for (let word of words) {
for (let j = 0; j < board.length; j++) {
for (let i = 0; i < board[0].length; i++) {
if (board[j][i] == word[0]) {
hasWord = false
DFS(word, board, 0, j, i, "")
if (hasWord) {
if (!ans.includes(word))
ans.push(word)
}
}
}
}
}
return ans
};
function DFS(word, board, index, j, i, subStr) {
if (word[index] == board[j][i]) {
subStr += board[j][i]
board[j][i] = "*"
if (j < board.length - 1)
DFS(word, board, index + 1, j + 1, i, subStr)
if (j > 0)
DFS(word, board, index + 1, j - 1, i, subStr)
if (i < board[0].length - 1)
DFS(word, board, index + 1, j, i + 1, subStr)
if (i > 0)
DFS(word, board, index + 1, j, i - 1, subStr)
board[j][i] = word[index]
}
if (index >= word.length || subStr == word) {
hasWord = true
}
}
const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
var longestIncreasingPath = function (matrix) {
if (matrix.length == 0) return 0
const m = matrix.length, n = matrix[0].length
let max = 1
let cache = new Array(m)
for (let i = 0; i < m; i++){
let child = new Array(n)
child.fill(0)
cache[i] = child
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
let len = dfs(matrix, i, j, m, n, cache)
max = Math.max(max, len)
}
}
return max
}
function dfs(matrix, i, j, m, n, cache){
if (cache[i][j] != 0) return cache[i][j]
let max = 1
for (let dir of dirs){
let x = i + dir[0], y = j + dir[1]
if(x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= matrix[i][j]) continue;
let len = 1 + dfs(matrix, x, y, m, n, cache)
max = Math.max(max, len)
}
cache[i][j] = max
return max
}将已使用 DFS 查找过的长度放入缓存，如果有其他元素走 DFS 走到当前值，直接返回缓存最大值即可。
链表
链表从 JS 的角度来说就是一串对象使用指针连接的数据结构。合理使用 next 指针改变指向来完成对链表的一系列操作。如：
链表的排序：
var sortList = function (head) {
if (head == null || head.next == null) return head
let prev = null, slow = head, fast = head
while (fast != null && fast.next != null) {
prev = slow
slow = slow.next
fast = fast.next.next
}
prev.next = null;
let l1 = sortList(head)
let l2 = sortList(slow)
return merge(l1, l2)
};
function merge(l1, l2) {
let l = new ListNode(0), p = l;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
if (l1 != null)
p.next = l1;
if (l2 != null)
p.next = l2;
return l.next;
}slow.next
和
fast.next.next
两种速度获取链表节点，从而获取中间值。
var reverseList = function(head) {
let ans = null,cur = head
while (cur != null) {
let nextTmp = cur.next
cur.next = ans
ans = cur
cur = nextTmp
}
return ans
};排序
插入排序
选择排序
快速排序
归并排序
计数排序
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function (nums, k) {
for (let i = 0; i <= k; i++) {
let max = i
for (let j = i; j < nums.length; j++) {
if (nums[j] > nums[max]) max = j
}swap(nums, i, max)
}
return nums[k - 1]
};
function swap(arr, a, b) {
let tmp = arr[a]
arr[a] = arr[b]
arr[b] = tmp
}
[2,0,2,1,1,0] 排序：
var sortColors = function (nums) {
sort(nums, 0, nums.length - 1)
};
function sort(arr, lo, hi) {
if (hi <= lo) return
let lt = lo, i = lo + 1, gt = hi;
let v = arr[lo]
while (i <= gt) {
if (arr[i] < v) swap(arr, lt++, i++)
else if (arr[i] > v) swap(arr, i, gt--)
else i++
}
sort(arr, lo, lt - 1)
sort(arr, gt + 1, hi)
}
function swap(arr, a, b) {
let x = arr[a]
arr[a] = arr[b]
arr[b] = x
}还有之前提到的链表的排序使用的是 归并排序 。
算术题
算术题看似简单，但是遇到最大的问题就是：如果使用累加、累成这种常熟级别的增长，遇到很大的数字会出现 TLE （超出时间限制）。所以，我们要用指数级别的增长来找到结果。如：
计算 x 的 n 次方：
var myPow = function (x, n) {
if (n == 0) return 1
if (n < 0) {
n = -n
x = 1 / x
}
return (n % 2 == 0) ? myPow(x * x, parseInt(n / 2)) : x * myPow(x * x, parseInt(n / 2));
};一开始我使用了 x*x 这么乘上 n 次，但是遇到 n 太大就直接超时了。使用以上方案：29 = 2 * 44 = 2 * 82 = 2 * 64 = 128
直接从常熟级变化变为指数级变化，这一点在数学运算中是需要注意的。
求 x 的平方根：
var mySqrt = function (x) {
let l = 0, r = x
while (true) {
let mid = parseInt(l + (r - l) / 2)
if (mid * mid > x) {
r = mid - 1
} else if (mid * mid < x) {
if ((mid + 1) * (mid + 1) > x) {
return mid
}
l = mid + 1
} else {
return mid
}
}
};这题使用二分法来找到结果。
二进制问题
Number.parseInt()
和
Number.prototype.toString()
来解决。
var reverseBits = function(n) {
var t = n.toString(2).split("");
while(t.length < 32) t.unshift("0"); // 插入足够的 0
return parseInt(t.reverse().join(""), 2);
};常用算法
简单说说几种排序和查找
冒泡排序：遍历数组，对比元素和后面相邻元素，如果当前元素大于后面元素，调换位置。这样从头遍历到尾，获取最后一位排序玩的元素。然后在 1 到 n - 1 中再次重复以上步骤。直到最后第一和第二个元素对比大小。是一种从后往前的排序。
选择排序：遍历数组，找到最小的元素位置，与第一个元素调换位置，然后缩小范围从第二个元素开始遍历，如此重复到最后一个元素。可以从后往前也可以从前往后排序。
function sort(arr) {
const len = arr.length
for (let i = 0; i < len; i++) {
let min = i
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[min]) min = j
}
swap(arr, i, min)
console.log(arr)
}
return arr
}插入排序：遍历数组，选中某一个元素，与前面相邻元素对比，如果当前元素小于之前元素，调换位置，继续对比直到当前元素前的元素小于当前元素（或者到最前面），如此对所有元素排序一遍。是一种从前往后的排序。
function sort(arr) {
const len = arr.length
for (let i = 1; i < len; i++) {
for (let j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
swap(arr, j, j - 1)
console.log(arr)
}
}
return arr
}希尔排序：类似于插入排序，选中一个元素与元素前 n 个元素进行比大小和调换位置。之后再缩小 n 的值。这种方法可以减少插入排序中最小值在最后面，然后需要一个一个调换位置知道最前面这类问题。减少调换次数。是一种从前往后的排序。
归并排序：在《算法》中提到了两种归并排序：一种是自上而下的归并排序。将数组不断二分到最小单位（1到2个元素）将他们进行排序，之后将前两个和后两个元素对比，如此往上最后完成整个数组的排序。还有一种自下而上的归并排序是直接将数组分割为若干个子数组进行排序然后合并。
let aux = new Array(arr.length)
function sort(arr, lo, hi) {
if (hi <= lo) return
let mid = lo + (parseInt((hi - lo) / 2))
sort(arr, lo, mid)
sort(arr, mid + 1, hi)
merge(arr, lo, mid, hi)
}
function merge(arr, lo, mid, hi) {
let i = lo, j = mid + 1
for (let k = lo; k <= hi; k++) {
aux[k] = arr[k]
}
for (let k = lo; k <= hi; k++) {
if (i > mid) arr[k] = aux[j++]
else if (j > hi) arr[k] = aux[i++]
else if (aux[j] < aux[i]) arr[k] = aux[j++]
else arr[k] = aux[i++]
}
console.log(arr)
}function sort(arr, lo, hi) {
if (hi <= lo + 1) return
let mid = partition(arr, lo, hi) // 切分方法
sort(arr, lo, mid)
sort(arr, mid + 1, hi)
}
function partition(arr, lo, hi) {
let i = lo, j = hi + 1
let v = arr[lo]
while(true) {
while(arr[++i] < v) if (i == hi) break
while(v < arr[--j]) if (j == lo) break
if ((i >= j)) break
swap(arr, i, j)
console.log(arr)
}
swap(arr, lo, j)
console.log(arr)
return j
}function sort(arr, lo, hi) {
if (hi <= lo) return
let lt = lo, i = lo + 1, gt = hi;
let v = arr[lo]
while (i <= gt) {
if (arr[i] < v) swap(arr, lt++, i++)
else if (arr[i] > v) swap(arr, i, gt--)
else i++
console.log(arr)
}
sort(arr, lo, lt - 1)
sort(arr, gt + 1, hi)
}堆排序：堆排序可以说是一种利用堆的概念来排序的选择排序。使用优先队列返回最大值的特性逐个返回当前堆的最大值。
计数排序：就是将数组中所有元素的出现次数保存在一个数组中，然后按照从小到大返回排序后的数组。
桶排序：其实就是字符串排序的 LSD 和 MSD 排序。LSD 使用索引计数法从字符串右边向左边移动，根据当前值进行排序。而 MSD 是从左到右使用索引计数法来排序，在字符串第一个字符后，将字符串数组分为若干个相同首字符串的数组各自进行第二、第三次的 MSD 排序。
二分查找：对有序数组去中间值与目标值相比对。如果目标值小于中间值，取前一半数组继续二分。如果目标值大于中间值，取后一半数组继续二分。如果目标值等于中间值，命中！
DFS
DFS（顶点v）
{
标记v为已遍历；
for（对于每一个邻接v且未标记遍历的点u）
DFS（u）;
}DFS 使用的是递归的方式进行搜索的。
示例：在二维字母矩阵中查找是否能够使用相邻字母组成目标单词。
var exist = function (board, word) {
for (let y = 0; y < board.length; y++) {
for (let x = 0; x < board[0].length; x++) {
if (find(board, word, y, x, 0)) return true
}
}
return false
};
function find(board, word, y, x, d) {
if (d == word.length) return true
if (y < 0 || x < 0 || y == board.length || x == board[y].length) return false;
if (board[y][x] != word[d]) return false
let tmp = board[y][x]
board[y][x] = "*"
let exist = find(board, word, y, x + 1, d + 1)
|| find(board, word, y, x - 1, d + 1)
|| find(board, word, y + 1, x, d + 1)
|| find(board, word, y - 1, x, d + 1)
board[y][x] = tmp
return exist
}BFS
广度优先搜索（BFS）就是将从条件1到条件2的所有可能性都列出来同步搜索的过程。适用于查找最短路径。举个栗子，如果有5条路，那么 BFS 算法就是分别向5条路排出斥候去侦察。
BFS()
{
输入起始点；
初始化所有顶点标记为未遍历；
初始化一个队列 queue 并将起始点放入队列；
while（queue 不为空）
{
从队列中删除一个顶点s并标记为已遍历；
将s邻接的所有还没遍历的点加入队列；
}
}BFS 是使用数组存储下一顶点的方式。
示例：每次改变一次字母，通过给定数组中的单词，从单词 A 变为单词 B。
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {number}
*/
var ladderLength = function (beginWord, endWord, wordList) {
if (!wordList.includes(endWord)) return 0
let set = new Set(),
visited = new Set(),
len = 1
set.add(beginWord)
visited.add(beginWord)
while (set.size != 0) {
let tmp = new Set([...set])
for (let w of tmp) {
visited.add(w)
set.delete(w)
if (changeOneChar(w, endWord))
return len + 1
for (let word of wordList){
if (changeOneChar(w, word) && !visited.has(word)){
set.add(word)
}
}
}
len++
}
return 0
};
function changeOneChar(a, b) {
let count = 0
for (let i = 0; i < a.length; i++)
if (a[i] != b[i])
count++
return count == 1
}最后
Robert Sedgewick，Kevin Wayne | 著
本书作为算法领域经典的参考书，全面介绍了关于算法和数据结构的必备知识，并特别针对排序、搜索、图处理和字符串处理进行了论述。
第4版具体给出了每位程序员应知应会的50个算法，提供了实际代码，而且这些Java 代码实现采用了模块化的编程风格，读者可以方便地加以改造。
本书配套网站提供了书中内容的摘要及更多的代码实现、测试数据、练习、教学课件等资源。本书适合用作大学教材或从业者的参考书。
本书是 JavaScript 经典图书的新版。第4版涵盖 ECMAScript 2019，全面、深入地介绍了 JavaScript 开发者必须掌握的前端开发技术，涉及 JavaScript 的基础特性和高级特性。
书中详尽讨论了 JavaScript 的各个方面，从 JavaScript 的起源开始，逐步讲解到新出现的技术，其中重点介绍 ECMAScript 和 DOM 标准。在此基础上，接下来的各章揭示了 JavaScript 的基本概念，包括类、期约、迭代器、代理，等等。
另外，书中深入探讨了客户端检测、事件、动画、表单、错误处理及 JSON。本书同时也介绍了近几年来涌现的重要新规范，包括 Fetch API、模块、工作者线程、服务线程以及大量新API。