43. 最小路径和 (minimum-path-sum)

标签

• 动态规划
• 中等

题目

leetcode 传送门

这里不贴题了，leetcode打开就行，题目大意：

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。

相关知识

从动态规划这篇我们了解到动态规划的基本步骤是下面三步：

1. 寻找最优子结构(状态表示)
2. 归纳状态转移方程(状态计算)
3. 边界初始化

然后上篇，我们有两个类似题提前看下，这题就太简单了。 前端算法面试必刷题系列[24]

基本步骤

接下来我们看下面具体问题

1. 状态表示:

• dp(i, j) 表示从左上角出发到 (i, j) 位置的最小路径和。

2. 状态转移方程:

• 由于我们每一步只能向下或向右移动一步，那么其实只有从(i-1, j)或者(i, j-1)这两处走过来，那么转移方程也很简单 dp[i][j] = min(grid[i-1][j], grid[i][j-1])，表示每条路径取较小的来路进行加和

3. 边界初始化:

• 那么下面就是定边界，我们知道最上面一排和最左边一排，只有一种可能来的路径，最顶时，来的路只有从左边1条，最左边来的路只有从上面1条。所以说，i = 0或j = 0时，直接进行来路加和就行，不用比较大小，因为只有一条。

写法实现

var minPathSum = function(grid) {
  let [row, col] = [grid.length, grid[0].length]
  // 可以直接在原来的数组中做原地 DP，不用额外空间
  // 跟上题类似，把边界先加和，左边只能从上走，上边只能从左走
  for (i = 1; i < row; i++) {
    grid[i][0] += grid[i-1][0]
  }
  for (j = 1; j < col; j++) {
    grid[0][j] += grid[0][j-1]
  }
  // 把剩下的非边界位置用递推公式补齐，据题意取来路较小路径的就行
  for (i = 1; i < row; i++) {
    for (j = 1; j < col; j++) {
      grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1])
    }
  }
  return grid[row-1][col-1]
};

let grid = [[1,3,1],[1,5,1],[4,2,1]]
console.log(minPathSum(grid))

44. 加一 (plus-one)

标签

• Array
• 数学
• 简单

题目

leetcode 传送门

这里不贴题了，leetcode打开就行，题目大意：

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

限制:

• 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
• 你可以假设除了整数 0 之外，这个整数不会以零开头。

例子

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。

相关知识

这是个简单题，其实就分三种情况

• 末位无进位，则末位加一即可，比如 13 => 14
• 末位有进位，在中间位置进位停止，整体位数不变，需要找到进位的标志:当前位 %10 == 0，则前一位加 1，直到不为 0 为止，比如 199 => 200
• 末位有进位，并且一直进位到最前方导致结果多出一位，比如 99 => 100

基本步骤

1. 数组倒序遍历，若需要进位，先行 +1
2. 判断当前数字是否大于 9， 大于代表需要进位，否则不进位。
3. 遍历结束，还存在进位，则扩充数组，首位补充 1。

写法实现

var plusOne = function(digits) {
  const len = digits.length
  // 倒序遍历
  for (let i = len - 1; i >= 0; i--) {
    digits[i]++;
    // 加一后看 % 10 是否为 0 ，为0说明有进位
    digits[i] = digits[i] % 10;
    if (digits[i] !== 0) {
      // 直接输出就行
      return digits;
    }
  }
  // 如果遍历到最后都需要进位，说明是要扩充数组
  digits = new Array(len + 1).fill(0)
  digits[0] = 1;
  return digits;
};

console.log(plusOne([9,9,9]))

今天就到这儿，想跟我一起刷题的小伙伴可以加我微信哦 搜索我的微信号infinity_9368，可以聊天说地 加我暗号 "天王盖地虎" 下一句的英文，验证消息请发给我 presious tower shock the rever monster，我看到就通过，暗号对不上不加哈，加了之后我会尽我所能帮你，但是注意提问方式，建议先看这篇文章：提问的智慧

参考