路径总和、环形链表、爬楼梯

路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false。

叶子节点是指没有子节点的节点。

思路：!root 的时候直接返回（为了贴合 root = [] 时不存在路径，所以为 false 的情况）；为叶子节点时（!root.left && !root.right）总结这一条路径（记住不是 targetSum === 0，而是 targetSum === root.val）

tsCopy
function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
  if (!root) {
    return false;
  }

  if (!root.left && !root.right) {
    return targetSum === root.val;
  }

  const newTarget = targetSum - root.val;
  return hasPathSum(root.left, newTarget) || hasPathSum(root.right, newTarget);
}

环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

思路：快慢指针。但是要注意 fast === slow 的判定需要在指针移动后进行。放在 while 循环的开头时，对于链表中只有一个元素的情况也会返回 true（但实际上应该是 false）

tsCopy
function hasCycle(head: ListNode | null): boolean {
  let slow = head,
    fast = head;
  while (fast) {
    fast = fast?.next?.next;
    slow = slow?.next;
    if (fast === slow) {
      return true;
    }
  }

  return false;
}

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例：

输入：n = 3

输出：3

解释：有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶

2. 1 阶 + 2 阶

3. 2 阶 + 1 阶

思路 1：斐波那契数列。

由f(n) = f(n - 1) + f(n - 2)，爬到 0 级阶梯的方法数 f(0) = 1，爬到 1 级阶梯的方法数 f(1) = 1，爬到 2 级阶梯的方法数 f(2) = 2

则从 f(0) 和 f(1) 递推到 2 所需要的循环数为 1，递推到 n 所需的循环数为 n - 1

tsCopy
function climbStairs(n: number): number {
  if (n < 3) {
    return n;
  }

  let p0 = 1,
    p1 = 1;
  for (let i = 1; i < n; i++) {
    [p0, p1] = [p1, p0 + p1];
  }

  return p1;
}

思路 2：动态规划。让 memo 数组记忆 dp[n] 的值

tsCopy
function climbStairs(n: number): number {
  let memo = new Array(n + 1).fill(0);

  const dp = (n) => {
    if (n < 3) {
      return n;
    }

    if (memo[n] > 0) {
      return memo[n];
    }

    memo[n] = dp(n - 1) + dp(n - 2);
    return memo[n];
  };

  return dp(n);
}