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

题目

leetcode 传送门

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

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

基本步骤

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

状态表示:

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

状态转移方程:

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

边界初始化:

那么下面就是定边界，我们知道最上面一排和最左边一排，只有一种可能来的路径，最顶时，来的路只有从左边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)

题目

leetcode 传送门

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

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

限制:

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

例子

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

基本步骤

数组倒序遍历，若需要进位，先行 +1
判断当前数字是否大于 9，大于代表需要进位，否则不进位。
遍历结束，还存在进位，则扩充数组，首位补充 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，我看到就通过，暗号对不上不加哈，加了之后我会尽我所能帮你，但是注意提问方式，建议先看这篇文章：提问的智慧

参考

常见问题FAQ

免费下载或者VIP会员专享资源能否直接商用？: 本站所有资源版权均属于原作者所有，这里所提供资源均只能用于参考学习用，请勿直接商用。若由于商用引起版权纠纷，一切责任均由使用者承担。更多说明请参考 VIP介绍。

提示下载完但解压或打开不了？: 最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量，若小于网盘提示的容量则是这个原因。这是浏览器下载的bug，建议用百度网盘软件或迅雷下载。若排除这种情况，可在对应资源底部留言，或联络我们.。

找不到素材资源介绍文章里的示例图片？: 对于PPT，KEY，Mockups，APP，网页模版等类型的素材，文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买，且本站不负责(也没有办法)找到出处。同样地一些字体文件也是这种情况，但部分素材会在素材包内有一份字体下载链接清单。