算法基本功

本文不是实际意义上的算法基础, 而是我个人学习了一段时间算法后总结出来的一些我认为对于初学者来说还算是比较重要的小点.

区间

区间的概念在实际生活中其实非常常见:

从 7 楼到 18 楼要爬多少层?
1 月 10 号到 1 月 30 号共有多少天?
1 月 10 号到 1 月 30 号之间有多少天?

如果有区间的概念, 就可以很容易解决:

(7, 18]: 7 到 18 楼, 那么是不包含 7 楼且包含 18 楼, 则需要爬 18 - 7 = 11.
[10, 30]: 包含 10 号和 30 号, 则 30 - 10 + 1 = 21 天
(10, 30): 不包含 10 号和 30 号, 则 30 - 10 - 1 = 19 天

善于总结的人已经注意到了: 闭区间用 [], 开区间用 (), 对应的计算公式是:

[i, j]: j - i + 1
(i, j): j - i - 1
(i, j]: j - i

可千万不要小瞧这个知识点, 如果对区间的概念不熟悉, 在做二分法的时候简直要命🥲

同意的朋友请在文章底部给我点个👍.

遍历

来看看区间在遍历中的作用, 先说结果:

对于循环不定式, 如果是闭区间则包含, 如果是开区间则不包含.

// [2, 28]
for (let i = 2; i <= 28; ++i) {}
// [2, 28)
for (let i = 2; i < 28; ++i) {}

一维数组的遍历没什么好多说的了, 主要看一下二位数组的遍历, 在动态规划中, 遍历的方式方向都是有一定技巧的.

螺旋遍历

螺旋遍历，和 BFS 有一点点像，需要 while 和 for 配合，同时需要四个边界来进行收缩。

let count = 0
let top = 0,
  left = 0,
  bottom = m - 1,
  right = n - 1
while (count < 25) {
  // 遍历顶部的行 区间 [left, right]
  for (let i = left; i <= right; ++i) {
    console.log(Arr[top][i])
    count++
  }
  top++
  // 遍历右边的列 [top, bottom]
  for (let i = top; i <= bottom; ++i) {
    console.log(Arr[i][right])
    count++
  }
  right--
  // 倒序遍历底部的行 [left, right]
  for (let i = right; i >= left; --i) {
    console.log(Arr[bottom][i])
    count++
  }
  bottom--
  // 倒序遍历左侧的列 [top, bottom]
  for (let i = bottom; i >= top; --i) {
    console.log(Arr[i][left])
    count++
  }
  left++
}

斜向遍历

如图，按照这样的顺序怎么遍历呢？

先了解一下

主对角线：左上角到右下角，坐标 i === j; 可得性质 i - j 固定值
副对角线：左下角到右上角，坐标 i + j === len - 1; 可得性质 i + j 固定值

而这个固定值, 在斜向遍历中恰好与斜线 l 的索引相等. (纯用数学归纳法的个人总结😂)

主对角线上半部分

// 数组大小为 5 * 5, 斜线对应索引为 [1, 4], 所以外层for遍历斜线
for (let l = 1; l < len; ++l) {
  for (let i = 0; i < len - l; ++i) { // i 的区间为 [0, len - l]
    const j = l + i // 主对角线 i - j 固定
    console.log(arr[i][j])
  }
}

主对角线下半部分

for(let l = 1; l < len; ++l) {
  for(let j = 0; j < len - l; ++j) { // 仅仅是 i 和 j 调换一下位置即可
    const i = l + j
    console.log(arr[i][j])
  }
}

副对角线留给你🐶 (当然我是不推荐死记硬背的, 还是得掌握基本原理, 多观察多思考.)

递归

递归就是自己调自己, 往往用来处理复杂的问题比较直观有效.常规的递归教学建议直接谷歌, 这里记录下我认为对递归理解需要注意的点:

递归必须有结束条件, 防止死循环
注意递归的过程中的 return, 对出参有数
充分利用好递归函数的入参保存传递信息

递归序

很多讲递归的都不会讲递归序, 但其实这对于递归的理解非常重要.

/**
 *        1
 *       / \
 *      2   3
 *     / \ / \
 *    4  5 6  7
 *
 * 下方 go 函数就是对这棵二叉树的递归序遍历
 * 每个节点都会结果 3 次，分别在1，2，3位置；实际遍历顺序：
 *
 * 1(1)，2(1)，4(1)，4(2)，4(3)，
 * 2(2)，5(1)，5(2)，5(3)，2(3)，
 * 1(2)，3(1)，6(1)，6(2)，6(3)，
 * 3(2)，7(1)，7(2)，7(3)，3(3)，1(3)
 *
 * 前序（根左右（1））结果：1，2，4，5，3，6，7
 * 中序（左根右（2））结果：4，2，5，1，6，3，7
 * 后序（左右根（3））结果：4，5，2，6，7，3，1
 */
funcion go(head) {
  if(head == null) return;
  // 1 前序
  go(head.left);
  // 2 中序
  go(head.right);
  // 3 后序
}

我们平时用的更多的递归, 可能只有 前序 + 后序, 而后序的特点就很重要了, 它能拿到之前调用栈归阶段时返回的信息.

来看一下 lc.206 反转链表easy 用递归怎么做:

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  if (head === null || head.next == null) return head
  const newHead = reverseList(head.next)
  head.next.next = head
  head = null
  return newHead
}

短短 5 行代码, 初学者真的还挺难理解的😂.为什么直接就 return newHead 就是最后的结果?

这个递归里的 return newHead 是在递归函数的下面, 也就是后序位置, 每次 return 的都是最后一轮递归调用栈返回的那个节点指针, 也就是最后一个节点的指针. 在 tree 递归中, 比如要寻找某个节点, 找到就返回, 那么对于 for 循环中递归递归的调用需要处理, 核心伪代码如下:

const find = () => {
  for (let i = 0; i < list; ++i) {
    if (find(list[i].children)) return true
  }
}

最后说一个对于递归很重要的点, 千万不要用你的脑子去挑战递归的深度, 不要陷入进去, 脑子会爆栈的💥~