精选留言(31)

• 
  kai

  2019-02-11

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

  展开

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

  共 2 条评论

  13
• 
  黄丹

  2019-02-11

  课程的最后一天，也是新年上班的第一天，感谢王老师的教育和陪伴，祝您生活开心，工作顺利。 今天的题目比前几天的都难一点，只做了三题，太累了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 课程完结撒花，真的学到好多，自己以后还会反复回顾的，再次感谢王争老师，还有每天负责朗读的声音好好听的修阳小哥哥。

  展开

  

  4
• 
  kai

  2019-02-11

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

  

  3
• 
  李皮皮皮皮皮

  2019-02-11

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

  

  3
• 
  kai

  2019-02-11

  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; } }

  展开

  

  2
• 
  Richard

  2019-02-11

  老师留的题都很不错，正在刷之前没做过的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。

  

  2
• 
  纯洁的憎恶

  2019-02-10

  这冲刺压力有点大了😓

  

  3
• 
  mgxian

  2019-02-11

  买卖股票的最佳时机 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)) }

  展开

  

  1
• 
  云之崖

  2021-01-22

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

  

  
• 
  xxxxL

  2020-01-18

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

  

  
• 
  马志远

  2020-01-09

  第一遍

  

  
• 
  明翼

  2019-09-03

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

  作者回复: 抱歉，这个我也不懂啊

  

  
• 
  好运连连

  2019-07-10

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

  

  
• 
  好运连连

  2019-07-10

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

  作者回复: 麻烦说具体点吧 太笼统了

  

  
• 
  Nereus

  2019-02-19

  零钱兑换 - 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

  买卖股票的最佳时机 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

  零钱兑换 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

  最小路径和 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

  正则表达式匹配 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 }

  展开

  

  
• 
  TryTs

  2019-02-14

  //零钱兑换 #include<iostream> #include<algorithm> using namespace std; int coins[10]; int amount; int k;//k代表纸币的数目 int dp[20];//代表面值最大，也可以采用动态扩容的方式 int cmax = 32767; int coinChange(int coins[],int amount){ for(int i = 1;i <= amount;i++){ dp[i] = cmax; for(int j = 0;j < k;j++){ int t = coins[j]; if(i >= t && coins[i - t] != cmax){ dp[i] = min(dp[i - t] + 1,dp[i]); } } } if(dp[amount] < cmax && dp[amount] > 0){ return dp[amount]; } else return -1; } int main(){ k = 0; while(true){ cin>>k; for(int i = 0;i < k;i++){ cin>>coins[i]; } cin>>amount; cout<<coinChange(coins,amount)<<endl; } }

  展开

  

  