春节7天练 | Day 7：贪心、分治、回溯和动态规划

精选留言

• kai

  2019-02-11 11:15:42

  听了老师的课程，第一遍的时候，只是在读，现在开始回顾：
  课程相关的知识点，做了笔记：https://github.com/guokaide/algorithm/blob/master/summary/algorithm.md
  课程涉及的题目，也在逐步总结当中：
  https://github.com/guokaide/algorithm/blob/master/questions/questions.md
  
  希望和大家一起进步，欢迎小伙伴们一起来讨论~
  

  作者回复

  感谢您参与春节七天练的活动，为了表彰你在活动中的优秀表现，赠送您99元专栏通用阅码，我们会在3个工作日之内完成礼品发放，如有问题请咨询小明同学，微信geektime002。

  2019-02-22 11:03:59

• 
  黄丹

  2019-02-11 21:39:33

  课程的最后一天，也是新年上班的第一天，感谢王老师的教育和陪伴，祝您生活开心，工作顺利。
  今天的题目比前几天的都难一点，只做了三题，太累了TaT。对于动态规划和贪心总觉得很巧妙，如果想不到动态转移方程式，就很难做，但要是想到了，真的是豁然开朗。对于这一类题，还是要多锻炼，找动态转移方程式要从最后一个结果出发，去想这个结果可以由什么得到，知道之前所有结点的信息，如何推导出当前结点的信息，其实和高中学的归纳法有一点点像。
  下面给出我今天做的三题的解题思路和代码
  1. Problem 121. Best Time to Buy and Sell Stock
  解题思路：这道题很久以前做的，我们可以维持两个变量 - 分别对应于最小谷值和最大利润（销售价格和最低价格之间的最大差异）的minprice 和maxprofit。
  代码：https://github.com/yyxd/leetcode/blob/master/src/leetcode/array/easy/Problem121.java
  2. Problem 120. Triangle
  解题思路：这道题给一个由整数组成的三角形，自上而下寻找顶点到三角形边的最短的一条路径，设置一个数组A[0...n-1][0...n-1]，A[i][j]代表到达第i行第j列结点的最短路径
* DP转移方程式为：A[i][j]=min(A[i-1][j-1],A[i-1][j])+triangle[i][j]
* 其中二维数组可以简化为一维数组，因为我们只需要上一行结点的信息
* 然后遍历到达最后一行的节点的路径，找到最短路径的值
  代码：https://github.com/yyxd/leetcode/blob/master/src/leetcode/dp/Problem120_Triangle.java
  3. Problem 322. Coin Change
  解题思路：这道题是给定具有n个不同金额的硬币（硬币个数无限）coins[0...n-1]，给一个整数amount，是否给的硬币能正好达到整数，给出能组成整数最少需要的硬币个数.
解法是设置一个数组A[0...amount],进行初始化A[0]=0;A[1...amount] = -1;保存的是当给定金额为i时，所需要的最少的硬币。
* dp转移方程式为 A[k] = 1+min(A[k-coins[0]],A[k-coins[1]],....A[k-coins[n-1]]).
* 这里要注意的是判断A[k]是否有解
  代码：https://github.com/yyxd/leetcode/blob/master/src/leetcode/dp/Problem322_CoinChange.java
  课程完结撒花，真的学到好多，自己以后还会反复回顾的，再次感谢王争老师，还有每天负责朗读的声音好好听的修阳小哥哥。
  
• 
  李皮皮皮皮皮

  2019-02-11 11:15:56

  每天一道算法题，风雨无阻（过年偷懒不算😛）
• kai

  2019-02-11 00:38:45

  动态规划，感觉是面试必考内容，今天跟着这些题目再来复习一遍~
• 
  纯洁的憎恶

  2019-02-10 21:38:32

  这冲刺压力有点大了😓
• kai

  2019-02-11 10:55:42

  8皇后问题
  
  public class EightQueen {
  
  private static final int QUEEN_NUMBER = 8; // 皇后个数
  private int[] columns = new int[QUEEN_NUMBER]; // 每个皇后存储的列 (row, col), row天然不相等
  private int total = 0;
  
  public int solution() {
  queen(0);
  return total;
  }
  
  private void queen(int row) {
  if (row == QUEEN_NUMBER) {
  total++;
  } else {
  for (int col = 0; col != QUEEN_NUMBER; col++) {
  columns[row] = col;
  if (isPut(row)) {
  queen(row+1);
  }
  }
  }
  }
  
  private boolean isPut(int row) {
  for (int i = 0; i != row; i++) {
  if (columns[row] == columns[i] || row - i == Math.abs(columns[row]-columns[i])) {
  return false;
  }
  }
  return true;
  }
  
  }
• 
  Richard

  2019-02-11 10:21:44

  老师留的题都很不错，正在刷之前没做过的LeetCode题。
  参与下答对三题送课程的活动:
  Day 1：
  1.求众数(Python)
  class Solution:
  def majorityElement(self, nums):
  return sorted(nums)[len(nums) // 2]
  2.缺失的第一个正数(Golang)
  func firstMissingPositive(nums []int) int {
  if len(nums) == 0 {
  return 1
  }
  
  var arr = make([]bool, len(nums)+1)
  var idx = 1
  for i := 0; i < len(nums); i++ {
  if nums[i] >= 0 && nums[i] < len(arr) {
  arr[nums[i]] = true
  }
  }
  
  for i := 1; i < len(arr); i++ {
  if arr[i] == false {
  idx = i
  break
  } else {
  idx = i + 1
  }
  }
  
  return idx
  }
  Day 7:
  3. 买卖股票的最佳时机(Python)
  class Solution:
  def maxProfit(self, prices):
  if not prices:
  return 0
  min_price = prices[0]
  res = 0
  for i in prices[1:]:
  min_price = min(min_price, i)
  if res < i - min_price:
  res = i - min_price
  return res
  

  作者回复

  感谢您参与春节七天练的活动，为了表彰你在活动中的优秀表现，赠送您99元专栏通用阅码，我们会在3个工作日之内完成礼品发放，如有问题请咨询小明同学，微信geektime002。

  2019-02-22 11:04:26

• 
  mgxian

  2019-02-11 08:30:29

  买卖股票的最佳时机 go 语言实现
  package main
  
  import "fmt"
  
  func maxProfit(prices []int) int {
  max := -1
  for i := 0; i < len(prices); i++ {
  for j := i + 1; j < len(prices); j++ {
  profit := prices[j] - prices[i]
  if profit > 0 && profit > max {
  max = profit
  }
  }
  }
  
  if max == -1 {
  return 0
  }
  
  return max
  }
  
  func main() {
  testData1 := []int{7, 1, 5, 3, 6, 4}
  testData2 := []int{7, 6, 4, 3, 1}
  
  fmt.Println(maxProfit(testData1))
  fmt.Println(maxProfit(testData2))
  }
  
• 
  虎虎❤️

  2019-02-10 21:35:35

  正则表达式
  public boolean isMatch(String s, String p) {
  
  if (s == null || p == null) {
  return false;
  }
  boolean[][] dp = new boolean[s.length()+1][p.length()+1];
  dp[0][0] = true;
  for (int i = 0; i < p.length(); i++) {
  if (p.charAt(i) == '*' && dp[0][i-1]) {
  dp[0][i+1] = true;
  }
  }
  for (int i = 0 ; i < s.length(); i++) {
  for (int j = 0; j < p.length(); j++) {
  if (p.charAt(j) == '.') {
  dp[i+1][j+1] = dp[i][j];
  }
  if (p.charAt(j) == s.charAt(i)) {
  dp[i+1][j+1] = dp[i][j];
  }
  if (p.charAt(j) == '*') {
  if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') {
  dp[i+1][j+1] = dp[i+1][j-1];
  } else {
  dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
  }
  }
  }
  }
  return dp[s.length()][p.length()];
  }
  
  leetcode的排名第一的答案，搬过来了
• 
  云之崖

  2021-01-22 18:06:29

  1年左右断断续续，终于学完了所有章节，这些练习题大部分不看提示都能搞得定了。
• 
  xxxxL

  2020-01-18 22:49:07

  请问这个在哪里呢（详细可看 @Smallfly 整理的 Minimum Path Sum）
• 
  大风歌

  2020-01-09 19:20:04

  第一遍
• 
  明翼

  2019-09-03 22:06:27

  请教下老师，遇到一个问题，给多个银行账号，假如每个账号每天都有交易，这样在坐标中可以画出时间和交易金额的曲线，求哪个曲线的更平滑或波动更大，银行账号的交易额度可能相差很大，银行账号交易梳理可能多个。

  作者回复

  抱歉，这个我也不懂啊

  2019-09-06 07:00:25

• 
  好运连连

  2019-07-10 14:20:18

  老师，具体的是这样，比如物流公司，用户下单，需要根据最短路线或者最少花费来找出合适的中转路线。 比如需要送货到B城市，A城市发货，但是，很多路线，需要选最合适的路线，比如A到D中转再到E中转最后送货到B。
• 
  好运连连

  2019-07-10 06:45:26

  老师，请教下。关于物流中转路线，应该采用哪种算法合适？

  作者回复

  麻烦说具体点吧 太笼统了

  2019-07-10 14:15:45

• Nereus

  2019-02-19 10:45:56

  零钱兑换 - GO
  
  func coinChange(coins []int, amount int) int {
  var dp []int = make([]int, amount+1)
  for _, record := range coins {
  if amount >= record {
  dp[record] = 1
  }
  }
  
  for i := 1; i <= amount; i++ {
  dp[i] = amount + 1
  for _, record := range coins {
  if i-record >= 0 {
  dp[i] = min(dp[i-record]+1, dp[i])
  }
  }
  }
  
  if dp[amount] > amount {
  return -1
  }
  
  return dp[amount]
  }
  
  func min(a, b int) int {
  if a < b {
  return a
  }
  return b
  }
  
  
• 
  拉欧

  2019-02-15 18:23:48

  买卖股票的最佳时机 go 语言实现
  
  func maxProfit(prices []int) int {
  
  max:=0
  for i:=0;i<len(prices);i++{
  for j:=0;j<i;j++{
  num:=prices[i]-prices[j]
  if num>max{
  max=num
  }
  }
  }
  return max
  }
• 
  拉欧

  2019-02-15 15:05:45

  零钱兑换 go语言实现
  func coinChange(coins []int, amount int) int {
  if amount==0{
  return 0
  }
  if len(coins)==0 && amount!=0{
  return -1
  }
  
  isSmall:=true
  for _,coin:=range coins{
  if coin<=amount{
  isSmall=false
  }
  }
  if isSmall{
  return -1
  }
  grid:=make([]int,amount+1)
  
  
  for _,coin:=range coins{
  if coin<=amount{
  grid[coin]=1
  }
  if coin==amount{
  return 1
  }
  }
  for i:=2;i<amount+1;i++{
  newGrid:=make([]int,amount+1)
  for j:=1;j<amount+1;j++{
  for _,coin:=range coins{
  if grid[j]==1 && j+coin<=amount{
  newGrid[j]=1
  newGrid[j+coin]=1
  }
  }
  }
  grid=newGrid
  if grid[amount]==1{
  return i
  }
  }
  return -1
  }
• 
  拉欧

  2019-02-15 12:02:46

  最小路径和 go实现
  
  func minPathSum(grid [][]int) int {
  l:=len(grid)
  w:=len(grid[0])
  sum:=make([][]int,l)
  for i:=0;i<l;i++{
  sum[i]=make([]int,w)
  }
  sum[0][0]=grid[0][0]
  for i:=1;i<w;i++{
  sum[0][i]=grid[0][i]+sum[0][i-1]
  }
  for j:=1;j<l;j++{
  sum[j][0]=grid[j][0]+sum[j-1][0]
  }
  for i:=1;i<l;i++{
  for j:=1;j<w;j++{
  sum[i][j]=less(sum[i-1][j],sum[i][j-1])+grid[i][j]
  }
  }
  
  return sum[l-1][w-1]
  }
  
  func less(i,j int) int{
  if i>j{
  return j
  }else{
  return i
  }
  }
• 
  拉欧

  2019-02-15 11:36:04

  正则表达式匹配 go语言实现，还是看别人的提示搞出来的
  func isMatch(s string, p string) bool {
  if len(p)==0{
  if len(s)==0{
  return true
  }else{
  return false
  }
  }
  if len(p)==1{
  if len(s)==1 && (s[0]==p[0] || p[0]=='.'){
  return true
  } else {
  return false
  }
  }
  if p[1]!='*'{
  if len(s)==0{
  return false
  }
  return (s[0]==p[0]||p[0]=='.') && isMatch(s[1:],p[1:])
  }else{
  for ;len(s)!=0 && (s[0]==p[0]||p[0]=='.');{
  if isMatch(s,p[2:]){
  return true
  }
  s=s[1:]
  }
  return isMatch(s,p[2:])
  }
  
  
  
  return true
  }