数据结构与算法之美
王争
前 Google 工程师
283752 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 81 讲
基础篇 (38讲)
数据结构与算法之美
15
15
1.0x
00:00/00:00
登录|注册

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

最长递增子序列
最长公共子序列
莱文斯坦最短编辑距离
最小路径和
0-1背包问题
逆序对个数
0-1背包问题
八皇后问题
Triangle
Maximum Product Subarray
Best Time to Buy and Sell Stock
Coin Change
Minimum Path Sum
Regular Expression Matching
动态规划
分治
回溯
LeetCode练习题
算法思想

该思维导图由 AI 生成,仅供参考

你好,我是王争。今天是节后的第一个工作日,也是我们“春节七天练”的最后一篇。

几种算法思想必知必会的代码实现

回溯

利用回溯算法求解八皇后问题
利用回溯算法求解 0-1 背包问题

分治

利用分治算法求一组数据的逆序对个数

动态规划

0-1 背包问题
最小路径和(详细可看 @Smallfly 整理的 Minimum Path Sum)
编程实现莱文斯坦最短编辑距离
编程实现查找两个字符串的最长公共子序列
编程实现一个数据序列的最长递增子序列

对应的 LeetCode 练习题(@Smallfly 整理)

Regular Expression Matching(正则表达式匹配)
Minimum Path Sum(最小路径和)
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

本文介绍了四种算法思想中必知必会的代码实现。作者首先介绍了回溯算法,包括八皇后问题和0-1背包问题的求解。接着讲解了分治算法,以及如何利用分治算法求一组数据的逆序对个数。动态规划也是本文重点讨论的内容,包括0-1背包问题、最小路径和、莱文斯坦最短编辑距离、查找两个字符串的最长公共子序列以及一个数据序列的最长递增子序列的编程实现。此外,作者还列举了对应的LeetCode练习题,供读者练习。整篇文章内容丰富,涵盖了算法思想和实际代码实现,对于想要系统学习算法的读者来说是一份很好的参考资料。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《数据结构与算法之美》
新⼈⾸单¥68
立即购买
登录 后留言

全部留言(31)

  • 最新
  • 精选
  • kai
    听了老师的课程,第一遍的时候,只是在读,现在开始回顾: 课程相关的知识点,做了笔记: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-11
    2
    13
  • Richard
    老师留的题都很不错,正在刷之前没做过的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-11
    2
  • 明翼
    请教下老师,遇到一个问题,给多个银行账号,假如每个账号每天都有交易,这样在坐标中可以画出时间和交易金额的曲线,求哪个曲线的更平滑或波动更大,银行账号的交易额度可能相差很大,银行账号交易梳理可能多个。

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

    2019-09-03
  • 好运连连
    老师,请教下。关于物流中转路线,应该采用哪种算法合适?

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

    2019-07-10
  • 黄丹
    课程的最后一天,也是新年上班的第一天,感谢王老师的教育和陪伴,祝您生活开心,工作顺利。 今天的题目比前几天的都难一点,只做了三题,太累了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
    4
  • 李皮皮皮皮皮
    每天一道算法题,风雨无阻(过年偷懒不算😛)
    2019-02-11
    3
  • kai
    动态规划,感觉是面试必考内容,今天跟着这些题目再来复习一遍~
    2019-02-11
    3
  • 纯洁的憎恶
    这冲刺压力有点大了😓
    2019-02-10
    3
  • kai
    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
    2
  • mgxian
    买卖股票的最佳时机 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
收起评论
大纲
固定大纲
几种算法思想必知必会的代码实现
回溯
分治
动态规划
对应的 LeetCode 练习题(@Smallfly 整理)
显示
设置
留言
31
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部