斐波那契数列、接雨水、翻转二叉树

斐波那契数列

题目描述

斐波那契数（通常用 F(n) 表示）形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1

F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n，请计算 F(n)。

答案需要取模 1e9+7(1000000007)，如计算初始结果为：1000000008，请返回 1。

示例：

输入：n = 2

输出：1

解释：F(2) = F(1) + F(0) = 1 + 0 = 1

注意

n < 2 时的情况要单独返回
根据题意，记得取 mod

题解

ts
function fib(n: number): number {
  if (n < 2) {
    return n;
  }

  const mod = 1000000007;

  let f0 = 0,
    f1 = 1;
  for (let i = 2; i <= n; i++) {
    [f0, f1] = [f1, (f1 + f0) % mod];
  }

  return f1;
}

接雨水

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]

输出：6

解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

思路 1：单调栈

我们可以把围成的雨水拆成一层一层的，再相加。

主要思路是维护一个单调递减的栈，存储其下标。当碰到第一个比栈的最小值大的数字，就 while 循环把所有值比它小的数都弹出来，逐层计算每个下标对应高度代表的该层雨水面积。

因为水槽的形成需要三个柱子——左、中，右。所以栈弹出来的第一个数字是下标 mid，此时栈剩下的最后一个数字就是下标 left（stack[stack.length - 1]，别忘记需要去 stack 里取实际数字）。

此时宽度应当是 i - left - 1，高度则应当是 Math.min(height[left], height[i]) - height[mid]（别忘了减去 height[mid]）

题解

ts
function trap(height: number[]): number {
  const stack = [];
  let res = 0;

  for (let i = 0; i < height.length; i++) {
    while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
      const mid = stack.pop();

      // 不存在左柱子
      if (stack.length === 0) {
        break;
      }

      // 左柱子的下标
      const left = stack[stack.length - 1];
      // 这一层的宽度
      const width = i - left - 1;

      // 记得减去 `height[mid]`
      const minHeight = Math.min(height[left], height[i]) - height[mid];
      res += width * minHeight;
    }

    stack.push(i);
  }

  return res;
}

思路 2：双指针

维护 left、right 指针，各自从左右两端开始内移；另外维护 leftMax 和 rightMax，代表当前左右两边最高的柱子高度

每次处理 height[left] 和 height[right] 之间较矮的一方
当 height[?] > ?max，更新 max；否则说明该柱子是有水位高度的（因为左右都比它高），此时计算高度差并加到结果里
指针内移

题解

ts
function trap(height: number[]): number {
  let left = 0,
    right = height.length - 1; // 左右指针
  let leftMax = 0,
    rightMax = 0; // 记录左右最大高度
  let water = 0; // 结果变量

  while (left < right) {
    // 当左右指针相遇时结束
    if (height[left] < height[right]) {
      // 如果左边较矮，处理左侧
      if (height[left] >= leftMax) {
        // 更新左侧最高柱子
        leftMax = height[left];
      } else {
        // 计算左侧存水量
        water += leftMax - height[left];
      }
      left++;
    } else {
      // 如果右边较矮，处理右侧
      if (height[right] >= rightMax) {
        // 更新右侧最高柱子
        rightMax = height[right];
      } else {
        // 计算右侧存水量
        water += rightMax - height[right];
      }
      right--;
    }
  }

  return water;
}

翻转二叉树

题目描述

给你一棵二叉树的根节点 root，翻转这棵二叉树，并返回其根节点。

题解

注意：要递归地翻转子节点，不能直接 [root.left, root.right] = [root.right, root.left]

另外要处理一下 root === null 的情况

ts
function invertTree(root: TreeNode | null): TreeNode | null {
  if (!root) return null;

  [root.left, root.right] = [invertTree(root.right), invertTree(root.left)];

  return root;
}