各类题的解决方案
话不多说，系统整理下解题的一些算法和解决方案
二叉树
二叉树大多使用递归的方式左右两个元素向下递归。比如：
计算二叉树最大深度
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]};
复制代码
使用了动态规划（DP），将从 0 到目标额度所需的最小硬币数都列出来。
求出从矩阵左上角走到右下角，且只能向右向下移动，一共有多少种可能性。
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};
复制代码
上面这题通过不断对比最大值来保留并返回最大值。
其实，可能性问题使用动态规划要比使用 DFS、BFS 算法更加简单而容易理解。（我使用 DFS 经常报 TLE）
查找
一般遇到的查找问题，如查找某个值一般会用到一下方法：
查找横向和纵向都递增的二维矩阵中的某个值
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}
复制代码
路径题
路径题可以使用深度优先（DFS）和广度优先（BFS）算法来做。我比较常用的是使用 DFS 来做。通过递归将走过的路径进行标记来不断往前找到目标路径。如：
通过给定单词在二维字母数组中查找是否能使用邻近字母组成这个单词(212 题)
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 }}
复制代码
由于 DFS 是一条路走到黑，如果每个元素都去使用 DFS 来找会出现超时的情况。如果条件允许（如查找递增数组）可以通过设置缓存来优化 DFS 查找超时问题。
获取二维矩阵中最大相邻递增数组长度。
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};
复制代码
排序
排序和查找算是算法中最重要的问题了。常用的排序算法有：
更多排序算法的知识点可参考《JS 家的排序算法》，文章作者图文并茂的讲解了各种排序算法，很容易理解。
举几个排序算法的栗子：
求数组中第 K 大的值
/** * @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}
复制代码
使用了选择排序排列了前 K 个值得到结果。
对有重复值的数组 [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()来解决。
将一个 32 位数字的二进制进行倒序
var reverseBits = function(n) { var t = n.toString(2).split(""); while(t.length < 32) t.unshift("0"); // 插入足够的 0 return parseInt(t.reverse().join(""), 2);};
复制代码
常用算法
讲了这么多，其实除了常用的排序、搜索，其他最常用的就是 DP、DFS、BFS 这三个算法了。可以这么说：掌握了排序和这三个算法，可以 AC 大多数的算法问题。这么牛逼的算法了解一下？
简单说说几种排序和查找
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 排序。
二分查找： 对有序数组去中间值与目标值相比对。如果目标值小于中间值，取前一半数组继续二分。如果目标值大于中间值，取后一半数组继续二分。如果目标值等于中间值，命中！
DP
我的理解：动态规划就是下一状态可以根据上一状态，或之前几个状态获取到的一种推理过程。
DFS
深度优先搜索（DFS）就是选中某条从条件 1 到条件 2 的某条可能性进行搜索，之后返回搜索其他一条可能性，如此一条条升入。举个栗子，如果有 5 条路，那么 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。（127 题）
/** * @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}
复制代码
最后
写下 AC 一遍题目之后的收获。
知道了方法论，做起题来轻松了不少。
遇到问题多找轮子，一定有某种方法论可以用。
不要耍小聪明用一些奇巧淫技，思路不对再怎么绕都是浪费时间。
不要想着自己造轮子（特别是算法方面），绝大多数问题前辈一定有更好更完善的方案在。自己造轮子费时费事又没太大意义。
看答案和自己做是两回事，自己动手实现了才能算是会了。
算法之所以存在，就是用来适应某些场景、解决某类问题的。在对的场景选择对的算法才能体现算法的价值，不要滥用算法。
没必要把所有算法都精通，但起码在遇到问题时可以找到最优算法解决问题。即知道算法的存在及其用途，按需深入学习。
其实刷算法题还是很有趣的事情，之后计划把 LeetCode 题库中的所有问题都刷一遍~
PS：本文以及相关项目中有任何错误或者可以改进的地方，还请提出。共同进步~
评论