在解决算法的过程中，我们实际上有很多技巧可以使用，往往遇到一个题目，比如发现求最优，你就应该想到动态规划，发现求最大最小，你就应该想到贪心算法，发现求子集，你就应该想到回溯算法等等。这些技巧实际上都是充分利用了数据结构的特点，然后通过一些巧妙的方法来解决问题。下面我们就来看一下算法中的一些技巧。
哨兵节点
哨兵节点是一种特殊的节点，它的作用是为了简化边界条件的判断。在链表中，我们经常会使用哨兵节点，比如在链表的头部添加一个哨兵节点，这样我们就不需要单独处理头节点的情况。举一个简单的例子，我们要删除链表中的一个节点，我们可以这样做：
//创建一个哨兵节点
let dummy = new ListNode(0);
dummy.next = head;
let prev = dummy;
while (prev.next) {
if (prev.next.val === val) {
prev.next = prev.next.next;
break;
}
prev = prev.next;
}
return dummy.next;
在这个例子中，我们创建了一个哨兵节点dummy，然后将它的next指针指向头节点head，这样我们就不需要单独处理头节点的情况。在循环中，我们只需要判断prev.next是否为空，就可以避免空指针异常。
双指针
双指针可以帮助我们解决很多问题，你可能不知道的是双指针通常可以分为两种类型：快慢指针和左右指针。
快慢指针
快慢指针主要用于解决链表中的问题。快慢指针通常是两个指针，一个指针走得快，一个指针走得慢。快慢指针的典型问题有判断链表是否有环、找到链表的中间节点等。举一个例子，我们要判断一个链表是否有环，我们可以这样做：
var hasCycle = function(head) {
if (!head || !head.next) {
return false;
}
let slow = head;
let fast = head.next;
while (slow !== fast) {
if (!fast || !fast.next) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
};
在这个例子中，我们使用了快慢指针来判断链表是否有环。我们让slow指针每次走一步，fast指针每次走两步，如果链表有环，那么slow指针和fast指针一定会相遇。
使用快慢指针还可以解决一些其他问题，比如找到链表的中间节点、找到链表的倒数第k个节点等。
左右指针
左右指针主要用于解决数组或字符串中的问题。左右指针通常是两个指针，一个指针从左向右移动，一个指针从右向左移动。左右指针的典型问题有反转数组、反转字符串、滑动窗口等。举一个例子，我们要反转一个数组，我们可以这样做：
var reverseArray = function(nums) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
[nums[left], nums[right]] = [nums[right], nums[left]];
left++;
right--;
}
return nums;
};
在这个例子中，我们使用了左右指针来反转一个数组。我们让left指针从数组的左边向右移动，right指针从数组的右边向左移动，然后交换left指针和right指针所指向的元素，直到left指针大于等于right指针。
在快速排序中，我们一般不采用左右指针进行 partition 操作，虽然左右指针可以解决，但是一般只使用一个指针，这样可以减少代码的复杂度。partition 操作的代码如下：
function partition(arr, left, right) {
let pivot = left;
let index = pivot + 1;
for (let i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
[arr[i], arr[index]] = [arr[index], arr[i]]; // 这样我们相当于把小于 pivot 的元素都放到了 pivot 的左边
index++;
}
}
[arr[pivot], arr[index - 1]] = [arr[index - 1], arr[pivot]];
return index - 1;
}
双指针效率可能稍微高那么一点，但是代码的复杂度会增加，所以在实际应用中，我们可以根据实际情况来选择。
滑动窗口
滑动窗口主要用于解决数组或字符串中的子数组或子串的问题。滑动窗口通常是两个指针，一个指针表示窗口的左边界，一个指针表示窗口的右边界。滑动窗口的典型问题有找到字符串中的最长无重复子串、找到数组中的最小子数组等。举一个例子，我们要找到字符串中的最长无重复子串，我们可以这样做：
var lengthOfLongestSubstring = function(s) {
let left = 0;
let right = 0;
let max = 0;
let set = new Set();
while (right < s.length) {
if (!set.has(s[right])) {
set.add(s[right]);
max = Math.max(max, set.size);
right++;
} else {
set.delete(s[left]);
left++;
}
}
return max;
};
在这个例子中，我们使用了滑动窗口来找到字符串中的最长无重复子串。我们让left指针和right指针分别表示窗口的左边界和右边界，然后我们不断移动right指针，直到窗口中出现重复字符，然后我们移动left指针，直到窗口中没有重复字符，然后我们继续移动right指针，直到遍历完整个字符串。
当然，最长无重复子串的问题还有其他解法，比如使用哈希表来存储字符的索引，这样我们就可以直接跳过重复字符，而不需要一个一个地删除，其解法如下：
var lengthOfLongestSubstring = function(s) {
let left = 0;
let right = 0;
let max = 0;
let map = new Map();
for (right = 0; right < s.length; right++) {
if (map.has(s[right])) {
left = Math.max(left, map.get(s[right]) + 1);
}
map.set(s[right], right);
max = Math.max(max, right - left + 1);
}
return max;
};
在这个解法中，我们使用了哈希表map来存储字符的索引，这样我们就可以直接跳过重复字符，而不需要一个一个地删除。
当然，这个问题还有其他解法，比如使用动态规划，我们可以定义一个数组dp，其中dp[i]表示以第i个字符结尾的最长无重复子串的长度，然后我们可以根据dp[i-1]来计算dp[i]，其解法如下：
var lengthOfLongestSubstring = function(s) {
let dp = new Array(s.length).fill(0);
let map = new Map();
dp[0] = 1;
map.set(s[0], 0);
let max = 1;
for (let i = 1; i < s.length; i++) {
if (map.has(s[i])) {
let index = map.get(s[i]);
if (i - index > dp[i - 1]) {
dp[i] = dp[i - 1] + 1;
} else {
dp[i] = i - index;
}
} else {
dp[i] = dp[i - 1] + 1;
}
map.set(s[i], i);
max = Math.max(max, dp[i]);
}
return max;
};
可以看到，在三种解法当中，滑动窗口的解法是最简单的，而且效率也是最高的。
递归
递归主要用于解决树、图等递归结构的问题。递归的核心思想是将一个大问题分解为若干个小问题，然后递归地解决这些小问题。递归的典型问题有二叉树的遍历、图的遍历等。举一个例子，我们要判断一棵二叉树是否对称，我们可以这样做：
var isSymmetric = function(root) {
return isMirror(root, root);
};
var isMirror = function(left, right) {
if (left === null && right === null) {
return true;
}
if (left === null || right === null) {
return false;
}
return (left.val === right.val) && isMirror(left.left, right.right) && isMirror(left.right, right.left);
};
在这个例子中，我们使用了递归来判断一棵二叉树是否对称。我们定义了一个辅助函数isMirror，它的作用是判断两个节点是否对称。如果两个节点都为空，那么它们是对称的；如果其中一个节点为空，那么它们不是对称的；如果两个节点的值相等，并且左子树的左子树和右子树的右子树对称，左子树的右子树和右子树的左子树对称，那么它们是对称的。
分治
分治主要用于解决数组、字符串等分治结构的问题。分治的核心思想是将一个大问题分解为若干个小问题，然后递归地解决这些小问题，最后将这些小问题的解合并起来得到大问题的解。分治的典型问题有归并排序、快速排序等。举一个例子，我们要求一个数组的逆序对的个数，我们可以这样做：
var reversePairs = function(record) {
let res = 0;
function mergeSort(arr) {
if (arr.length < 2) {
return arr;
}
let mid = Math.floor(arr.length / 2);
let left = arr.slice(0, mid);
let right = arr.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let result = [];
while (left.length && right.length) { // 这种方式避免指针操作，也算是一个技巧
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
res += left.length; // 因为 left 和 right 都是有序的，所以如果 left[0] > right[0]，那么 left[0] 及其后面的元素都大于 right[0]
}
}
return result.concat(left, right);
}
mergeSort(record);
return res;
};
这个算法实际上是利用了归并排序的思想，我们将数组分成两部分，然后分别求出左半部分的逆序对的个数和右半部分的逆序对的个数，然后再求出左半部分和右半部分之间的逆序对的个数，最后将这三部分的逆序对的个数相加，就是整个数组的逆序对的个数。
回溯
回溯主要用于解决组合、排列等问题。回溯的核心思想是递归地枚举所有可能的解，然后通过剪枝来减少不必要的计算。回溯的典型问题有全排列、子集等。举一个例子，我们要求一个数组的全排列，我们可以这样做：
var permute = function(nums) {
let res = [];
let used = new Array(nums.length).fill(false);
function backtrack(path) {
if (path.length === nums.length) {
res.push(path.slice());
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}
path.push(nums[i]);
used[i] = true;
backtrack(path);
path.pop();
used[i] = false;
}
}
backtrack([]);
return res;
};
思考一下，这里一定需要加上 used 数组，因为我们要求的是全排列，所以我们需要标记哪些元素已经使用过了，哪些元素还没有使用过。
回溯算法解决的经典问题还有 N 皇后问题、解数独等，这些问题都是通过枚举所有可能的解，然后通过剪枝来减少不必要的计算。比如八皇后问题，我们可以通过枚举每一行的皇后的位置，然后判断是否满足条件，如果满足条件，那么我们就继续递归地枚举下一行的皇后的位置，如果不满足条件，那么我们就剪枝，不再继续递归。
位运算
位运算主要用于解决位操作的问题。位运算的核心思想是通过位运算来实现一些特定的功能，比如异或运算、与运算、或运算等。位运算的典型问题有只出现一次的数字、两个数的交换等。举一个例子，我们要找到数组中只出现一次的数字，我们可以这样做：
var singleNumber = function(nums) {
let res = 0;
for (let num of nums) {
res ^= num;
}
return res;
};
在这个例子中，我们使用了异或运算来找到数组中只出现一次的数字。异或运算的性质是：两个相同的数异或等于0，一个数和0异或等于它本身，所以我们可以通过异或运算来找到只出现一次的数字。
哈希表
哈希表主要用于解决查找、去重等问题。哈希表的核心思想是通过哈希函数将键映射到值，然后通过哈希表来存储这些值键对。为什么要使用值作为键呢？你可能需要思考一下这个问题。同样，单调栈存的也不是值，而是索引，这样可以更好地解决问题。
var twoSum = function(nums, target) {
let map = new Map();
for (let i = 0; i < nums.length; i++) {
let complement = target - nums[i];
if (map.has(complement)) {
return [map.get(complement), i];
}
map.set(nums[i], i);
}
};
在这个例子中，我们使用了哈希表来找到数组中两个数的和等于目标值。我们定义了一个哈希表map，然后遍历数组，对于每个元素，我们计算它的补数，然后判断这个补数是否在哈希表中，如果在，那么我们就找到了这两个数。
单调栈
单调栈主要用于解决找到数组中下一个更大元素等问题。单调栈的核心思想是维护一个单调递增或单调递减的栈，然后通过栈来找到数组中下一个更大元素或下一个更小元素。单调栈的典型问题有找到数组中下一个更大元素、找到数组中下一个更小元素等。举一个例子，我们要找到数组中下一个更大元素，我们可以这样做：
var nextGreaterElement = function(nums) {
let stack = [];
let res = new Array(nums.length).fill(-1);
for (let i = 0; i < nums.length; i++) {
while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {
res[stack.pop()] = nums[i];
}
stack.push(i);
}
return res;
};
在这个例子中，我们使用了单调栈来找到数组中下一个更大元素。我们定义了一个栈stack，然后遍历数组，对于每个元素，我们判断它是否大于栈顶元素，如果大于，那么我们就找到了栈顶元素的下一个更大元素，然后我们将栈顶元素出栈，继续判断，直到栈为空或者当前元素小于栈顶元素。
一个变种问题是接雨水，我们可以使用单调栈来解决这个问题，框架大题一致，只是在处理的时候稍微有点不同，代码如下：
var trap = function(height) {
let stack = [];
let res = 0;
for (let i = 0; i < height.length; i++) {
while (stack.length && height[i] > height[stack[stack.length - 1]]) {
let top = stack.pop();
if (!stack.length) { // 如果栈为空，说明无法形成凹槽
break;
}
let left = stack[stack.length - 1];
let width = i - left - 1; // 计算宽度
let h = Math.min(height[i], height[left]) - height[top]; // 计算高度
res += width * h; // 计算面积
}
stack.push(i);
}
return res;
};
单调队列
单调队列主要用于解决滑动窗口最大值等问题。单调队列的核心思想是维护一个单调递增或单调递减的队列，然后通过队列来找到滑动窗口的最大值或最小值。单调队列的典型问题有滑动窗口最大值、滑动窗口最小值等。举一个例子，我们要找到数组中滑动窗口的最大值，我们可以这样做：
var maxSlidingWindow = function(nums, k) {
let queue = [];
let res = [];
for (let i = 0; i < nums.length; i++) {
while (queue.length && nums[i] > nums[queue[queue.length - 1]]) {
queue.pop();
}
queue.push(i);
if (queue[0] === i - k) {
queue.shift();
}
if (i >= k - 1) {
res.push(nums[queue[0]]);
}
}
return res;
};
在这个例子中，我们使用了单调队列来找到数组中滑动窗口的最大值。我们定义了一个队列queue，然后遍历数组，对于每个元素，我们判断它是否大于队尾元素，如果大于，那么我们就找到了队尾元素的下一个更大元素，然后我们将队尾元素出队，继续判断，直到队列为空或者当前元素小于队尾元素。然后我们判断队头元素是否在滑动窗口的范围内，如果不在，那么我们就将队头元素出队。最后，我们将队头元素加入结果数组。
优先队列
优先队列主要用于解决找到数组中的最大值或最小值等问题。优先队列的核心思想是维护一个优先级队列，然后通过队列来找到数组中的最大值或最小值。优先队列的典型问题有找到数组中的最大值、找到数组中的最小值等。举一个例子，我们要找到数组中的第k个最大元素，我们可以这样做：
var findKthLargest = function(nums, k) {
let pq = new PriorityQueue();
for (let num of nums) {
pq.push(num);
if (pq.size() > k) {
pq.pop();
}
}
return pq.top();
};
class PriorityQueue {
constructor() {
this.pq = [];
}
push(val) {
this.pq.push(val);
this.pq.sort((a, b) => b - a);
}
pop() {
this.pq.pop();
}
top() {
return this.pq[this.pq.length - 1];
}
size() {
return this.pq.length;
}
}
在这个例子中，我们使用了优先队列来找到数组中的第k个最大元素。我们定义了一个优先队列pq，然后遍历数组，对于每个元素，我们将它加入优先队列，然后判断优先队列的大小是否大于k，如果大于，那么我们就将队头元素出队。最后，我们返回队头元素。
动态规划
动态规划主要用于解决最优子结构的问题。动态规划的核心思想是将一个大问题分解为若干个小问题，然后递归地解决这些小问题，最后将这些小问题的解合并起来得到大问题的解。动态规划的典型问题有斐波那契数列、最长递增子序列等。举一个例子，我们要求一个数组的最长递增子序列的长度，我们可以这样做：
var lengthOfLIS = function(nums) {
let dp = new Array(nums.length).fill(1);
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return Math.max(...dp);
};
在这个例子中，我们使用了动态规划来求一个数组的最长递增子序列的长度。我们定义了一个数组dp，其中dp[i]表示以nums[i]结尾的最长递增子序列的长度，然后我们遍历数组，对于每个元素，我们再次遍历之前的元素，如果当前元素大于之前的元素，那么我们就更新dp[i]，最后我们返回dp数组中的最大值。
贪心算法
贪心算法主要用于解决最优解的问题。贪心算法的核心思想是每一步都选择最优解，然后得到全局最优解。贪心算法的典型问题有跳跃游戏、分发饼干等。举一个例子，我们要分发饼干，我们可以这样做：
var findContentChildren = function(g, s) {
g.sort((a, b) => a - b);
s.sort((a, b) => a - b);
let i = 0;
let j = 0;
while (i < g.length && j < s.length) {
if (g[i] <= s[j]) {
i++;
}
j++;
}
return i;
};
在这个例子中，我们使用了贪心算法来分发饼干。我们首先将孩子的胃口和饼干的大小都排序，然后我们使用两个指针i和j分别指向孩子和饼干，然后我们比较孩子的胃口和饼干的大小，如果孩子的胃口小于等于饼干的大小，那么我们就将孩子的胃口加1，然后继续比较，直到孩子的胃口大于饼干的大小或者饼干分发完毕。
Tire 树
Tire 树主要用于解决字符串匹配等问题，特别适合查找字符串长度基本都不长，但是量很大的情况。Tire 树的核心思想是将字符串存储在树中，然后通过树来查找字符串。Tire 树的典型问题有实现一个 Trie 树、实现一个 Trie 树的前缀搜索等。举一个例子，我们要实现一个 Trie 树，我们可以这样做：
class Trie {
constructor() {
this.root = {};
}
insert(word) {
let node = this.root;
for (let char of word) {
if (!node[char]) {
node[char] = {};
}
node = node[char];
}
node.isEnd = true;
}
search(word) {
let node = this.root;
for (let char of word) {
if (!node[char]) {
return false;
}
node = node[char];
}
return node.isEnd || false;
}
startsWith(prefix) {
let node = this.root;
for (let char of prefix) {
if (!node[char]) {
return false;
}
node = node[char];
}
return true;
}
}
由于 Tire树查询一个字符串的时间只和字符串的长度有关，所以 Tire 树的查询效率非常高，是一种非常实用的数据结构。
总结
每一种技巧实际上都是充分利用了数据结构的特点，然后通过一些巧妙的方法来解决问题。比如单调栈和单调队列都是利用了栈和队列的特点，然后通过维护一个单调递增或单调递减的栈或队列来解决问题。而动态规划则是利用了最优子结构的特点，然后通过递归地解决子问题，最后将子问题的解合并起来得到大问题的解。贪心算法则是每一步都选择最优解，然后得到全局最优解。
算法的解决肯定不是那么容易，但是也是有方法可循的，我们可以通过不断地练习，不断地总结，来提高自己的算法水平。希望大家都能够掌握这些技巧，然后在解决算法问题的时候游刃有余。
参考资料
关注微信公众号 老码沉思录 ，了解我最新的动态。