第三章 栈

p57 等价类划分问题 - 邻接表的DFS

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
/**
  结构体为 AGragh n为元素个数  r为等价条件数
  输入的集合是1～n的数
**/
void equiv(int n, int r) {
  int a, b, visit[n+1] = {0};
  stack<int> stack;
  AGragh *g = new AGragh();
  G->n = n, G->e = r;
  for (int i = 1; i <= n; i++) {
    g->adjList[i].firstarc->next = NULL; // 为数组中的每个结点新建链表
  }
  for(int i = 1; i < r; i++) {
    scanf("%d%d", &a, &b); //输入等价条件 创建邻接表
    ListInsert(0, b, g->adjList[a]);
    ListInsert(0, a, g->adjList[b]);
  }
  // 以下相当于邻接表的DFS
  for(int i = 1; i < r; i++) {
    if (visit[i] == 0) { // 依次找到visit数组未被访问的结点，形成新的类型
      stack.push();
      while(!stack.empty()) {
        int cur = stack.top();
        cout<< cur << " ";
        ANode *q = g->adjList[cur].firstarc;
        while(visit[q->adjvex] == 1 && q) q = q->nextarc;
        if(q == NULL) stack.pop();
        else {
          visit[q->adjvex] = 1;
          stack.push(q->adjvex);
        }
      }
      printf("\n");
    }
  }
}

p59 直方图最大面积矩形问题 -

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
/**
  算法思想： 对于某一子块W来说，其被包含的最大面积为：
  向左找到第一个小于W值的块位置i 向右找到第一个小于W值的块位置j 则 S = w * (j-i)
  假设从i = 0开始
**/
int hosto(int n, int p) {
  int max = 0; i = 0, s;
  stack<int> stack;
  while(i<n) {
    // 小于栈顶的元素都入栈
    if(stack.empty() && p[stack.top()] <= p[i]) stack.push(i); i++;
    else {
      // 此时来到一个j 其值小于栈顶 对栈顶来说 是右侧第一个较小的数
      int temp = stack.top();
      stack.pop();
      if(stack.empty()) s = p[temp] * i; //队列中只有自己，表明在此之前，没有比此方格更小的。
      else s = p[temp] * (p - stack.top() + 1); // 和老师的有点出入 我觉得他忘了加括号
      if(max < s) max = s;
    }
  }
  while(!stack.empty()) {
    int temp = stack.top();
    stack.pop();
    if(stack.empty()) s = p[temp] * i; //自己是最小的
    else s = p[temp] * (p - stack.top() + 1);
    if(max < s) max = s;
  }
  return max；
}

第四章 队列

p70 电路布线问题 BFS + 回溯

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
//默认给出的pos数组内元素值均为0
int search(vector<int> a, vector<int> b, vector<vector<int>> pos) {
  int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; //相对位移
  queue<vector<int>> q; // 待考察方格队列
  if(a[0][0] == b[0][0] && a[0][1] == b[0][1]) return 0;//两方格相同
  q.push(a); //将a入队
  pos[a[0][0]][a[0][1]] = 2;
  int step = 2, size, len; //分别记录步数及队列的长度
  vector<int> m, ans;
  while(!q.empty()) {
    size = q.size();
    step += 1;
    m = q.front();
    q.pop();
    for(int j = 0; j < size; j++) {
      // 开始遍历上下左右
      for(int i = 0; i < 4; i++) {
        int x = dx[i] + m[0][0], y = dy[i] + m[0][1];
        if(x>=0 && x<pos.size() && y>=0 && y<pos[i].size() && pos[x][y] == 0) {
          ans[0][0] = x; ans[0][1] = y;
          q.push(ans); pos[x][y] = step;
        }
        if(x == b[0][0] && y == b[0][1]) {
          len = pos[x][y] - 2;
          return pos[x][y] - 2; //找到该点，并且该点的长度也被修改了
        }
      }
    }
  }
  return 0;
}

p72 窗口查询问题 单调队列（双端）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> q; int left=0, max;
        vector<int> ans;
        if(nums.size()==0) return ans;
        for(int i = 0; i < nums.size(); i++) {
            while(!q.empty() && nums[q.back()] <= nums[i]) q.pop_back();
            if(!q.empty() && i - q.front() >=k) q.pop_front();
            q.push_back(i); max = nums[q.front()];
            if(i>=k-1) {
                ans.push_back(max);
            }
        }
        return ans;
    }

第五章 排序

各类改进算法

p98 带权中位数 快排 + 分治

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
// 时间复杂度为O(logn)版本

int main() {
  // 使用内置的sort函数或者快排
  int R[m] = ...
  quickSort(R, 0, m); // 排序完成
  // sort(R, 0, m); 因为内置的排序函数也是使用的快排 所以时间复杂度没有区别
  int i = 0; double c = 0;
  while(i<m && c+R[i]<0.5) c+=R[i];  //权重值相加，直到所有权值之和大于总值的一半
  return R[i];
}

void quickSort(int R[], int low, int high) {
  int temp = R[low];
  int i = low, j = high;
  if(low < high) {
    while(i < j) {
      while(i<j && R[j]>temp) j--;
      if(i<j) {
        R[i] = R[j];
        ++i;
      }
      while (i<j && R[i]<temp) i++;
      if(i<j) {
        R[j] = R[i];
        --j;
      }
    }
    R[i] = temp;
    quickSort(R, low, i-1);
    quickSort(R, i+1, high);
  }
}

拓展：部分背包问题

问题描述：

一个窃贼去一家商店偷窃，有n件商品：第 i 件商品价值 vi 元，重 wi 磅（vi、wi都是整数），他的背包最多只能装下 w 磅物品，每个商品他可以选择一部分带走，问他最多能带走多贵的物品？

问题分析：

窃贼可对每件商品选择一部分带走，这不同于0-1背包问题，这里的商品就像是金粉😳

算法分析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
我们可以对每件商品的价值 —— 每磅的价值 进行排序，然后按价值大小依次往背包里装，这样，时间复杂度为 O(n*logn)。这里，时间复杂度主要是排序，那么，可以不排序吗？

  当然OK。就像是上面查找带权中位数的算法，排序只是为了将单价高的商品筛选出来，所以我们并不需要将所有的商品价值进行排序。

  采用分治法（divide and conquer），先找出中位数！

  找出其中位数，将数组分为 SL[单价大于中位数]、SV[单价等于中位数]、SR[单价小于中位数] 三个集合；

  接下来分3种情况：
// 重点
  ①如果 SL 数组中所有商品的重量 ≥ w，则问题在 SL 中递归解决；

  ②如果 SL + SV ≥ w，则先将 SL 中的物品全部装入包中，然后在 SV 中递归解决；

  ③如果 SL + SV < w，则将 SL 和 SV 中的物品全部装入背包中，再在 SR 中递归解决。

时间复杂度分析：

1
T(n) ≤ T(n/2) + O(n)   → T(n) = O(n)

p99 最大递增序列 排序 + 贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int maxs(vector<vector<int>> s) {
  int n = s.size(), m = s[0].size(); // n行m列的整数矩阵
  for(int i = 0; i < n; i++) {
    sort(s[i], 0, m); //对每行进行排序
  }
  int sum = s[n-1][m-1], pre = s[n-1][m-1];
  for(int i = n-2; i>=0; i--) {
    for(int j=m-1; j>=0; j--) {
      if(a[i][j] < pre) {  //从每一列的最后一个元素往左找 比pre小则选中 并跳出 比较下一行
        pre = a[i][j];
        sum+= pre;
        break;
      }
    }
    if(j==-1) return 0; //说明该行没有找到 不存在递增序列
  }
  return sum;
}

第六章 二叉树

p143 信号增强装置 贪心

IMG_2BE6568F1E09-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/** 使用后序遍历，可以使其计算过程最后来到根结点
**/
void Place(btlink x) {
  int deg;
  btlink y->left;
  x->element.D = 0; // 防止没有子树的情况 及 仅有一个孩子的情况
  if(y) {
    deg = y.element->D + y.element->d;
    if(deg > tol) {
      y.element->boost = 1;
      x.element->D = y.element->d; // 注意区别是修改 x 还是 y
    }
    else x.element->D = deg;
  }
  y = x->right;
  if(y) {
    deg = y.element->D + y.element->d;
    if(deg > tol) {
      y.element->boost = 1;
      x.element->D = y.element->d; // 注意区别是修改 x 还是 y
    }
    if(x->element.D<deg) x.element->D = deg;
  }
}

p145 最长连续递增子序列 像分治

IMG_FC64AC4A4CAE-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 书上代码难看 我也看不懂 所以自己找了一个
int maxLengthAc(int arr[], int n, int Len[]) {
    int max = 1;
    for(int i = 0; i<n-1; i++) {
        if(arr[i+1] > arr[i]) Len[i+1] = Len[i]+1;
        if(Len[i+1] > max){ max = Len[i+1]; q = i+1;}
    }
    return max;
}
int main() {
    int n;
    scanf("%d", &n);
    int arr[n], Len[n];
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        Len[i] = 1;
    }
    int max = -1;
    max = maxLengthAc(arr, n, Len);
    for(int i = q-max+1; i<=q; i++) {
        printf("%d ", arr[i]);
    }
}

第七章 散列表

p170 元素唯一性问题

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
const int N = 12;
int n, h[N], a[N];
bool find(int x) {
    int k = x % N; //不考虑负数
    while(a[k]!=-1 && a[k]!=x) {
        k++;
        if(k==N) k = 0;
    }
    return k;
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &h[i]);
    }
    memset(a, -1, sizeof a);
    for (int i = 0; i < n; i++) {
        int k = find(h[i]);
        if( a[k] == h[i]) { //查找成功
            cout << "元素重复" << endl; exit(-1);
        } else {
            a[k] = h[i];
        }
    }
    cout << "无重复元素" << endl;
}

p170 字符串频率统计问题

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
int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点 输入了几个结点 son就有几行 真的是牛逼啊
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}
// 查询字符串出现的次数
int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

int main() {
  scanf("%d", &n);
  char op[2]; string str;
  while(n--) {
    scanf("%s%s", op, str);
    if(op[0] == 'I') insert(str);
    else printf("%d\n", query(str));
  }
  return 0;
}

第八章 优先队列

p186 哈夫曼编码

​ priority_queue, 优先队列，默认是大根堆
​ push() 插入一个元素
​ top() 返回堆顶元素
​ pop() 弹出堆顶元素
​ 定义成小根堆的方式：priority_queue<int, vector, greater> q;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 需要引用的头文件
#include <vector>
#include <queue>

int n, k, res;
int main() {
    //升序 greater
    priority_queue<int, vector<int>, greater<int>> heap;
    //降序 priority_queue <int,vector<int>,less<int> >q;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &k);
        heap.push(k); //建立小根堆
    }
    while(heap.size() > 1) {
        int a = heap.top(); heap.pop();
        int b = heap.top(); heap.pop();
        res += (a + b);
        heap.push(a+b);
    }
    cout << heap.top();
}

第九章 并查集

p199 离线最小值问题

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 20;
vector<int> en, in, out;
int root[N], dis[N], si[N], is[N], pre[N], post[N], h[N];
int n, idx, p;
char op[2];
int findRoot(int x) {
    while(root[x] != x) x = root[x];
    return x;
}

// 路径压缩
void Union(int x, int y) {
    int x_root = findRoot(x);
    int y_root = findRoot(y);
    if (x != y) {
        if(dis[x_root] > dis[y_root]) root[x_root] = y_root;
        else if(dis[x_root] < dis[y_root]) root[y_root] = x_root;
        else {
            root[y_root] = x_root;
            dis[x_root]++;
        }
    }
}
void mergeIn(int k) {
    // 集合数
    for(int i = 1; i <= k; i++) {
        int cur, index;
        // 第一个集合的root位置为 in[1]，cur拿root
        if(i==1) {
            cur = in[1];
            index = 0;
        }
        // en[] = {2,3,4} ; in[] = {3(1),4(2),2(3),1(3)}； 第i个集合的起始下标是en[i-1]
        // 例如，第二个集合的起始下标， 先取下标， 再加1
        else {
            index = en[i-1];
            cur = in[index + 1]; //对应下标在in中取到的元素 第i个集合的第1个元素
        }
        for(int j = index + 1; j <= en[i]; j++) {
            Union(cur, in[j]);
            // 映射关系 si[3] = 1; is[1] = 3;
            si[cur] = i; is[i]=cur;
        }
    }
    //数组链表
    for(int i = 1; i < k; i++ ) {
        // 集合i+1的前驱是i 集合i的后继是i+1 共有k个集合
        pre[i+1] = i;
        post[i] = i + 1;
    }
    for(int i = 1; i <= p; i++) {
        int name = findRoot(i); //找到1的根结点
        int t = si[name]; // 所属集合 2
        if(t<=k) // 集合存在 该集合的下一个集合与该集合合并
        {
            int newset = name;
            if(is[post[t]]) {
                Union(name, is[post[t]]);
            }
            // 映射关系 name所对应的集合 与 post[t]所指向的集合合并 即I1 合并至 I2
            si[name] = post[t];
            // 将is的映射关系做相应的修改
            is[post[t]] = newset;
            post[pre[t]] = post[t];
            pre[post[t]] = pre[t];
            // 第i个数在第t个集合中，意思是当来到t时它才会被输出
            h[t] = i;
        }
    }
}

int main() {
    scanf("%d", &n);
    p = n;
    en.push_back(0);
    in.push_back(0);
    while(n--) {
        scanf("%s", op);
        if(op[0] == 'D') en.push_back(idx);
        else {
            int s = op[0] - '0';
            in.push_back(s);
            idx++;
        }
    }
    for(int i = 1; i <= p; i++) {
        root[i] = i;
        dis[i] = 0;
    }
    // 将insert分成了en.size()个集合
    int len = en.size();
    mergeIn(len-1);
    for(int i = 1; i <= len-1; i++) {
        cout << h[i] << " ";
    } // wocaonio
}

p200 朋友圈问题

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
/**
	输入： 5 3					输出：2
				F 1 2
				E 2 3
				E 3 4
				E 5 3
**/
const int N = 20;
int n, m, root[N], e[N];
char op[2];
int a, b, ans;

int findRoot(int x) {
    while(root[x] != x) x = root[x];
    return x;
}

void Union(int x, int y) {
    int x_root = findRoot(x);
    int y_root = findRoot(y);
    if(x_root!=y_root) root[y_root] = x_root;
}
int main() {
    scanf("%d%d", &n, &m); //n个人m条朋友圈
    for(int i = 1; i <= n; i++ ) {
        root[i] = i;
        e[i] = 0;
    }
    while(m--) {
        scanf("%s%d%d", op, &a, &b);
        if(op[0] == 'E') {
            if(e[a] == 0) e[a] = b;
            else Union(e[a], b); // 如果a已经有敌人 则把b和a的敌人合并
            if(e[b] == 0) e[b] = a;
            else Union(e[b], a); // 同理，如果b有敌人 则把敌人合并成朋友
        } else {
            Union(a, b);
        }
    }
    for(int i = 1; i <=n ; i++) {
        if(root[i] == i) ans++;
    }
    cout << ans;
}