leetcode动态规化习题二

2020-01-12 by 杜宏伟

leetcode 动态规划习题第二集。

v[i]是第i个元素的值。v[i][j]是第i行,第j列元素的值

最长有效括号

给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。

dp[i]表示第i个元素结尾的有效括号的长度。初始化dp[i]全为0。因为(结尾的一定不是有效的,一定为0。所以只需要更新)结尾的位置即可

if (s.charAt(i) == ')') {
  if (s.charAt(i - 1) == '(') {
    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
  } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
  }
  maxans = Math.max(maxans, dp[i]);
}

这种实战意义不大。因为推导公式不容易想出,也很容易出错,知道可以这样做即可。不是唯一方式,用栈的方式实用性更好。

编辑距离

给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

插入一个字符
删除一个字符
替换一个字符

示例 1:

输入: word1 = "horse", word2 = "ros"
输出: 3
解释: 
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2:

输入: word1 = "intention", word2 = "execution"
输出: 5
解释: 
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

dp[i][j] word1的前i个字符转成word2的前j个字符需要的最少操作数

let word1 = 'aaa'
let word2 = 'abcd'
let m = word1.length, n = word2.length

let dp = []
//第一列为从空字符串到 word2 的第一个字符
for (let i = 0; i < m+1; i++) {
  dp[i] = [i]
}
//第一行为从 word1 的第一个字符到空字符串
for (let j = 0; j < n+1; j++) {
  dp[0][j] = [j]
}
//递推从 word1 的第 i 个字符转换到 word2 的第 j 个字符需要的最少步数
for (let i = 1; i < m; i++) {
  for (let j = 1; j < n; j++) {
    if (word1[i] == word2[j]) {
      dp[i][j] = dp[i][j]
    }
    else {
      dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
    }

  }
}

交错字符串

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

示例 1:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true

示例 2:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false

和编辑距离有点象

dp[i][j]且示s1的前i个字符,s2的前j个字符能否构成s3的前i+j个字符

let s1 = 'aaa'
let s2 = 'abcd'
let s3 = 'aabcaa'
let m = s1.length, n = s2.length

//空字符和空字符可以组成空字符
let dp = [[true]]
//第一列表示不考虑 s2 , s1 能否构成 s3
for (let i = 1; i < m; i++) {
  dp[i] = [s1[i - 1] === s3[i - 1]]
}
//第一行表示不考虑s1,s2能否构成word3
for (let j = 1; j < n; j++) {
  dp[0][j] = s2[j - 1] === s3[j - 1]
}

for (let i = 1; i < m; i++) {
  for (let j = 1; j < n; j++) {

    //无论是 s1,s2谁出一个字符都可以,只要这个字符可以构成当前规模下的s3的最后一个字符
    dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) ||
           (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]);

  }
}

买卖股票的最佳时机 III

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,
这笔交易所能获得利润 = 3-0 = 3 。随后,在第 7 天(股票价格 = 1)的时候买入,
在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3 。

示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出,
 这笔交易所能获得利润 = 5-1 = 4 。   

 注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。   
 因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

示例 3:

输入: [7,6,4,3,1] 
输出: 0 
解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。

动态规划其实就是穷举 + 记忆。按这个思路,可以穷举所有状态

/* dp[i][k][0],第i天进行了k次交易后手上有没有股票,此时利润的最大值
共有 n 天,可以交易 p 次 */

//构建三维数组
for (let i = 0; i < n + 1; i++) {
  dp[i] = []
  for (let k = 0; i < p + 1; p++) {
    dp[i][k] = []
  }
}
//构建 dp[0][k][0] = 0

//第0天相当于交易还没开始,从第1天开始
for (let k = 0; k < p; k++) {
  //解释:因为 i 是从 1 开始的,所以 i = -1 意味着还没有开始,这时候的利润当然是 0 。
  dp[0][k][0] = 0
  //解释:还没开始的时候,是不可能持有股票的,用负无穷表示这种不可能。
  dp[0][k][1] = -infinity
}
for (let i = 0; i < n + 1; i++) {
  //用到这种状态的可能是不可能有利润的。也就排除了这种可能
  dp[i][0][0] = 0
  //解释:因为 k 是从 1 开始的,所以 k = 0 意味着根本不允许交易,这时候利润当然是 0 。
  dp[i][0][1] = -infinity
  //解释:不允许交易的情况下,是不可能持有股票的,用负无穷表示这种不可能。
}
//v[i-1]表示第i天的价格
for (let i = 1; i < n + 1; i++) {
  for (let k = 1; i < p + 1; p++) {
    dp[i][k][0] = Math.max(dp[i - 1][k][1] + v[i - 1], dp[i - 1][k][0])
    dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k][0] - v[i - 1])
  }
}

return dp[i][k][0]

停在原地的方案数

有一个长度为 arrLen 的数组,开始有一个指针在索引 0 处。

每一步操作中,你可以将指针向左或向右移动 1 步,或者停在原地(指针不能被移动到数组范围外)。

给你两个整数 steps 和 arrLen ,请你计算并返回:在恰好执行 steps 次操作以后,指针仍然指向索引 0 处的方案数。

由于答案可能会很大,请返回方案数 模 10^9 + 7 后的结果。

示例 1:

输入:steps = 3, arrLen = 2
输出:4
解释:3 步后,总共有 4 种不同的方法可以停在索引 0 处。
向右,向左,不动
不动,向右,向左
向右,不动,向左
不动,不动,不动

示例 2:

输入:steps = 2, arrLen = 4
输出:2
解释:2 步后,总共有 2 种不同的方法可以停在索引 0 处。
向右,向左
不动,不动
示例 3:

输入:steps = 4, arrLen = 2
输出:8

提示:

1 <= steps <= 500
1 <= arrLen <= 10^6

我叫杜宏伟,前端开发。

一直想写博客,在2018的年的最后几天,终于上线了。

对于前端开发,一个特点就是太零散,很容易会了后面忘了前面,所以归纳总结很重要。再有就是分享,做前端好多年,以前都是看你们写的文章, 现在我也开始写一些,希望可以帮到入行的小伙伴。微信号 duhongwei5775

欢迎转载,只需注明作者,出处即可

版权说明:署名 4.0 国际(CC BY 4.0)