数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

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

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

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

回溯

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

分治

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

动态规划

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

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

Regular Expression Matching(正则表达式匹配)
Minimum Path Sum(最小路径和)
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(28)

  • 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
    6
  • 黄丹
    课程的最后一天,也是新年上班的第一天,感谢王老师的教育和陪伴,祝您生活开心,工作顺利。
    今天的题目比前几天的都难一点,只做了三题,太累了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
  • kai
    动态规划,感觉是面试必考内容,今天跟着这些题目再来复习一遍~
    2019-02-11
    3
  • 李皮皮皮皮皮
    每天一道算法题,风雨无阻(过年偷懒不算😛)
    2019-02-11
    2
  • 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
  • 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-02-10
    2
  • _CountingStars
    买卖股票的最佳时机 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
  • 明翼
    请教下老师,遇到一个问题,给多个银行账号,假如每个账号每天都有交易,这样在坐标中可以画出时间和交易金额的曲线,求哪个曲线的更平滑或波动更大,银行账号的交易额度可能相差很大,银行账号交易梳理可能多个。

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

    2019-09-03
  • go
    老师,具体的是这样,比如物流公司,用户下单,需要根据最短路线或者最少花费来找出合适的中转路线。 比如需要送货到B城市,A城市发货,但是,很多路线,需要选最合适的路线,比如A到D中转再到E中转最后送货到B。
    2019-07-10
  • go
    老师,请教下。关于物流中转路线,应该采用哪种算法合适?

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

    2019-07-10
  • Nereus
    零钱兑换 - 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-19
  • 拉欧
    买卖股票的最佳时机 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
    }
    2019-02-15
  • TryTs
    //零钱兑换
    #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;
    }
    }
    2019-02-14
  • TryTs
    回溯0-1背包问题
    #include<iostream>
    using namespace std;
    int v[10] = {2,2,4,6,3};
    int M;//代表背包的容积
    int n;
    int cmax = 0;

    void f(int w,int k){
    // if(w == 0){
    // if(w > max) max = w;
    // }
    if(w == M || k == n){
    if(w > cmax) cmax = w;
    return ;
    }
    f(w,k + 1);
    if(w + v[k] <= M){
    f(w + v[k],k + 1);
    }
    }
    int main(){
    //v[] = {2,2,4,6,3};
    M = 9;
    n = 5;
    f(0,0);
    cout<<cmax<<endl;
    }
    2019-02-14
  • TryTs
    #include<iostream>
    #include<cmath>
    using namespace std;

    int queen[100];
    int sum = 0;
    int n;
    void Print(){
    //cout<<"ss"<<endl;
    for(int i = 0;i < n;i++){
    cout<<"("<<i+1<<","<<queen[i] + 1<<")";
    }
    sum++;
    cout<<endl;
    }

    void Queen(int queen[],int k){
    if(k == n) {
    Print();
    //return ;
    }
        int j = 0;
        for(int i = 0;i < n;i++){
         //j = i;
         for( j = 0;j < k;j++){
         if((queen[j] == i)||(abs(queen[j] - i) == abs(k - j)))
    break;
    }
    if(j == k){
    queen[k] = i;
    Queen(queen,k+1);
    }
    }
    }
    int main(){
    cin>>n;
    Queen(queen,0);
    cout<<sum<<endl;
    }
    2019-02-14
  • 纯洁的憎恶
    第一题,把39讲的代码改了一下。。。

    public class Pattern {
      private boolean matched = false;
      private char[] pattern; // 正则表达式
      private int plen; // 正则表达式长度

      public Pattern(char[] pattern, int plen) {
        this.pattern = pattern;
        this.plen = plen;
      }

      public boolean match(char[] text, int tlen) { // 文本串及长度
        matched = false;
        if (pattern[0]='*')
               return matched;
       int i = 0;
       int j = 0;
       while (i<=plen&&j<=tlen&&pattern[i]!=text[j]&&pattern[i]!='.')
             i++;
        rmatch(0, 0, text, tlen);
        return matched;
      }

      private void rmatch(int ti, int pj, char[] text, int tlen) {
        if (matched) return; // 如果已经匹配了,就不要继续递归了
        if (ti == tlen){ //文本串到结尾了
          matched = true;
          return;
        }
        if (pattern[pj] == '*') { // * 匹配任意个字符
          for (int k = 0; k <= tlen-ti&&tex[ti+k]==text[ti]; ++k) {
            rmatch(ti+k, pj+1, text, tlen);
          }
        } else if (pattern[pj] == '.') { // . 匹配 0 个或者 1 个字符
          rmatch(ti, pj+1, text, tlen);
          rmatch(ti+1, pj+1, text, tlen);
        } else if (ti < tlen && pattern[pj] == text[ti]) { // 纯字符匹配才行
          rmatch(ti+1, pj+1, text, tlen);
        }
      }
    }
    2019-02-12
收起评论
28
返回
顶部