最近在MOOC上报名了北大郭炜老师的算法课程，感觉收获还是蛮大的，因此整理一下自己的学习心得，方便以后复习查阅。

第一章_枚举

  • 逐个尝试答案的一种求解策略
  • 遇到题，首先考虑枚举法，看数据量是否允许，是否有“剪枝”策略。
  • 但枚举时也要考虑“减枝”：如何去掉明显不满足的解，加快枚举速度
  • 转变枚举思路：从条件出发找解 -> 从解出发去试是否满足条件，解比条件组合更容易遍历所有情况。
    自问：题目什么是结果，什么是条件。
  • 局部枚举：
    可由局部来确定剩余部分的状态，这样只需枚举局部即可实现对全体的枚举。
    关键是找出局部->全体的推导关系。

第二章_递归

  • 常用递归情况：
    1.解决用递归定义的问题(求解表达式问题)
    2.将问题分解为规模更小的子问题来求解(汉诺塔问题)

  • 想明白递推关系(递推函数是干什么的、返回值是什么)、终止条件。

  • 递归用于数据量较小的情况，数据量大用动态规划。

  • 递归的本质也是分解子问题，思考怎样把问题缩小。

第三章_动态规划

  • 解题思路

    1. 设计子问题，将原问题分解为子问题(满足最优子结构和无后效性两条件)
    2. 存放子问题解：一个解若由K个变量决定，就申请一个K维数组来保存。
    3. 确定初始子问题：问题的边界值(最小的子问题)。
    4. 确定递推函数：如何从子问题->父问题。多为一个单位一个单位使问题规模递增。可以先做一步，再看能不能划分为形式相同子问题。

  • 可用动规解决的问题的特点

    • 最优子结构：若父问题解是最优的，则子问题解也肯定是最优的。

    • 无后效性：父问题的解只和子问题解的值有关，和子问题的解是如何求得的无关。

    • 与递归的相同处：思路都是大问题分成相同形式子问题(递推函数)，小问题的解再组合为大问题解。

    • 与递归的不同处：动归要保存中间结果(多用全局数组保存)，避免重复计算。

  • 递归函数与递推函数：递推函数是用循环实现的：找好结束条件，确定从哪开始循环，在循环体里写递推函数就可以了。

  • 递推函数开数组：数组若特别大，考虑用滚动数组，后项不断覆盖前项，可实现二维数组->一维数组的降维。

第四章_深度优先搜索

  • 多为递归+剪枝来实现。剪枝分为可行性剪枝(能否求得解)和最优性剪枝(是否是最优解)，从这两个思路来想。

  • 深搜的本质还是递归分解子问题，一层层地分解，用栈解决的问题用递归都都可以解决。

  • 搜索问题其实就是遍历所有解找最优解的过程，枚举也是搜索的一种，深度/广度搜索只是枚举的策略不同而已。搜索和一般的枚举区别在于，搜索问题的点与点之间是有关系的(边表示这种关系)，因此从一个点可以按规则进入下一个点，而不是盲目的枚举。(如正则表达式问题，出现了’(‘即表示要递归进入新的节点，出现’)’即表示要结束当前问题，出现’|’即需要求左右两边最大值)

  • 遍历图的伪代码流程

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    int main(){
        将所有点标记为新点
        起点=xx;
        重点=xx;
        cout<<Dfs(起点);
    }

    //判断从V出发是否能走到终点
    bool Dfs(V){
        if(V是终点)
            return true;
        if(V是旧点)
            return false;
        将V标记为旧点;
        遍历V相邻的每个结点U{
            if(Dfs(U)==true)
                return true;
        }
        return false;
    }

    //判断从V出发是否能走到终点，并记录路径
    Node path[MAX_LEN]; //全局数组，记录路径
    int depth=0; //记录深度
    bool Dfs(V){
        if(V是终点){
            path[depth]=V;
            return true;
        }
        if(V是旧点){
            return false
        }
        将V标记为旧点;
        path[depth]=V;
        depth++;
        遍历V相邻的每个结点U{
            if(Dfs(U)==true)
                return true;
        }
        depth--; //从V走不到终点，回退
        return false;
    }

    //遍历图中所有点
    int main(){
        将所有点标记为新点;
        while(在图中能找到能找到新点K) 
            Dfs(K);
    }
    Dfs(V){
        if(V是旧点) return;
        将V标记为旧点;
        对和V相邻的每个点U{
            Dfs(U);
        }
    }

  • 图的数据结构

    • 邻接矩阵：二维数组，G[i][j]表示节点i和节点j之间边的情况。遍历复杂度O(n2)

    • 邻接表：每个节点V设置一个一维数组，存放从V连出去的边。边稀疏时效率高，遍历复杂度O(n+e)。

      1
      2
      3
      4
      //邻接表实现
      Vector<Vector<T>> v   //变长二维数组，用法和数组一样
      v.push_back()   //添加元素
      v[0].size()    //vector长度

第五章_广度优先搜索

  • 依层次顺序，从小到大扩展节点。把层次低的点全部扩展出来后，才会扩展层次高的点。

  • 可确保找出最短路径解，因为是一层一层找的

  • 深搜用栈(递归)存节点，广搜用队列存节点。

    1
    2
    3
    4
    5
    6
    //队列操作
    queue<T> q
    q.empty()  //是否为空
    q.front()  //取队首元素  
    q.push(xx)   //加入元素
    q.pop()  //抛弃元素

广搜中若要输出路径，则就要自己实现队列，数组 + aad、tail指针，队头取数，队尾加数。

  • 优先队列：priority_queue

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    //与multiset区别，pr_queue默认从大到小，multiset默认从小到大。
    //pr_queue重载'<'运算符(直接写重载函数即可)，multiset重载'()'运算符(写在结构体中)。
    //重写operator<比较符
    bool operator<(const T & t1,const T & t2){
        return t1<t2;  //t1的优先级小于t2，则t2排在队首(优先级高的排队首)
    }
    priority_queue<T> q;  //自动按重写的<对T排序
    q.top()   //取队首
    q.push()  //入队尾
    q.pop()   //扔队首

  • 深搜/广搜区别，深搜用递归，广搜用队列(空间需求会大一些)。广搜最先找到的一定是最优解，深搜则要全部搜完才能找到最优解。因此需要遍历所有节点的情况用深搜，要递归的情况用深搜。

第六章_贪心算法

  • 每一步行动总是选取当前下一步的最优操作，并不考虑之后的影响。
    (要考虑当前的最优操作也是整体的最优操作)

  • 大部分贪心都和排序相关，直接从排序结果中从高到低选择即可。

  • 三类常见的区间贪心问题

    • 线段覆盖
      n个开区间(ai,bi)，选择尽量多个区间，使得这些区间两两不相交
      右端点排序（<）兼顾左端点（>），再从左到右遇到不相交的就选

      1
      2
      3
      4
      5
      6
      7
      //a[i].l、a[i].r为左、右端点
      sort(a,a+n,cmp);
      int num=1,now=a[0].r;  
      for(int i=1; i<n; i++) {
          if(a[i].l>=now) now=a[i].r,num++;
      }
      printf("%d", num);

    • 区间选点
      n个闭区间[ai,bi]，选择尽量少的点，使得每个区间至少有一个点
      右端点排序（<）兼顾左端点（>），每次选择可选区间的最后一个点

      1
      2
      3
      4
      5
      6
      sort(a,a+n,cmp);
      int num=1,now=a[0].r;
      for(int i=1; i<n; i++) {
          if(a[i].l>now) now=a[i].r,num++;   
      }
      printf("%d", num);

    • 区间覆盖
      数轴上有n个闭区间[ai,bi]，选择尽量少的区间覆盖一条指定的线段[s,t]
      左端点排序（<）兼顾右端点（<），每次选择从当前起点能覆盖到的最长的区间

      1
      2
      3
      4
      5
      6
      7
      sort(a,a+n,cmp);
      int num=0,now=s,to=-1;
      for(int i=1; i<=n && to<=t; i++) {
          if(a[i].l<=now)    to=max(to,a[i].r);
          else    now=to,to=a[i].r,num++;
      }
      printf("%d", num);

一些基础知识

  • 有关复杂度的估算：
    十亿级肯定超时，亿级较危险，最好千万以下

  • 算法中的证明，很难从正面直接证明，多为反证法，要多考虑反面的不可能性。eg,证明两数不可能相等，就想两数什么时候会相等、若相等会有什么条件不满足等等…

  • 算法三大能力：
    1.按步骤思考，大问题分为小问题，一步步解决问题的能力
    2.实际问题抽象为计算机表示的能力(列出问题涉及的元素，再依次表示为计算机的数据结构)
    3.编程实现的能力(按1.的步骤，对数据结构进行操作，即编写算法)

解题思路：数据量不大，先想枚举，再想递归。大数据量考虑动规。其次深搜、广搜。然后贪心。

C/C++不能动态申请数组，就一次申请最大量，空间->时间。

for循环中：++i比i++效率高(无需保存原先的变量)，尽量使用++i。

  • vector<pair<string, int>> word; gcc会报错”>>”，理解为输入符号。此时应加上空格：
    vector<pair<string, int> >

  • 对于涉及到“选前n个数”的问题，下标统一从1开始，这样下标使用的时候可以统一，只用把存储信息的数组从1开始存就可以了。

好题记录：

  • POJ 1222(灯泡、开关问题)，第一周4题
  • 放苹果，第三周3题(递归、动态规划对比)
  • 找n元素数组前m大的数，第五周3题(n+mlogm算法)
  • 最佳加法表达式，第六周4题(怎样自底向上推导)
  • 分蛋糕，第七周5题(怎样自底向上推导，循环的嵌套)
  • 城市通路，第九周1题(深搜，怎样剪枝)
  • 生日蛋糕，第九周3题(深搜，剪枝)
  • 带限制的广搜：增加搜索状态的维度，判重时要考虑增加的维度。

Post Date： 2018-04-13

版权声明： 本文为原创文章，转载请注明出处