京公网安备11010502063487号和上一题一样，机器人从网格左上角走到右下角，只能向右或向下；不同的是网格里有障碍（1 表示障碍，0 表示空地），路径不能经过障碍。动态规划的思路不变：走到 (i, j) 的路径数等于上面那格加左边那格，但障碍格子的路径数是 0。边界情形需要小心：起点本身是障碍、终点本身是障碍、第
给定一个 m × n 的非负整数网格，从左上角走到右下角，每次只能向右或向下走一格，求路径上所有数字之和的最小值。和"不同路径"同一个网格结构，但这次每一步有代价，要的是最小值而不是路径数。动态规划：走到 (i, j) 的最小路径和，等于 (i, j) 自己的值，加上走到它上面和
给定一个字符串，判断它是否是一个有效的数字。有效数字由可选的符号、一个数字部分（整数，或者带小数点的小数，小数点前后至少有一侧有数字）、和可选的指数部分（`e` 或 `E`，后面跟可选的符号和至少一位整数）组成，中间不能有空格。规则不多，但细节很杂：`"4."` 和 `".5"`
给定一个用数字数组表示的非负整数（最高位在最前面，没有前导 0，`[1, 2, 3]` 表示 123），返回加 1 之后的数字数组。做法很直接：从最低位开始，遇到不是 9 的位就加 1 并结束，遇到 9 就变成 0 并继续向前进位；如果所有位都是 9，就在最前面补一个 1。这道题
给定两个用字符串表示的二进制数，返回它们的和（同样是二进制字符串）。做法就是竖式加法：从两个字符串的最低位（最右边）往左，逐位相加，每一位的结果是 `(a位 + b位 + 进位) % 2`，新的进位是 `(a位 + b位 + 进位) / 2`；两个数都走完之后如果还有进位，还要再
给定一组单词和一个行宽，把单词排成若干行，每行恰好 `maxWidth` 个字符，要求：每行尽量多放单词（贪心）；单词之间至少一个空格；中间的行两端对齐，多余的空格尽量平均地分到单词之间的空隙里，如果分不均匀，左边的空隙多一个；最后一行左对齐，单词之间只有一个空格，右边补空格；只
给定一个非负整数 x，计算并返回 x 的算术平方根向下取整的结果，不允许使用内置的指数或平方根函数。因为只要整数部分，可以用二分查找：找最大的整数 r，使得 r × r ≤ x。这道题最有价值的一点是整数溢出：直接写 `mid * mid <= x`，在 32 位整数里当 mid
爬 n 阶楼梯到楼顶，每次可以爬 1 或 2 阶，问有多少种不同的方法。到第 n 阶的最后一步，要么是从第 n - 1 阶爬 1 阶，要么是从第 n - 2 阶爬 2 阶，所以方法数 f(n) = f(n-1) + f(n-2)，这就是斐波那契数列（f(0) = f(1) = 1
给定一个 Unix 风格的绝对路径，把它简化成规范路径：`.` 表示当前目录，忽略；`..` 表示上一级目录；连续的多个 `/` 视为一个；结果以 `/` 开头，目录之间用单个 `/` 连接，末尾不带 `/`（根目录本身除外）。三个点 `...` 或者 `..a` 这样的名字是合
给定两个字符串 `word1` 和 `word2`，求把 `word1` 变成 `word2` 所需的最少操作数，操作只有三种：插入一个字符、删除一个字符、替换一个字符。这是经典的二维动态规划：`dp[i][j]` 表示 `word1` 的前 i 个字符变成 `word2` 的前
给定一个 m × n 的矩阵，如果某个元素是 0，就把它所在的整行和整列都设为 0，要求原地操作。最容易想到的做法是用两个集合记下所有含 0 的行和列，最后统一清零，额外空间 O(m + n)。进阶要求是只用 O(1) 额外空间：把矩阵自己的第一行和第一列当作"这一行要清零""这
给定一个 m × n 的矩阵，每一行从左到右升序，并且每一行的第一个数大于上一行的最后一个数。判断目标值是否在矩阵中。这个特殊的排列意味着：把所有行首尾相接，得到的是一个长度 m × n 的升序一维数组。所以可以直接对这个"虚拟"数组做二分查找，一维下标 k 对应第 `k / n