算法知识点

kyoma comment: 难度不分先后, 求补充对应英文

1 数据结构 Data Structure

1.1 Stack

洛谷P1449
3*(5–2)+7对应的后缀表达式为：3 5 2 - * 7 +. 输入后缀表达式求式子的结果. 经典利用栈来解的题.
leetcode-Valid Parentheses
给出混合括号字符串诸如”([)–>false”, “()[]{}–>true”来判断是否为合法串. 对每一个右括号，找到在它左边最靠近它的左括号匹配, 经典利用栈来解. 遍历,前括号进栈遇到后括号时出栈检查合法性

1.2 Queue

1.3 Linked List

参考题单Leetcode链表专题

Leetcode-Add Two Numbers
两个链表,每个节点上有一个10以内的数字, 一个链表代表一个数, 求两数加合结果, 结果同样以链表形式返回.

code

  
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
  ListNode *p1=l1, *p2=l2, *res = new(ListNode);
  ListNode *p = res, *pre = NULL;
  int add = 0;
  while(p1!=NULL || p2!=NULL) {
      int now = 0;
      if(p1==NULL) {
          now = p2->val + add;
          p2 = p2->next;
      } else if (p2==NULL) {
          now = p1->val + add;
          p1 = p1->next;
      } else {
          now = p1->val + p2->val + add;
          p1 = p1->next;
          p2 = p2->next;
      }
      if(now >= 10){
          add = 1;
          now -= 10;
      } else add = 0;
      p->val = now;
      p->next = new(ListNode);
      pre = p;
      p = p->next;
  };
  if(add){
      p->val = 1;
      p->next = NULL;
  } else pre->next = NULL;
  return res;
}

leecode-reverse linked list
链表翻转, 不要慌分分钟写出来.

code

 
ListNode* reverseList(ListNode* head) {
  ListNode *pre=NULL, *p=head, *tmp;
  while(p!=NULL){
      tmp = p->next;
      p->next = pre;
      pre = p;
      p = tmp;
  }
  return pre;
}

leetcode-Remove Nth Node From End of List
删除链表倒数第n个node, 要在一遍内执行完的问题就是指针不能知道当前节点是倒数第几个，所以考虑用快慢指针。快指针比慢指针快n个节点，当快指针的下一个元素为空就说明慢指针的下一个节点应该删除。

code

 
  ListNode* removeNthFromEnd(ListNode* head, int n) {
      ListNode *fast=head, *slow=head, *pre = NULL;
      for(int i=0; inext;
      while(fast != NULL){
          fast = fast->next;
          pre = slow;
          slow = slow->next;
      }
      if(pre==NULL) return slow->next;
      else pre->next = slow->next;
      return head;
  }

链表排序
使用快慢指针来找到链表的中点, 利用归并排序来做会很好写.

归并版code


ListNode* merge(ListNode *left, ListNode *right){
      ListNode *res = new ListNode;
      ListNode *p = res;
      while(left!=NULL && right!=NULL){
          if(left->val < right->val) {
              p->next = left;
              p = p->next;
              left = left->next;
          } else {
              p->next = right;
              p = p->next;
              right = right->next;
          }
      }
      while(left!=NULL){
          p->next = left;
          p = p->next;
          left = left->next;
      }
      while(right!=NULL){
          p->next = right;
          p = p->next;
          right = right->next;
      }
      return res->next;
  }    
  ListNode* mergeSort(ListNode *head) {
      if(head == NULL || head->next == NULL) return head;
      ListNode *p1 = head, *p2 = head, *pre;
      while(p1 != NULL && p2 != NULL && p2->next != NULL){
          pre = p1;
          p1 = p1->next;
          p2 = p2->next->next;
      }
      pre->next = NULL;
      ListNode *left = mergeSort(head);
      ListNode *right = mergeSort(p1);
      return merge(left, right);
  }

1.4 树 Tree

二叉搜索树 Binary serch Tree

作用：插入删除、查询是否包含某个数
所有节点满足左子树上的所有节点都比自己小，右子树上的所有节点都比自己大。
插入直接按照树的大小关系插，删除分以下情况：
(1) 需要删除的节点没有左儿子，那么把右儿子提上来
(2) 需要删除的节点的左儿子没有右儿子，把左儿子提上来
(3) 上述情况不满足，把左儿子的子孙中最大的提到需要删除的点上
插入查找删除的复杂度都为$O(\log N)$

中序遍历+前序遍历重建二叉树

code

    
TreeNode* buildTree(vector pre,vector vin, int l1, int r1, int l2, int r2) {
  if(l1 >= r1 || l2 >= r2) return NULL;
  if(l1 + 1 == r1) return new TreeNode(pre[l1]);
  if(l2 + 1 == r2) return new TreeNode(vin[l2]);
  int root_val = pre[l1], i;
  for(i=l2; ileft = buildTree(pre, vin, l1, r1, l2, r2);
  l1 = r1, r1 = l1 + rTree_size;
  l2 = root_pos_vin + 1, r2 = l2 + rTree_size;
  root->right = buildTree(pre, vin, l1, r1, l2, r2);
  return root;
}
TreeNode* reConstructBinaryTree(vector pre,vector vin) {
  if(pre.size() == 0) return NULL;
  return buildTree(pre, vin, 0, pre.size(), 0, vin.size());
}

打印二叉树
从上往下打印出二叉树的每个节点，同层节点从左至右打印。显然BFS
检查二叉树是否对称
前序遍历二叉树-非递归版

code

  
class Solution {
public:
    vector preorderTraversal(TreeNode* root) {
        vector res;
        TreeNode *p = root;
        stack sta;
        while(p != nullptr || !sta.empty()) {
            while(p != nullptr) {
                res.push_back(p->val);
                sta.push(p);
                p = p->left;
            }
            if(!sta.empty()) {
                p = sta.top();
                sta.pop();
                p = p->right;
            }
        }
        return res;
    }
};

平衡二叉树

定义: 二叉查找树基础之上, 根结点的左右子树的高度相差不过1

1.5 Set, Map, Vector

1.6 并查集

查询两个节点是否属于同一个组，沿着树往上走，查询包含这个元素的根是谁。如果两个节点走到同一个根，那么可知它们同属于同一组。

POJ1182 食物链
三种动物ABC，食物链关系为A吃B，B吃C，C吃A，题目给出两种描述：

x和y同属于一类

x吃y
问给出$k$条描述中有几条是假的（和前面的描述产生冲突即为假）
题目给$N$个点，但是我们建立$3N$个点，其中$i\in [0,N)$表示$i$属于种类$A$，$i\in [N,2N)$表示$i$属于种类$B$，$i\in [2N,3N)$表示$i$属于种类$C$.
这样当输入$x$和$y$同属一个种类时，对应地合并三个段里的点($(x+A,y+A),(x+B,y+B),(x+C,y+C)$).而输入给出$x$吃$y$时，按照题目给的关系合并点。
我自己一直搞不明白的是判断矛盾时为什么不把所有情况都列出来，例如对于$x$和$y$属于同一种类的输入，判断$same(x+A,x+B)||same(x+A,x+C)||same(x+B,x+C)$。这是因为读题的问题，题目要求一出现矛盾即++res，而我这样判断会容忍某些矛盾出现，题目要求的是x，y为任意种类时都无矛盾。

code

 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 50010;
int father[3*maxn];
void init(int N){
 for(int i=0; i= n || y < 0 || y >= n) ++res;
     else if(op==2 && x == y) ++res;
     else { // 当x+A和y+B属于同一组，表示x为A时，y一定为B。并且y为B时，x一定为A
         if(op == 1){
             if(find(x+A) == find(y+B) ||
                find(x+A) == find(y+C)
                ){ // 两个动物为同类时，x只可能与0~N同组，不可能与N~2N/N~3N同组
                 ++res;
                 continue;   
             }
             unite(x+A, y+A);
             unite(x+B, y+B);
             unite(x+C, y+C);
         } else {
             // x eat y
             // A eat B, B eat C, C eat A
             if(find(x+A) == find(y+A) ||
                find(x+A) == find(y+C)){ // x吃y时，x不可能与y同组。x只能与x+B同组，不可能与y+C同组
                 ++res;
                 continue;
             }
             unite(x+A, y+B);
             unite(x+B, y+C);
             unite(x+C, y+A);
         }
     }
 }
 printf("%d\n", res);
 return 0;
}

1.7 优先队列、堆 Stack

1.7.1 堆(优先队列)

性质：（小顶堆为例）儿子的值一定不小于父亲的值。堆是一棵完全二叉树
插入：先在堆的末尾（从上到下，从左到右）插入数值，这个数值不断上升（和父节点swap）直到没有大小颠倒为止。仅当父节点大于新插入点时才swap，此时父节点的另一个儿子节点由于一定大等于父节点，因此也大等于新插入点。因此新插入点只需考虑一直向上swap即可，不会破坏堆的有序性
删除：删除堆的根节点（最小值）时，先将堆的最后（指从上到下，从左到右的顺序）一个节点拷贝到根节点上，然后删除最后一个节点。接下来把这个新根节点不断向下交换直到没有大小颠倒为止。
复杂度：插入和删除都为$O(\log N)$

堆的数组实现

 
class Heap_kyo {
public:
    int max_size;
    int size;
    int node[10010];
    Heap_kyo(){
        this->size = 0;
        this->max_size = 0;
    };
    ~Heap_kyo(){
    };
    void float_up(int index) {
        int father_index = index/2;
        while(node[father_index] > node[index]) {
            swap(node[father_index], node[index]);
            index /= 2;
            father_index = index / 2;
        }
    }
    void sink_down() {
        int index = 0;
        int l = index*2 + 1;
        int r = index*2 + 2;
        while((l node[r]) // 因为是完全二叉树，所以右节点存在的时候左节点一定存在 
                       || (!left_condition&&right_condition)) { 
                swap(node[r], node[index]);
                index = r;
            } else { // 两个子节点相等
                swap(node[l], node[index]);
                index = l;
            }
            l = 2*index + 1;
            r = 2*index + 2; 
        }
    }
    void print_tree(){
        for(int i=0; isize < max_size) {
            node[size] = val;
            float_up(size);
            ++size;
        } else {
            if(val > this->top()){
                node[0] = val;
                sink_down();
            }
        }
    }
    int top(){
        return node[0];
    }
    void pop(){
        node[0] = node[size-1];
        --size;
        sink_down();
    }

POJ-2431 Expedition
一辆车从起点往终点开，起点到终点距离为$l$,一开始车上有$p$单位的油，每走一个单位消耗一个单位的油。路上坐标$a[i]$有加油站可以加油$b[i]$单位，假设车装油箱无限大，问最少加几次油能到终点。
每经过一个加油站$a[i]$，可以认为获得了一次在之后任何时候都可以加$b[i]$的权利。在某个时刻车上油耗光时，就利用这个权利认为之前加过了。由于求最小次数，所以每次油耗光取权利时贪心地拿最大的已获得的$b[i]$。所以用一个大顶堆来维护已获得的$b[i]$.

code

 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include "assert.h"
#include 
using namespace std;
const int maxn = 10010;
struct unit {
  int distance;
  int fuel;
}save[maxn];
bool cmp(unit a, unit b) {
  return a.distance > b.distance;
}
int main(){
  int n, l, p;
  scanf("%d", &n);
  for(int i=0; i heap; // 大根堆
  bool flag = true;
  int res = 0;
  for(; l>0; l--, p--) {
      while(p_save < n && l == save[p_save].distance) {
          // 将此处的汽油加入堆中，未来油不够的时候就假设在此处加过油了
          heap.push(save[p_save].fuel);
          ++p_save;
      }
      if(p == 0) {
          // 油用完的场合，因为希望加油次数最少，贪心地加堆顶
          if(heap.empty()) {
              flag = false;
              break;
          } else {
              ++res;
              p += heap.top();
              heap.pop();
          }
      }
  }
  if(flag)
      printf("%d\n", res);
  else 
      printf("-1\n");
  return 0;
}

## 2 搜索参考题单[kuangbin带你飞](https://vjudge.net/article/187) ### 1.1 Depth-First Search

POJ-1321 棋盘问题
棋盘上任意两棋子不能处在同一行同一列, 经典dfs

1.2 Breadth-First Search

POJ-2251 Dungeon Master
三维地图上求起点至终点最短距离, 经典bfs

BFS-经典走地图板子


int bfs(){
  queue que;
  memset(dis, inf, sizeof(dis));
  que.push(sta);
  dis[sta.x][sta.y][sta.z] = 0;
  while(!que.empty()){
      unit q = que.front();
      que.pop();
      if (q == esc) break;
      for(int i=0; i<6; i++){ int nx="q.x" + dx[i], ny="q.y" dy[i], nz="q.z" dz[i]; if(0<="nx&&nx

POJ-3278 Catch That Cow
一维地图上求起点至终点的最短距离, 一眼bfs题. 旅行者可以左右走一步或者以所处坐标的两倍跳跃, 我觉得跳跃的上界可以设置为终点坐标的两倍.
牛客商汤科技2018校招C /算法开发/大数据/后端/运维/测试… 12题

给定四个空杯子，容量分别为S1 S2 S3 S4，允许进行以下操作：

将某个杯子接满水
将某个杯子里的水全部倒掉
将杯子A中的水倒进杯子B，直到A倒空或者B被倒满

问最少要多少步操作才能使得这四个杯子装的水分别为T1 T2 T3 T4

样例(0,0,0,0)->(0,2,0,0)->(0,2,3,0)->(0,2,0,3)->(0,0,2,3)->(0,2,2,3)->(0,1,2,4), 共6步. 同样也是非常经典的bfs问题.

1.3 Binary Search

二分的方法一定是需要找到某种单调性。只要能找到符合条件的单调性，那么在这一个部分一定可以考虑用二分来解决这部分的问题。
参考题单洛谷二分

1.3.1 lower_bound 与 upper_bound

lower_bound(ForwardIter first, ForwardIter last,const _Tp& val)返回一个非递减序列[first, last)中的第一个大于等于值val的位置
upper_bound(ForwardIter first, ForwardIter last, const _Tp& val)返回一个非递减序列[first, last)中第一个大于val的位置

leetcode-Search Insert Position
洛谷P2299
在不递减的数组中寻找第一个大等于target的位置.

洛谷P1102 A-B 数对
在一个无序数组中寻找存在多少对A、B, 使得A-B=C. 事实上对数组排序, 枚举A并二分查找B=A+C的上下界即可.

上界与下界的二分搜索


vector::iterator k_lower_bound(vector &nums, int target) {
  vector::iterator left = nums.begin(), right = nums.end();
  vector::iterator mid;
  while(left < right){
      mid = left + (right-left)/2;
      if (*mid == target) {
          right = mid;
      } else if (*mid < target) {
          left = mid + 1;
      } else { // nums[mid] > target
          right = mid;
      }
  }
  return left;
}
vector::iterator k_upper_bound(vector &nums, int target) {
  vector::iterator left = nums.begin(), right = nums.end();
  vector::iterator mid;
  while(left < right) {
      mid = left + (right-left)/2;
      if(*mid == target) {
          left = mid + 1;
      } else if (*mid < target) {
          left = mid + 1;
      } else { //nums[mid] >target
          right = mid;
      }
  }
  return left;
}

洛谷P1873 砍树
二分枚举数值, 寻找该数值可以取到的最小值. 值得注意的是二分的写法不一定只有$mid=(left+right)/2$. 当在二分内部使用$right-1$来缩小范围时, 可以令$mid=(left+right+1)/2$来让二分终止$while(left<right)$循环.

1.4 剪枝 Pruning

1.5 暴力枚举

POJ-3279 Fliptile
枚举首状态, 随后步骤贪心可以求得首状态下可行解. 在所有可行解中挑出最优解.

3 排序 Sorting

3.1 Quick Sort

3.2 Merge Sort

数组中的逆序对
逆序对可以用树状数组做(比较抽象), 形象的做法用归并. 具体来说, 每次对左有序part和右有序part归并的时候, 如果此时是从右边part头取数字, 这就说明左边part的数字都比右边part这个头大, 构成了sizeof(左边part)的逆序对, 那么答案就要加上sizeof(左边part).
这里贴一个merge sort模版(无本题逆序对的计数)
code
```
 
void mergeArray(int a[], int left, int mid, int right){ 
  int i;
  int p1 = left, p2 = mid+1,p = 0;
  while(p1<=mid&&p2<=right){ if(a[p1]
```

4 Dynamic Programming

约瑟夫环
编号1~n个人玩游戏, 报到数字m的人出局. 一直报到最后1个人, 问最后留下的人编号.
DP$O(n)$解法, 先定义状态$f[i]$为剩下i人时, 出局者的编号. 其实剩下1人可以将其视为他时最后一个出局的.
$i=1$时, 我们把这位天选之子编号记为0. 现在开始倒推0号在初始状态时(剩下n个人时)是几号, $f[2]$时, 可以知道$m-1$出局了, 而0号应该是第$m$人(0 base), 因而$f[2]=(f[1]+m)\mod2$.
进而可知$f[i+1] = (f[i]+m)\mod i$
跳台阶跳1或2层台阶求方案数
$step[i] = step[i-1] + step[i-2]$
矩阵覆盖
最长公共子序列
老经典了，子序列不需要在原串中连续。输入两串$s,t$,$dp[i][j]$表示$s_1…s_i$和$t_1…t_j$两个串对应的LCS，那么当新加入的$s_{i+1}==t_{j+1}$时，$s_1…s_{i+1}$和$t_1…t_{j+1}$可能的LCS是：

在$s_1…s_i$和$t_1…t_j$的公共子序列末尾追加$s_{i+1}$（同时也是$t_{j+1}$）
$s_1…s_{i}$和$t_1…t_{j+1}$的LCS

$s_1…s_{i+1}$和$t_1…t_{j}$的LCS

code

 
class Solution {
public:
 int dp[1010][1010];
 int longestCommonSubsequence(string text1, string text2) {
     for(int i=1; i<=text1.length(); i++){ for(int j="1;" j<="text2.length();" j++) { if(text1[i-1]="=" text2[j-1]) dp[i][j]="max(dp[i-1][j-1]" + 1, max(dp[i-1][j], dp[i][j-1])); } else dp[i][j-1]); return dp[text1.length()][text2.length()]; }; < code>

Leetcode 221 Maximal Square
给出一个由01组成的矩阵，求这个矩阵里最大的全1正方形.定义$dp[i][j]$为全1正方形右下角坐标为$i,j$时，这个正方形最大的边长。
那么对于$dp[i][j]$，需要检查它左上角($dp[i-1][j-1]$)，左边($dp[i][j-1]$)，上边($dp[i-1][j]$)的正方形.比如下图为检查左边正方形的情况,其中n的位置为$i,j$,那么图中x的位置不考虑，从n开始啊往上检查有几个o是1。
1 1 1 o
1 1 1 o
x x x n

code

 
class Solution {
public:
  int maximalSquare(vector>& matrix) {
      int ans = 0;
      int dp[310][310];
      for(int i=0; i=0 && j-1>=0) {//左上的正方形
                      for(int k=0; k=0 && j-k-1>=0; k++) {
                          if(matrix[i-k-1][j] == '0' || matrix[i][j-k-1] == '0' || i-k-1< 0 || j-k-1 < 0) {
                              break;
                          } else {
                              dp[i][j] = k + 2;
                          }
                      }
                  } else if(i-1>=0) { // 上边的正方形
                      for(int k=0; k= 0; k++) {
                          if(matrix[i][j-k-1] == '0' || j-k-1 < 0) {
                              break;
                          } else {
                              dp[i][j] = k+2;
                          }
                      }
                  } else if(j-1>=0) { //左边的正方形
                      for(int k=0; k= 0; k++) {
                          if(matrix[i-k-1][j] == '0' || i-k-1 < 0) {
                              break;
                          } else {
                              dp[i][j] = k+2;
                          }
                      }
                  } 
              }
              ans = max(ans, dp[i][j]);
          }
      }
      return ans*ans;
  }
};

4.1 01背包

Leetcode 416. 分割等和子集
将一个只包含整数的集合分成两个部分，使两个集合的和相等。经典01背包
code
```
class Solution {
public:
  int dp[210][20010];
  bool canPartition(vector& nums) {
      int sum = 0;
      for(int i=0; i
```
Leetcode 474. 一和零
一个字符串集合，字符串仅包含01. 最多能从中挑出几个串，使它们0的数量小等于m，1的数量小等于n。这也能01背包
code
```
class Solution {
public:
  int dp[610][110][110];
  int one_num[610], zero_num[610];
  int findMaxForm(vector& strs, int m, int n) {
      for(int i=0; i
```

4.2 完全背包

[LeetCode 322. 零钱兑换]
给一些硬币数值，每种硬币的数量无限。用这些凑一个给定数字$amount$,求最少硬币数。
对于完全背包问题，完全背包的point是当取第$i$件物品时，可以直接采用$dp[i][j-cost[i]]$状态

code


class Solution {
public:
  int dp[100010];
  const int inf = 0x3f3f3f3f;
  int coinChange(vector& coins, int amount) {
      memset(dp, inf, sizeof(dp));
      dp[0] = 0;
      for (int i=1; i<=coins.size(); i++) { for (int j="0;" j<="amount;" j++) if(j-coins[i-1]>=0 && dp[j-coins[i-1]] != inf) {
                  dp[j] = min(dp[j], dp[j-coins[i-1]] + 1);
              }
          }
      }
      if(dp[amount] == inf) return -1;
      else return dp[amount];
  }
};

4.3 多重背包

POJ1742 Coins
多重背包的不同点是所有的物品有数量限制，那么定义状态dp[i][j]: 取到第i个物品时，物品价值凑的总和为j，第i种物品最多能剩下多少个。状态转移方程可以列为
$$ dp[i][j]=\left{
\begin{aligned}
&num[i]， & dp[i-1][j]\geq 0上一种物品的价值已经能凑出j \
&dp[i-1][j-val[i]] - 1， &j\geq val[i]\ 且\ dp[i-1][j-val[i]\geq 0]第i种物品再装一个\
&-1， & 凑不出来
\end{aligned}
\right.
$$

code


int main() {
  int n, m;
  while(~scanf("%d%d", &n, &m)) {
      if(n==0&&m==0) break;
      for(int i=1; i<=n; i++) { scanf("%d", val + i); } for(int i="1;" i<="n;" num dp[i][j]: 取到第i个硬币时，硬币凑的总和为j，第i种硬币最多能剩下多少个 dp[i]="-1;" dp[0]="0;" dp[0][0] j="0;" j<="m;" j++) if(dp[j]>= 0) { // 上一种硬币已经能凑出j了
                  dp[j] = num[i];
              } else if (j>=val[i] && dp[j-val[i]] >= 0) {
                  dp[j] = dp[j-val[i]] - 1;
              } else {
                  dp[j] = -1;
              }
          } 
      }
      int ans = 0;
      for(int i=1; i<=m; i++) { if(dp[i]>= 0) {
              ++ans;
          } 
      }
      printf("%d\n", ans);
  }
  return 0;
}

4.3 最长上升子序列

LeetCode longest-increasing-subsequence
$O(N^2)$的做法，

code


class Solution {
public:
  int dp[3000];
  int lengthOfLIS(vector& nums) {
      // dp[i] 到第i个字符为止的最长上升子序列长度
      int res = 0;
      for(int i=0; i nums[j]) {
                  dp[i] = max(dp[j]+1, dp[i]);
              }
          }
          res = max(res, dp[i]);
      }
      return res;
  }
};

还可以将状态$dp[i]$定义为：长度为i的上升子序列中末尾元素最小值(不存在则为inf)
先将dp初始化为inf，遍历输入的字符串，从左到右每吃一个字符$c$，就去dp[1~N]中寻找第一个大等于$c$的位置$k$，（注意，dp记录的不再是数字，而是字符/值）然后更新$dp[k]$。由于dp[i]中i的意义是有序的，因此可以二分，复杂度$O(N\log N)$

code


class Solution {
public:
    int dp[3000];
    const int inf = 0x3f3f3f3f;
    int lengthOfLIS(vector& nums) {
        // dp[i]: 长度为i的上升子序列中末尾元素最小值(不存在则为inf)
        memset(dp, inf, sizeof(dp));
        for(int i=0; i=0; i--) {
            if(dp[i] != INF) {
                res = i;
                break;
            }
        }
        return res; 
    }
};

4.4 划分数

n个无区别的物体，将它们分成不超过m组，求划分方案。
将状态定义为$dp[i][j]:j$的$i$划分，把$j$分成$i$份的方案数
考虑$n$的$m$划分的一种方案${a_i}(\sum_{k=0}^m a_k=n)$，如果对于所有的$i$都有$a_i>0$，那么${a_i-1}(\sum_{k=0}^m a_k=n-m)$就是$n-m$的$m$划分；另外如果存在$a_i=0$，那么这个方案就对应了$n$的$m-1$划分，所以递推式为$dp[i][j]=dp[i][j-i]+dp[i-1][j]$

code


int n, m;
int dp[MAX_M+10][MAX_M+10];
int solve(){
    dp[0][0] = 1;
    // dp[i][j]: j的i划分，把j分成i份，方案数
    for(int i=1; i<=m; i++) { for(int j="0;" j<="n;" j++) if(j - i>= 0) {
                dp[i][j] = dp[i-1][j-i] + dp[i-1][j];
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[m][n];
}

### 4.5 多重集组合数

5 Graph Theory

没有圈的连通图叫树，一棵树的边数恰好是顶点数$-1$. 反之，边书等于顶点数$-1$的连通图就是树。
没有圈的有向图叫做DAG（Directed Acyclic Graph）

5.1 最短路 Shortest Path

Dijkstra
Bellman-Ford
Floyd
5.2 拓扑序

LeetCode207 课程表
判断一个有向图拓扑序是否冲突，bfs的方法，先把入度为0的点加入队列中，然后将其指向的点加入队列，并把指向的点的入度-1（即删边)。删到最后所有的点入度应该为0.

code


const int maxn = 1e5+10;
class Solution {
public:
    vector path[maxn];
    int in_num[maxn];
    bool canFinish(int numCourses, vector>& prerequisites) {
        for(int i=0; i que;
        for(int i=0; i

### 5.3 欧拉回路 ### 5.4 最小生成树 Minimum Spanning Tree * Kruskal

6 网络流 Network Flow

6.1 最大流

6.2 最小割

6.3 二分图

Leetcode 判断二分图
直接dfs搜一遍，走一步换个色图，如果相邻点已经涂色那么判一下和自己颜色是不是一样。

code


class Solution {
public:
  bool flag;
  void dfs(int index, int curr_color, vector>& graph, int color[]){
      if(!flag) return;
      color[index] = curr_color;
      for(int i=0; i>& graph) {
      int color[graph.size()];
      memset(color, 0, sizeof(color));
      flag = true;
      for(int i=0; i

### 6.4 费用流

7 贪心 Greedy

参考题单：洛谷贪心专题

区间调度/线段覆盖
给出n个工作，以及每项工作时间上的起点、终点$(s_i,t_i)$，同一时刻只能做一项工作，希望尽可能多做工作，求最大参与的数目。
解法是每次取结束时间最早的那一项。
字典序最小问题
标记线段上的点
线段上有一些点，从中选择若干标记。对于每个点，要求它距离为$R$范围内的区域里必须由带标记的点，（自身为标记点可认为距离为0）。满足此条件求最少标记多少个点。

1.对于每个点，总是往右找一个最远的在距离R内的点去标记。2.然后从这个点往右找第一个超出距离$R$的点，3.重复第1步

切木板
将木板切成$N$块，长度分别为$L_1,L_2,…,L_N$，原木板的长度为$\sum_i^NL_i$,长度为21的木板切成13和8时，开销为21。求切割最小开销。

贪心解法：想了一个$O(n^2\log n)$的做法，因为总是想贪心地合并最小的凉快木板所以需要排序，然而其实不需要对整个数组排序，只需要维护最小和次小值就行了，所以复杂度可以到$O(n^2)$,当然这是纯贪心的做法。

贪心+堆优化解法：贪心不变，就是维护最大最小使用了堆，所以复杂直接到$N\log N$

code


const int maxn = 20010;
int save[maxn];
int main(){
    int n,i,j;
    scanf("%d",&n);
    priority_queue, greater > que;
    for(i=1;i<=n;i++){ scanf("%d",save+i); que.push(save[i]); } long res="0;" while(que.size()> 1) { // 合并到只剩一块木板
        int a, b;
        a = que.top();
        que.pop();
        b = que.top();
        que.pop();
        res += a+b;
        que.push(a+b);
    }
    printf("%lld\n",res);
    return 0;
}

8 数论

9 奇技淫巧

9.1 尺取法

9.2 倍增

9.3 快速幂

数值的整数次方
9.4 滑动窗口

(leetcode 3) Longest Substring Without Repeating Characters
求字符串$s$内最长连续子串，使得子串内没有重复的字符
定义左指针右指针，并且用$map[s[i]]$记录$s[i]$上次出现的位置。窗口的右边界向右扩张时，如果右边界的字符上一次出现的位置在左边界及其之后，那么把左边界往上次出现的位置后一位调整。这个过程中记录区间的长度最大值。

code


class Solution {
public:
  int lengthOfLongestSubstring(string s) {
      int l = 0, r = 0, ans = 0;
      map mp;
      // [l, r]这个窗口内没有重复的字符
      while(r < s.length()) {
          if(mp.count(s[r]) && mp[s[r]]>=l) { // 假如现在的字符上一次出现在左端点及左端点之后， 那么把左端点往上次出现的位置后挪一位
              l = mp[s[r]] + 1;
          }
          mp[s[r]] = r;
          ans = max(ans, r - l + 1);
          ++r;
      }
      return ans;
  }
};

10 博弈论

10.1 Nim游戏

11 脑筋急转弯

反码、补码
正数的补码 = 原码
负数的补码 = 负数的原码取反（符号位保持不变）+ 1
eg: [ -7 ]补=11111001（八位二进制） : 原码： 10000111—— 反码（符号位不变）：11111000——加1得补码：11111001
原来1一直左移(p=1, p<<1)最后会变成0啊. 最后会这样:-2147483648->0->1

算法知识点

1 数据结构 Data Structure

1.1 Stack

1.2 Queue

1.3 Linked List

1.4 树 Tree

二叉搜索树 Binary serch Tree

平衡二叉树

1.5 Set, Map, Vector

1.6 并查集

1.7 优先队列、堆 Stack

1.7.1 堆(优先队列)

1.2 Breadth-First Search

1.3 Binary Search

1.3.1 lower_bound 与 upper_bound

1.4 剪枝 Pruning

1.5 暴力枚举

3 排序 Sorting

3.1 Quick Sort

3.2 Merge Sort

4 Dynamic Programming

4.1 01背包

4.2 完全背包

4.3 多重背包

4.3 最长上升子序列

4.4 划分数

5 Graph Theory

5.1 最短路 Shortest Path

5.2 拓扑序

6 网络流 Network Flow

6.1 最大流

6.2 最小割

6.3 二分图

7 贪心 Greedy

8 数论

9 奇技淫巧

9.1 尺取法

9.2 倍增

9.3 快速幂

9.4 滑动窗口

10 博弈论

10.1 Nim游戏

11 脑筋急转弯