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

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

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

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

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

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

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

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

这冲刺压力有点大了😓

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

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