真题训练
最长回文子串
中心扩散
function longestPalindrome(s) {
const len = s.length;
let res = "";
if (len < 2) return s;
for (let i = 0; i < len; i++) {
if (len % 2 === 0) {
// 长度为奇数
helper(i, i);
} else {
// 长度为偶数
helper(i, i + 1);
}
}
function helper(i, j) {
while (i >= 0 && j < len && s[i] === s[j]) {
i--;
j++;
}
if (j - 1 - (i + 1) + 1 > res.length) {
res = s.slice(i + 1, j);
}
}
return res;
}
动态规划
题干中的“最长”二字，表明了这是一道“求最值”型问题。前面我们说过，看到最值，就要把动态规划调度进可用解题工具里。
继续往下分析，发现这道题中，较长回文子串中可能包含较短的回文子串（最优子结构）
我们拿到的原始素材是一个字符串序列，符合“序列型”动态规划的特征。大家现在已经知道，对于序列型动态规划，我们总是需要以它的索引为线索去构造一维或二维的状态数组。对于这道题来说，由于定位任意子串需要的是两个索引，因此我们的状态数组应该是一个二维数组：
// 初始化一个二维数组
let dp = [];
const len = s.length;
for (let i = 0; i < len; i++) {
dp[i] = [];
}
由于 i 和 j 分别表示子串的两个端点，只要我们明确了这两个值，就能间接地求出子串的长度。因此 dp[i][j]不必额外记录长度这个状态，只需要记录该区间内的字符串是否回文。这里我们把回文记为 1（或 true），不回文记为 0（或 false）。
按照这个思路走下去，我们需要关注到的无疑就是字符串的两个端点 s[i]和 s[j]了。当遍历到一对新的端点的时候，有以下两种可能的状态转移情况：
- s[i] === s[j]。这种情况下，只要以 s[i+1]和 s[j-1]为端点的字符串是回文字符串，那么 dp[i][j] = 1 就成立，否则 dp[i][j] = 0。
- s[i] !== s[j]。这种情况下，一定有 dp[i][j]=0。
到这里，我们也就明确到了这道题的状态转移方程，这里我用编码表达如下：
if (s[i] === s[j]) {
dp[i][j] = dp[i + 1][j - 1];
} else {
dp[i][j] = 0;
}
找出了状态转移方程，现在来找边界值。这里大家需要注意的是：如果在一个序列中，涉及到了 i、j 两个索引，那么一定要关注到 i===j 这种特殊情况。在这道题中，由于 i===j 时，dp[i][i]对应的是一个单独的字母，单独的字母必然回文（长度为 1），因此 dp[i][i] = 1 就是这道题的边界值（或者说初始值）。
function longestPalindrome(s) {
const len = s.length;
if (len < 2) return s;
const dp = [];
for (let i = 0; i < len; i++) {
dp[i] = [];
}
// 初始化最长回文子串的两个端点值
let st = 0,
end = 0;
// 初始化最长回文子串的初始值为1
for (let i = 0; i < len; i++) {
dp[i][i] = 1;
}
// 这里为了降低题目的复杂度，我们预先对悬念比较小的 s[i][i+1] 也做了处理
for (let i = 0; i < len - 1; i++) {
if (s[i] === s[i + 1]) {
dp[i][i + 1] = 1;
st = i;
end = i + 1;
}
}
// n 代表子串的长度，从3开始递增
for (let n = 3; n <= len; n++) {
// 下面的两层循环，用来实现状态转移方程
for (let i = 0; i <= len - n; i++) {
let j = i + n - 1;
if (dp[i + 1][j - 1]) {
if (s[i] === s[j]) {
// 若定位到更长的回文子串，则更新目标子串端点的索引值
dp[i][j] = 1;
st = i;
end = j;
}
}
}
}
// 最后依据端点值把子串截取出来即可
return s.substring(st, end + 1);
}
从前序（先序）与中序遍历序列构造二叉树
题目描述：根据一棵树的前序遍历与中序遍历构造二叉树。
前序序列当前范围的头部索引记为 preL，尾部索引记为 preR；把中序序列当前范围的头部索引记为 inL，尾部索引记为 inR
根结点(p1)在中序序列中的坐标索引为 k，于是左子树的结点个数就可以通过计算得出：
numLeft = k - 1
那么左子树在前序序列中的索引区间就是 [preL+1,preL+numLeft]，在中序序列中的索引区间是 [inL, k-1]；右子树在前序序列的索引区间是 [preL+numLeft+1, preR]，在中序序列中的索引区间是 [k+1, inR]。
function buildTree(preOrder, inOrder) {
const len = preOrder.length;
function build(preL, preR, inL, inR) {
if (preL > preR || inL > inR) return null;
const root = new TreeNode();
root.val = preOrder[preL];
const k = inOrder.indexOf(root.val);
const numLeft = k - inL;
root.left = build(preL + 1, preL + numLeft, inL, k - 1);
root.right = build(preL + numLeft + 1, preR, k + 1, inR);
return root;
}
return build(0, len - 1, 0, len - 1);
}
从后序（先序）与中序遍历序列构造二叉树
function buildTree(inOrder, postOrder) {
const len = inOrder.length;
function build(inL, inR, postL, postR) {
if (inL > inR || postL > postR) return null;
const root = new TreeNode(postOrder[postR]);
const k = inOrder.indexOf(root.val);
const numLeft = k - inL;
root.left = build(inL, k - 1, postL, postL + numLeft - 1);
root.right = build(k + 1, inR, postL + numLeft, postR);
return root;
}
return build(0, len - 1, 0, len - 1);
}
复制带随机指针的链表
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深拷贝。
function copyRandomList(head) {
// 处理边界条件
if (!head) return null;
// 初始化copy的头部结点
let copyHead = new Node();
// 初始化copy的游标结点
let copyNode = copyHead;
// 初始化hashMap
const hashMap = new Map();
let curr = head;
// 首次循环，正常处理链表的复制
while (curr) {
copyNode.val = curr.val;
copyNode.next = curr.next ? new Node() : null;
// 存储原节点和对应的copy节点的关系，用于random节点的拷贝 !!!!
hashMap.set(curr, copyNode);
curr = curr.next;
copyNode = copyNode.next;
}
// 将游标复位到head
curr = head;
// 将copy链表的游标也复位到copyHead
copyNode = copyHead;
// 再搞个循环，特殊处理random关系
while (curr) {
copyNode.random = curr.random ? hashMap.get(curr.random) : null;
curr = curr.next;
copyNode = copyNode.next;
}
return copyHead;
}
岛屿数量问题
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
每座岛屿只能由水平或竖直方向上相邻的陆地连接而成。
若当前所在位置是 1，从 1 出发，可以抵达的所有1 都和它算作同一个岛屿。
看到“所有”，必须想到“枚举”！看到“枚举”，必须回忆起 DFS 和 BFS！
- 岛屿的统计思路：从起点出发，遵循“不撞水面（也就是 0）不回头”的原则，枚举当前可以触及的所有 1。当枚举无法继续进行时，说明当前这座岛屿被遍历完毕，记为一个。也就是说每完成一次 DFS，就累加一个岛屿。
- 避免重复计算的方法：每遍历过一个 1，就把它置为 0，后续再次路过时就会自动忽略它啦
function numIslands(grid) {
// moveX[i], moveY[i] 表示对当前格子的 上下左右四个方向的遍历
const moveX = [0, 0, -1, 1];
const moveY = [-1, 1, 0, 0];
if (!grid || !grid.length || !grid[0].length) {
return 0;
}
let count = 0;
const row = grid.length,
column = grid[0].length;
for (let i = 0; i < row; i++) {
for (let j = 0; j < column; j++) {
if (grid[i][j] === 1) {
dfs(grid, i, j);
// 每完成一个 dfs，就累加一个岛屿
count++;
}
}
}
function dfs(grid, i, j) {
if (
i < 0 ||
i >= grid.length ||
j < 0 ||
j >= grid[0].length ||
grid[i][j] === 0
) {
return;
}
// 遍历过的坑位都置0，防止反复遍历
grid[i][j] = 0;
// 遍历完当前的1，继续去寻找下一个1
for (let k = 0; k < 4; k++) {
dfs(grid, i + moveX[k], j + moveY[k]);
}
}
return count;
}
后续我们遇到的一些题目，一旦和这道题一样，强调了“水平”、“垂直”方向上的相邻关系，我们就可以无脑复用这个套路啦~
“扫地机器人”问题
房间（用格栅表示）中有一个扫地机器人。格栅中的每一个格子有空和障碍物两种可能。
扫地机器人提供 4 个 API，可以向前进，向左转或者向右转。每次转弯 90 度。
当扫地机器人试图进入障碍物格子时，它的碰撞传感器会探测出障碍物，使它停留在原地。
请利用提供的 4 个 API 编写让机器人清理整个房间的算法。
interface Robot {
// 若下一个方格为空，则返回true，并移动至该方格
// 若下一个方格为障碍物，则返回false，并停留在原地
boolean move();
// 在调用turnLeft/turnRight后机器人会停留在原位置
// 每次转弯90度
void turnLeft();
void turnRight();
// 清理所在方格
void clean();
}
输入：
room = [
[1,1,1,1,1,0,1,1],
[1,1,1,1,1,0,1,1],
[1,0,1,1,1,1,1,1],
[0,0,0,1,0,0,0,0],
[1,1,1,1,1,1,1,1]
],
row = 1,
col = 3
房间格栅用 0 或 1 填充。0 表示障碍物，1 表示可以通过。 机器人从 row=1，col=3 的初始位置出发。在左上角的一行以下，三列以右。
思路分析
这道题涉及到对二维数组网格的枚举，可能与岛屿数量问题的基本思路一致（将 DFS 作为优先方法来考虑）。虽然我不知道对不对，但是沿着这个思路往下多分析几步总是好的：
- 机器人从初始位置出发，检查上下左右四个方向是否有障碍物，进而决定是否进入对应方向的格子完成清扫。
- 因为题目强调了“所有可抵达的格子都是相连的，亦即所有标记为 1 的格子机器人都可以抵达”，所以我们借助 DFS 尝试枚举所有可抵达的格子是完全没有问题的。DFS 的主要递归逻辑其实就是步骤 1。
- 当某一个方向已经“撞到南墙”后，机器人应该逐渐回溯到上一个位置，尝试新的方向。
- 最后，由于递归边界其实就是障碍物/已经清扫过的格子。所以别忘了对已经清扫过的格子做个标记。
假设机器人现在所在的格子坐标是 (i, j)，它的旋转角度以及对应的前进坐标之间就有以下关系（结合题意我们把“上”这个初始方向记为 0 度）：
（定义逻辑）
// 初始化角度为 0 度
let dir = 0
...
（判断逻辑）
// 将角度和前进坐标对应起来
switch(dir) {
// 0度的前进坐标，是当前坐标向上走一步
case 0:
x = i - 1
break
// 90度（顺时针）的前进坐标，是当前坐标向右走一步
case 90:
y = j + 1
break
// 180度（顺时针）的前进坐标，是当前坐标向下走一步
case 180:
x = i + 1
break
// 270度（顺时针）的前进坐标，是当前坐标向左走一步
case 270:
y = j - 1
break
default:
break
}
...
（叠加逻辑）
// 注意这里我给机器人的规则就是每次顺时针转一个方向，所以是 turnRight
robot.turnRight()
// turnRight的同时，dir需要跟着旋转90度
dir += 90
// 这里取模是为了保证dir在[0, 360]的范围内变化
dir %= 360
如何优雅地对已处理过的格子做标记
请思考一下，在这道题里，是否还可以沿用“岛屿数量”问题中直接修改二维数组的思路？说实话，没试过，也不建议——就这道题来说，题给的四个 API 都不是我们自己实现的，一旦改了全局的 room 变量，谁知道会影响哪个 API 呢。保险起见，我们应该优先考虑不污染 room 变量的实现方法，这里我借助的是 Set 数据结构：
以下是定义逻辑）
//初始化一个 set 结构来存储清扫过的坐标
const boxSet = new Set()
...
（以下是判断逻辑）
// 标识当前格子的坐标
let box = i + '+' + j
// 如果已经打扫过，那么跳过
if(boxSet.has(box)) return
// 打扫当前这个格子
robot.clean()
// 记住这个格子
boxSet.add(box)
function cleanRoom(robot) {
// 初始化一个 set 结构来存储清扫过的坐标
const boxSet = new Set();
// 初始化机器人的朝向
let dir = 0;
// 进入 dfs
dfs(robot, boxSet, 0, 0, 0);
function dfs(robot, boxSet, i, j, dir) {
// 记录当前格子的坐标
let box = i + "+" + j;
// 如果已经打扫过，那么跳过
if (boxSet.has(box)) return;
// 打扫当前这个格子
robot.clean();
// 记住这个格子
boxSet.add(box);
// 四个方向试探
for (let k = 0; k < 4; k++) {
// 如果接下来前进的目标方向不是障碍物（也就意味着可以打扫）
if (robot.move()) {
// 从当前格子出发，试探上右左下
let x = i,
y = j;
// 处理角度和坐标的对应关系
switch (dir) {
case 0:
x = i - 1;
break;
case 90:
y = j + 1;
break;
case 180:
x = i + 1;
break;
case 270:
y = j - 1;
break;
default:
break;
}
dfs(robot, boxSet, x, y, dir);
// 一个方向的dfs结束了，意味着撞到了南墙，此时我们需要回溯到上一个格子
robot.turnLeft();
robot.turnLeft();
robot.move();
robot.turnRight();
robot.turnRight();
}
// 转向
robot.turnRight();
dir += 90;
dir %= 360;
}
}
}
编码复盘
dfs(robot, boxSet, x, y, dir);
robot.turnLeft();
robot.turnLeft();
robot.move();
robot.turnRight();
robot.turnRight();
结合一下代码的上下文，这里我给机器人的设定是：
你在进入每一个格子后，都需要基于当前方向顺时针旋转四次
在这个前提下，机器人在 (x,y) 这个格子工作完之后，它的朝向一定是和刚进入 (x,y)时的朝向是一样的，区别在于在原来的基础上多走了一个格子
此时后一个网格的机器人要想退回“事前”的状态，它必须先旋转 180 度，然后前进一步，再旋转 180 度。而“旋转 180 度”这个动作，可以通过连续两次 turnLeft 或者 turnRight 来完成。
“合并区间”问题
给出一个区间的集合，请合并所有重叠的区间。
示例
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
function merge(intervals) {
// 定义结果数组
const result = [];
// 处理区间的边界情况
if (!intervals || !intervals.length) {
return [];
}
// 缓存区间个数
const len = intervals.length;
// 将所有区间按照第一个元素大小排序
intervals.sort(function(a, b) {
return a[0] - b[0];
});
prev = intervals[0];
for (let i = 1; i < len; i++) {
cur = intervals[i];
if (cur[0] <= prev[1]) {
prev[1] = Math.max(cur[1], prev[1]);
} else {
result.push(prev);
prev = cur;
}
}
result.push(prev);
return result;
}
接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
对于凹槽来说，决定它高度的不是与它相邻的那个柱子，而是左侧最高柱子和右侧最高柱子中，较矮的那个柱子。
function trap(height) {
let ans = 0;
let left = 0,
right = height.length - 1;
let leftMax = 0,
rightMax = 0;
while (left < right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if (leftMax < rightMax) {
ans += leftMax - height[left];
++left;
} else {
ans += rightMax - height[right];
--right;
}
}
return ans;
}
K 个一组翻转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序
unction reverseList(a, b) {
let prev = null,
cur = a,
next;
while (cur !== b) {
next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}
function reverseKGroup(head, k) {
let a = head,
b = head;
for (let i = 0; i < k; i++) {
// 不足 k 个，不需要反转，base case
if (b === null) {
return head;
} else {
b = b.next;
}
}
const newHead = reverseList(a, b);
a.next = reverseKGroup(b, k);
return newHead;
}
柱状图中的最大矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。
function largestRectangleArea(heights) {
if (!heights || !heights.length) return 0;
let max = -1;
const len = heights.length;
for (let i = 0; i < len; i++) {
if (i === len - 1 || heights[i] > heights[i + 1]) {
let minHeight = heights[i];
for (let j = i; j >= 0; j--) {
minHeight = Math.min(minHeight, heights[i]);
max = Math.max(minHeight * (i - j + 1), max);
}
}
}
return max;
}
寻找二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
function lowestCommonAncestor(root, p, q) {
let ans = null;
// 判断以root为根节点的树是否包含p/q节点
function dfs(root, p, q) {
if (!root) return false;
const left = dfs(root.left, p, q);
const right = dfs(root.right, p, q);
if (
(left && right) ||
((root.val === p.val || root.val === q.val) && (left || right))
) {
ans = root;
}
return lson || rson || root.value === p.value || root.value === q.value;
}
dfs(root, p, q);
return ans;
}
寻找两个正序数组的中位数
- 合并两个有序数组；然后根据长度找出中位数
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
题目中若要求 log 级别的时间复杂度，则优先使用二分法解题
nums1 切割后左侧的元素个数+nums2 切割后左侧元素的个数===两个数组长度和的一半
// slice1和slice2分别表示R1的索引和R2的索引
slice1 + slice2 === Math.floor((nums1.length + nums2.length) / 2);
nums1、nums2 的长度是已知的，这也就意味着只要求出 slice1 和 slice2 中的一个，另一个值就能求出来了。
因此我们的大方向先明确如下：
用二分法定位出其中一个数组的 slice1，然后通过做减法求出另一个数组的 slice2
“其中一个数组”到底以 nums1 为准还是以 nums2 为准？答案是以长度较短的数组为准，这样做可以减小二分计算的范围
这里我们假设 nums1 和 nums2 分别是以下两个数组：
nums1 = [5, 6, 7];
nums2 = [1, 2, 4, 12];
用二分法做题，首先需要明确二分的两个端点。在没有任何多余线索的情况下，我们只能把二分的端点定义为 nums1 的起点和终点:
// 初始化第一个数组二分范围的左端点
let slice1L = 0;
// 初始化第一个数组二分范围的右端点
let slice1R = len1;
基于此去计算 slice1 的值：
slice1 = Math.floor((slice1R - slice1L) / 2) + slice1L;
然后通过做减法求出 slice2：
slice2 = Math.floor(len / 2) - slice1;
第一次二分，两个数组分别被分割为如下形状：
L1 R1
nums1 = [5, |6, 7]
L2 R2
nums2 = [1, 2, |4, 12]
如何确认你的二分是否合理？标准只有一个——分割后，需要确保左侧的元素都比右侧的元素小，也就是说你的两个分割线要间接地把两个数组按照正序分为两半。这个标准用变量关系可以表示如下：
L1 <= R1;
L1 <= R2;
L2 <= R1;
L2 <= R2;
由于数组本身是正序的，所以 L1 <= R1、L2 <= R2 是必然的，我们需要判断的是剩下两个不等关系：
若发现 L1 > R2，则说明 slice1 取大了，需要用二分法将 slice1 适当左移；若发现 L2 > R1，则说明 slice1 取小了，需要用二分法将 slice1 适当右移：
// 处理L1>R2的错误情况
if (L1 > R2) {
// 将slice1R左移，进而使slice1对应的值变小
slice1R = slice1 - 1;
} else if (L2 > R1) {
// 反之将slice1L右移，进而使slice1对应的值变大
slice1L = slice1 + 1;
}
只有当以上两种偏差情况都不发生时，我们的分割线才算定位得恰到好处，此时就可以执行取中位数的逻辑了：
// len表示两个数组的总长度
if (len % 2 === 0) {
// 偶数长度对应逻辑（取平均值）
const L = L1 > L2 ? L1 : L2;
const R = R1 < R2 ? R1 : R2;
return (L + R) / 2;
} else {
// 奇数长度对应逻辑（取中间值）
const median = R1 < R2 ? R1 : R2;
return median;
}
// 双指针
function findMedianSortedArrays(nums1, nums2) {
const n1 = nums1.length,
n2 = nums2.length;
const len = n1 + n2;
let prevValue = -1;
let curValue = -1;
let p1 = 0,
p2 = 0;
for (let i = 0; i <= Math.floor(len / 2); i++) {
prevValue = curValue;
if (p1 < n1 && (p2 >= n2 || nums1[p1] < nums2[p2])) {
curValue = nums1[p1++];
} else {
curValue = nums2[p2++];
}
}
return len % 2 === 0 ? (prevValue + curValue) / 2 : curValue;
}
// 二分法
function findMedianSortedArrays(nums1, nums2) {
const len1 = nums1.length;
const len2 = nums2.length;
// 确保直接处理的数组（第一个数组）总是较短的数组
if (len1 > len2) {
return findMedianSortedArrays(nums2, nums1);
}
const len = len1 + len2;
let start = 0,
end = len - 1;
let partLen1 = 0;
let partLen2 = 0;
while (start <= end) {
partLen1 = Math.floor((start + end) / 2);
partLen2 = Math.floor(len / 2) - partLen1;
const l1 = partLen1 === 0 ? -Infinity : nums1[partLen1 - 1];
const r1 = partLen1 === len1 ? Infinity : nums1[partLen1];
const l2 = partLen2 === 0 ? -Infinity : nums2[partLen2 - 1];
const r2 = partLen2 === len2 ? Infinity : nums2[partLen2];
if (l1 > r2) {
end = partLen1 - 1;
} else if (l2 > r1) {
start = partLen1 + 1;
} else {
return len % 2 === 0
? (Math.max(l1, l2) + Math.min(r1, r2)) / 2
: Math.max(l1, l2);
}
}
return -1;
}
“粉刷房子”问题
假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的矩阵来表示的。 例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。请你计算出粉刷完所有房子最少的花费成本。
f[i][x] =
Math.min(f[i - 1][x以外的索引1号], f[i - 1][x以外的索引2号]) + costs[i][x];
x 以外的索引 1 号、 x 以外的索引 2 号的原因是相邻的两个房子颜色不能相同
其中 f[i][x]对应的是当粉刷到第 i 个房子时，使用第 x（x=0、1、2）号油漆对应的总花费成本的最小值。
状态的初始值，就是当 i=0 时对应的三个值：
f[0][0] = costs[0][0];
f[0][1] = costs[0][1];
f[0][2] = costs[0][2];
f[0][0]、f[0][1]、f[0][2]分别表示当粉刷到第 0 个房子时，对它使用 0 号、1 号、2 号油漆对应的总花费成本。此时由于只粉刷了一个房子，所以总花费成本就等于房子本身的花费成本。
function minCosts(costs) {
if (!costs || !costs.length) return 0;
const len = costs.length;
const f = new Array(len);
for (let i = 0; i < len; i++) {
f[i] = new Array(3);
}
f[0][0] = costs[0][0];
f[0][1] = costs[0][1];
f[0][2] = costs[0][2];
// 开始更新刷到每一个房子时的状态值
for (let i = 1; i < len; i++) {
// 更新刷到当前房子时，给当前房子选用第0种油漆对应的最小总价
f[i][0] = Math.min(f[i - 1][1], f[i - 1][2]) + costs[i][0];
// 更新刷到当前房子时，给当前房子选用第1种油漆对应的最小总价
f[i][1] = Math.min(f[i - 1][2], f[i - 1][0]) + costs[i][1];
// 更新刷到当前房子时，给当前房子选用第2种油漆对应的最小总价
f[i][2] = Math.min(f[i - 1][1], f[i - 1][0]) + costs[i][2];
}
// 返回刷到最后一个房子时，所有可能出现的总价中的最小值
return Math.min(f[len - 1][0], f[len - 1][1], f[len - 1][2]);
}