两道迷你算法题 - 爬楼梯 & 链表回环

最前

算法题，开发人员求职时或许会遇到的拦路小怪。

一些碎碎念

背景

吾辈曾经（久远的曾经）做过的算法题目并不多，大多数是在 Leetcode 平台完成，印象深刻的题目有那么一些，而这当中，“最有好感”的是以下两个题目：

爬楼梯 —— 好感原因：吾辈总觉得这个题目是带着好兆头的寓意，所谓路漫漫，一步两步向上爬嘛。
回文链表 —— 好感原因：该题目的其中一个解法，只要脑洞够大，漫天联想，就会觉得这不就是诺兰的电影：信条 - TENET 里的情节！

所以本文成行，一方面，是关于题解的分享；更多的是出于私心，将其记录在这里， 留个曾经吾辈也有过一段刷算法题时光的纪念。

电影信条官方海报

正文

题目：爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

背后的数学规律

本题目以下的解法基本涉及菲波那切数列特征，这里不过多展开，简要来说，本题目符合这样的数学规律：走到第 n 阶的解法等于走到第 n - 1 阶的解法，加上走到第 n - 2 阶的解法之和

另外本题目的相关解法中，也容易延伸到另一个概念：动态规划，本文不做展开

解法 1 - 一般递归

实现代码；

function climbStairs(n) {
  if (n < 3) {
    return n;
  }
  return climbStairs(n - 1) + climbStairs(n - 2);
}

解法 2 - 递归优化 + 缓存数组

const cache = [1, 1, 2];
function climbStairs(n) {
  if (cache[n]) {
    return cache[n];
  }

  cache[n] = climbStairs(n - 1) + climbStairs(n - 2);

  return cache[n];
}

该解法，可以写为更简短的版本，不过适当牺牲了可读性，如下：

function climbStairs(n, cache = [1, 1, 2]) {
  return (
    cache[n] ??
    (cache[n] = climbStairs(n - 1, cache) + climbStairs(n - 2, cache))
  );
}

对该写法的简略补充

1. 将用于缓存计算结果的变量 cache 形参化，免去了声明 cache 的步骤，且在形参定义处赋默认初始值
这里简短提下赋默认初始值的细节，Leetcode 平台调用的时候，固定调用形式是：climbStairs([someNum])，显然的，平台不会因为我们声明了第二形参，而为我们传入相应参数。
2. 学习编程语言的基础中（不局限在 JavaScript），会提到表达式的概念，比如像 0 > 1 这样的“判断表达式”，而像 “a = a + 2” 这样的语句实际也是一个表达式：“赋值表达式”，容易忽略的是：赋值表达式本身也是有返回值的，所以我们可以如上的：
return cache[n] = p1 + p2
但显然的，日常书写中并不推荐这样的写法，前文已经提及，其为了所谓精简代码而牺牲了可读性

解法 3 - 常规循环

function climbStairs(n) {
  const cache = [1, 1, 2];
  if (n < 3) {
    return cache[n];
  }
  for (let i = 3; i <= n; i++) {
    cache[i] = cache[i - 1] + cache[i - 2];
  }
  return cache[n];
}

使用常规循环遍历的解法，对于不习惯递归的朋友，或许显得更加友好。但总的来说，该题目下，使用递归也是很容易理解的。

解法 4 - “晦涩”递归

开门见山的，实现代码如下：

function climbStairs(n) {
  let ansCou = 0;
  (function action(step) {
    if (step > n) return;
    if (step === n) {
      ansCou++;
      return;
    }
    action(step + 1);
    action(step + 2);
  })(0);
  return ansCou;
}

tip

该解法虽然不能通过 Leetcode 的测试用例，但也提供了另一个新的解题角度，且吾辈之前简单翻阅社区的各种题解中，并没有看到如上的解法。
该解法，可能初看有些晦涩（至少对于当初的吾辈是如此），但是细看就是利用递归解决问题的巧妙思路；且对比上面的运用菲波那切数列特征求解的思路，该解法从直觉上更贴合题目的表述。
👉 解法参考自：Eloquent Javascript(2nd) 第三章节
另外，如此的解法，实际也非常适合解题人一开始并不知道菲波那切数列特征的情况。
以及，该解法非常容易解决题目变体：比如，题目更改为一次可以爬 1 或 2 个或 3 个台阶，那么只需要对上述代码更改为：
在action(step + 2);后再添加 action(step + 3)即可

补充 - Eloquent Javascript 摘录

But recursion is not always just a less-efficient alternative to looping. Some problems are much easier to solve with recursion than with loops. Most often these are problems that require exploring or processing several “branches”, each of which might branch out again into more branches.

Consider this puzzle: by starting from the number 1 and repeatedly either adding 5 or multiplying by 3, an infinite amount of new numbers can be produced. How would you write a function that, given a number, tries to find a sequence of such additions and multiplications that produce that number? For example, the number 13 could be reached by first multiplying by 3 and then adding 5 twice, whereas the number 15 cannot be reached at all.

Here is a recursive solution:

function findSolution(target) {
  function find(current, history) {
    if (current == target)
      return history;
    else if (current > target)
      return null;
    else
      return find(current + 5, "(" + history + " + 5)") ||
             find(current * 3, "(" + history + " * 3)");
  }
  return find(1, "1");
}

console.log(findSolution(24));
// → (((1 * 3) + 5) * 3)

题目：回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

解法 1 - 暴力解法

var isPalindrome = function (head) {
  const arr = [];
  let node = head;
  while (node) {
    arr.push(node.val);
    node = node.next;
  }

  for (let i = 0, len = arr.length; i < Math.ceil((len - 1) / 2); i++) {
    if (arr[i] !== arr[len - 1 - i]) {
      return false;
    }
  }
  return true;
};

不推荐该解法的原因在于：没有用上链表的特性，实际上述的解法，就是传统的对字符串、或者数组是否回文的简单判断了。

解法 2 - 快慢指针 + 链表反转

该解法需额外声明对链表反转的功能函数如下：

function reverse(head) {
  let prev = null;
  while (head) {
    let nextNode = head.next;
    head.next = prev;
    prev = head;
    head = nextNode;
  }

  return prev;
}

以下是使用快慢指针的解法，细节之后提及：

function isPalindrome(head) {
  let fast = head,
    slow = head;

  while (fast && fast.next) {
    fast = fast.next.next;
    slow = slow.next;
  }

  if (fast) {
    slow = slow.next; // 🎈 奇数个节点的情况下，正中间的节点不用判断。 - slow 再后移一位。
  }

  slow = reverse(slow);
  fast = head;

  while (slow) {
    if (slow.val !== fast.val) {
      return false;
    }
    slow = slow.next;
    fast = fast.next;
  }
  return true;
}

解法 3 - 🎞 “TENET 信条”递归

function isPalindrome(head) {
  let headReal = head;

  return check(head);

  function check(headNode) {
    if (!headNode) return true;
    const res = check(headNode.next) && headNode.val === headReal.val;
    headReal = headReal.next; // 🎈 我们需要在递归过程中手动的去更改 headReal 指向
    return res;
  }
}

官方表述：如果使用递归反向迭代节点，同时使用递归函数外的变量向前迭代，就可以判断链表是否为回文。

注意：上面代码中，当第一次尝试判断 headReal.val === headNode.val 时，因为之前的不断的 check(headNode.next) 的"递归下探",此时 headNode 实际指向的是末尾的节点。

电影信条剧照

之后就如🎥 电影信条的剧情：头尾节点向中间靠拢(对于 headReal 指针，是通过手动声明，不断的右移。而 headNode 则是随着递归深度不断往上返回值，—— 当 check(headNode.next) 返回 true 时，再进而判断 headNode.val === headReal.val , 则呈现一种“左移”的效果)。两者在中间节点交汇后，最后再分开继续朝向头尾结点（正是电影里双男主贯穿全剧情的钳形行动本身）