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

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

Richard 👍（2） 💬（1）
老师留的题都很不错，正在刷之前没做过的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
2019-02-11

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

好运连连 👍（0） 💬（1）
老师，请教下。关于物流中转路线，应该采用哪种算法合适？
2019-07-10

黄丹 👍（4） 💬（0）
课程的最后一天，也是新年上班的第一天，感谢王老师的教育和陪伴，祝您生活开心，工作顺利。今天的题目比前几天的都难一点，只做了三题，太累了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

李皮皮皮皮皮 👍（3） 💬（0）
每天一道算法题，风雨无阻（过年偷懒不算😛）
2019-02-11

kai 👍（3） 💬（0）
动态规划，感觉是面试必考内容，今天跟着这些题目再来复习一遍~
2019-02-11

纯洁的憎恶 👍（3） 💬（0）
这冲刺压力有点大了😓
2019-02-10

kai 👍（2） 💬（0）
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; } }
2019-02-11

mgxian 👍（1） 💬（0）
买卖股票的最佳时机 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-11

虎虎❤️ 👍（1） 💬（0）
正则表达式 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的排名第一的答案，搬过来了
2019-02-10

云之崖 👍（0） 💬（0）
1年左右断断续续，终于学完了所有章节，这些练习题大部分不看提示都能搞得定了。
2021-01-22

xxxxL 👍（0） 💬（0）
请问这个在哪里呢（详细可看 @Smallfly 整理的 Minimum Path Sum）
2020-01-18

大风歌 👍（0） 💬（0）
第一遍
2020-01-09

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