普里姆（Prim）算法

构造邻接矩阵

1. 结构体

   1 2 3 4 5 6 7 8 9

   typedef char VertexType; typedef int EdgeType; #define MAXVEX 100 #define INFINITY 0x3f3f3f3f // 在程序设计中，将无穷大设为0x3f3f3f3f typedef struct { VertexType vexs[MAXVEX]; EdgeType arc[MAXVEX][MAXVEX]; int numVertexes, numEdges; }MGraph;

2. 实例化邻接矩阵

   1 2 3 4 5 6 7 8 9 10 11

   MGraph G; memset(G.arc, 0x3f, sizeof(G.arc)); int N; cout << "请输入有多少条边："; cin >> N; for (int i = 0; i < N; i++) { int ti, tj, va; cin >> ti >> tj >> va; G.arc[ti][tj] = va; G.arc[tj][ti] = va; }

生成最小生成树

步骤：

1. 随机将一个点作为生成树的顶点，这里以$V_0$为顶点；
2. 将各点与$V_0$的距离保存到 lowcost 数组中；
3. adjvex 用来存储各个顶点的值，用来看是哪个点与接下来的哪个点相连的；
4. lowcost 存储各个顶点是否为生成树顶点；
5. 遍历数组 lowcost ，找到与顶点 $V_0$最短的边，并将对应的顶点，添加到生成树中；
6. 接着，将下一个顶点与$V_0$看成整体 O，更新 lowcost 的值（更新其他顶点与 O 的更短的距离）;
7. 直到数组 lowcost 全部为0。

代码：

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

/**
  * Prim算法生成最小生成树 
  */
void MiniSpanTree_Prim(MGraph G)
{
    int min, lowcost[MAXVEX], adjvex[MAXVEX];
    lowcost[0] = 0; // 以v0作为生成树的顶点
    for (int i = 1; i < G.numVertexes; i++) {
        lowcost[i] = G.arc[0][i]; // [0][i]  是因为v0为生成树的顶点
        adjvex[i] = 0; //这里为0，是因为以V0作为生成树的顶点
    }

    for (int i = 1; i < G.numVertexes; i++) {
        int j = 1, k = 0;
        min = 0x3f3f3f3f;
        while (j < G.numVertexes) {
            if (lowcost[j] != 0 && min > lowcost[j]) {
                min = lowcost[j];
                k = j;
            }
            j++;
        }
        printf("(%d, %d), %d", adjvex[k], k, min);
        
        lowcost[k] = 0;
        // 更新lowcost
        for (int j = 1; j < G.numVertexes; j++) {
            if (lowcost[j] != 0 && lowcost[j] > G.arc[k][j]) {
                adjvex[j] = k;
                lowcost[j] = G.arc[k][j];
            }
        }
    }   
}

克鲁斯卡尔（Kruskal）算法

步骤：

1. 判断该边添加上之后是否会使生成树生成回路，由于该边是与其两端点有关系，因此，判断该点是否在生成树中即可；
2. 用一个数组标明

串的定义

1. 定义：由零个或多个字符组成的有限序列，又名叫字符串
2. 所谓的序列，说明串的相邻字符之间具有前驱和后继的关系
3. 子串在主串中的位置就是子串的第一个字符在主串种的序号

串的比较

1. 串的比较是通过组成串的字符之间的编码来进行的
2. 字符的编码指的是字符再对应字符集中的序号
3. 类似于：查字典就是在比较字符串大小的过程

串的抽象数据类型

1. 字符串与线性表的差别：
   1. 线性表更关注的是单个元素的操作，比如查找一个元素，插入或删除一个元素
   2. 串中更多的是查找子串的位置、得到指定位置子串、替换子串等操作

朴素的模式匹配算法

1. 子串的定位操作通常称作串的模式匹配
2. 简单的说，就是对主串的每一个字符作为子串开头，与要匹配的字符串进行匹配。对主串做大循环，每个字符开头做T长度的小循环，指导匹配成功或全部遍历完成为止。
3. S的长度放在S[0]中，T的长度放在T[0]中
4. 代码

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

   int Index(string S, string T, int pos) { int i = pos; int j = 1; while (i <= S[0] && j <= T[0]) { if (S[i] == T[j]) { i++; j++; } else { i = i - j + 2; j = 1; } } if (j > T[0]) return i - T[0]; else return 0; }

KMP模式匹配算法

题目

解析

1. 类似于 30. 三角形最小路径和
2. 不同点：比 30. 三角形最小路径和难，难于： 都是一排排的数，而不是三角形，但是思路是一样的，最后看dp[0][6]的值（整体向右挪了一位，并且删除边缘效应，且从上到下，第0秒是最终结果）

代码

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

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;

const int N = 100010;
int dp[N][13];


int main() {
    int n;
    while(~scanf("%d",&n)) {
        if (n == 0) break;
        int maxt = 0;
        memset(dp, 0, sizeof(dp)); // 为什么不加这个会报错????
        for (int i = 0; i < n; i++) {
            int x, t;
            scanf("%d%d", &x, &t);
            dp[t][x + 1]++;
            maxt = max(maxt, t);
        }

        for (int i = maxt - 1; i >= 0; i--) {
            for (int j = 1; j < 12; j++) {
                dp[i][j] += max(dp[i + 1][j - 1], max(dp[i + 1][j], dp[i + 1][j + 1]));
            }
        }

        cout << dp[0][6] << endl;
    }

    return 0;
}

题目

解析

1. 从第一个到最后一个字母进行遍历，父循环循环变量(i)决定子串的右端
2. 其次，子循环循环变量(j)决定子串的左端
3. 然后，若是j左侧不可拆分，那么就跳过（因为左边无法拆分，即便右边可以拆分也没有意义）
4. 输出dpn

【释】：dp 负责记录 第n个之前（包括第n个）能否拆分

代码

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

#include <bits/stdc++.h>

using namespace std;

int main()
{
    string s;
    int n, nn;
    cin >> s >> nn;
    n = s.size();
    vector<bool> dp(n + 1, false);
    set<string> ss;
    for (int i = 0; i < nn; i++) {
        string t;
        cin >> t;
        ss.insert(t);
    }

    dp[0] = true;
    for (int i = 0; i <= n; i++) {
        for (int j = i; j > 0; j--) {
            if (!dp[j - 1])
                continue;
            if (ss.find(s.substr(j - 1, i - j + 1)) != ss.end()) {
                dp[i] = true;
                break;
            }
        }
    }

    cout << boolalpha << dp[n];
    return 0;
}

基本术语

二叉树性质

1. 在二叉树得第i(i >= 1)层最多有$2^{i-1}$个节点
2. 深度为k(k>=1)的二叉树上至多含$2^k-1$个节点
3. 对任何一颗二叉树，若它含有$n_0$个叶子节点、$n_2$个度为2得节点，则必存在关系式：$n_0=n_2+1$
4. 具有n个节点的完全二叉树的深度为$\lfloor{\log{_2n}+1} \rfloor$
5. 若对含n个节点的完全二叉树从上到下且从左到右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点（简称为结点i），有以下关系：
   1. 若i=1，则结点i是二叉树的根，无双亲节点；若i>1,则结点$\lfloor{i/2} \rfloor $为其双亲结点
   2. 若2i>n，则节点i无左孩子;否则结点2i为其左孩子；
   3. 若2i+1>n，则结点i无右孩子；否则，结点2i+1为其右孩子。

定义

1. 树（Tree）是n(n >= 0 )个结点的有限集。n = 0时称为空树。在任意一棵非空树中：（1）有且仅有一个特定的称为根（root）的结点；（2）在 n > 1 时，其余结点可分为m（m > 0）个互不相交的有限集 $T_1, T_2, T_3 … T_m$，其中每一个集合本身又是一颗树，并且称为根的子树（SubTree）。

2. n > 0时根结点是唯一的，不可能存在多个根结点。

3. m > 0时，子树的个数没有限制，但他们一定是互不相交的。

4. 结点用用改的子树数称为结点的度。

5. 度为0的结点称为叶子结点或终端结点；度不为0的结点称为非终端结点或分支结点。

6. 除根结点之外，分支结点称为内部节点。

7. 树的度是树内各结点度的最大值。

为什么$n$个结点的树，有$n - 1$条边

1. 假设有1个结点时，则有0条边
2. 有2个结点时，若是连通的且不能为环，所以就得有$1$条边将这两个结点连接在一起
3. 若有3个结点时，将前两个看为一个整体，则必须有$1$条边，将这两个部分连接在一起
4. 以此类推

【释】：整体化一思想

1. 内存单元从0开始编号，称为内存地址。每个内存单元可以看作一间房间，内存地址就是门牌号。

数据类型

基本数据类型/原始类型（primitive type）

1. 用于保存简单的单个数据
2. 首字母一般小写
3. 基本数据类型：
   1. int (4B)
      Java的整型数字中间可以加入下划线以便用户识别。
   2. short (2B)
   3. long (8B)
   4. byte (1B)
   5. float (4B)

      1. 对于float类型，需要加上f后缀,如: float f = 3.14e5f;
      2. float类型可最大表示 $3.4 \times 10^{38}$

   6. double (8B)
      float类型可最大表示 $1.79 \times 10^{308}$
   7. boolean (1B)

      Java语言对布尔类型的存储并没有做规定，因为理论上存储布尔类型只需要1 bit，但是通常JVM内部会把boolean表示为4字节整数。

   8. char (2B)

      1. 布尔类型boolean只有true和false两个值
      2. 字符类型char表示一个字符。Java的char类型除了可表示标准的ASCII外，还可以表示一个Unicode字符，如： char a = '中';
      3. 注意char类型使用单引号’，且仅有一个字符，要和双引号”的字符串类型区分开。

4. 引用类型

   1. 除了上述基本类型的变量，剩下的都是引用类型。例如，引用类型最常用的就是String字符串: String s = "hello";
   2. 引用类型的变量类似于C语言的指针，它内部存储一个“地址”，指向某个对象在内存的位置.

   通俗的解释：引用类型的变量赋值，先申请内存存放内容，然后变量再指向它，若改变变量的值，则会再重新申请内存，放入内容，再将变量指向这块内存，原来的内存还在只不过无法通过变量指向它罢了。

5. 常量

> 1. 定义变量的时候，如果加上final修饰符，这个变量就变成了常量

   
1
2
3
4
final double PI = 3.14; // PI是一个常量
double r = 5.0;
double area = PI * r * r;
PI = 300; // compile error!

> 2. 常量在定义时进行初始化后就不可再次赋值，再次赋值会导致编译错误。
> 3. 常量的作用是用有意义的变量名来避免魔术数字（Magic number），例如，不要在代码中到处写3.14，而是定义一个常量。如果将来需要提高计算精度，我们只需要在常量的定义处修改，例如，改成3.1416，而不必在所有地方替换3.14。
> 4. 根据习惯，常量名通常全部大写。

11. var关键字

> 1. 有些时候，类型的名字太长，写起来比较麻烦。例如：`StringBuilder sb = new StringBuilder();`, 这个时候，如果想省略变量类型，可以使用var关键字： `var sb = new StringBuilder();`,编译器会根据赋值语句自动推断出变量sb的类型是StringBuilder。对编译器来说，语句：`var sb = new StringBuilder();`,实际上会自动变成：`StringBuilder sb = new StringBuilder();`
> 2. 使用var定义变量，仅仅是少写了变量类型而已。

12. 定义变量时，要遵循作用域最小化原则，尽量将变量定义在尽可能小的作用域，并且，不要重复使用变量名。

13. 整数运算

    1. 整数的数值表示不但是精确的，而且整数运算永远是精确的，即使是除法也是精确的，因为两个整数相除只能得到结果的整数部分
    2. 特别注意：整数的除法对于除数为0时运行时将报错，但编译不会报错
    3. 要特别注意，整数由于存在范围限制，如果计算结果超出了范围，就会产生溢出，而溢出不会出错，却会得到一个奇怪的结果
    4. 自增/自减、+=，-=，*=，/=：同C++
    5. 移位运算
       1. >>: 根据符号位来补充
       2. 无符号的右移运算>>>: 它的特点是不管符号位，右移后高位总是补0
    6. 位运算
       1. 与运算: &
       2. 或运算: |
       3. 非运算: ~
       4. 异或运算: ^

14. 运算优先级

    • ()
    • ! ~ ++ --
    • * / %
    • + -
    • << >> >>>
    • &
    • |
    • += -= *= /=

15. 浮点数运算

    1. 浮点数运算会产生误差

       浮点数运算和整数运算相比，只能进行加减乘除这些数值计算，不能做位运算和移位运算。在计算机中，浮点数虽然表示的范围大，但是，浮点数有个非常重要的特点，就是浮点数常常无法精确表示。

       举个栗子：
       
       浮点数0.1在计算机中就无法精确表示，因为十进制的0.1换算成二进制是一个无限循环小数，很显然，无论使用float还是double，都只能存储一个0.1的近似值。但是，0.5这个浮点数又可以精确地表示。
       
       因为浮点数常常无法精确表示，因此，浮点数运算会产生误差:

       1 2 3 4 5 6 7 8 9

       public class Main { public static void main(String[] args) { double x = 1.0 / 10; double y = 1 - 9.0 / 10; // 观察x和y是否相等: System.out.println(x); System.out.println(y); } }

       结果为：

       1 2	0.1 0.09999999999999998

    2. 溢出

       整数运算在除数为0时会报错，而浮点数运算在除数为0时，不会报错，但会返回几个特殊值：

       1. NaN表示Not a Number
       2. Infinity表示无穷大
       3. Infinity表示负无穷大
          如：

       1 2 3

       double d1 = 0.0 / 0; // NaN double d2 = 1.0 / 0; // Infinity double d3 = -1.0 / 0; // -Infinity

16. 布尔运算

    1. 布尔运算是一种关系运算，包括以下几类：
       • 比较运算符：>，>=，<，<=，==，!=
       • 与运算 &&
       • 或运算 ||
       • 非运算 !
    2. 关系运算符的优先级从高到低依次是
       • !
       • >，>=，<，<=
       • ==，!=
       • &&
       • ||
    3. 短路运算、三元运算符：同C++

17. 字符与字符串

    1. 字符类型

       Java在内存中总是使用Unicode表示字符，所以，一个英文字符和一个中文字符都用一个char类型表示，它们都占用两个字节。要显示一个字符的Unicode编码，只需将char类型直接赋值给int类型即可

       1 2	int n1 = 'A'; // 字母“A”的Unicodde编码是65 int n2 = '中'; // 汉字“中”的Unicode编码是20013

    2. 字符串类型

       和char类型不同，字符串类型String是引用类型，我们用双引号"..."表示字符串。一个字符串可以存储0个到任意个字符：

       1. 常见的转义字符包括：

          • \" 表示字符"
          • \' 表示字符'
          • \\ 表示字符\
          • \n 表示换行符
          • \r 表示回车符
          • \t 表示Tab
          • \u#### 表示一个Unicode编码的字符

       2. 字符串连接

          Java的编译器对字符串做了特殊照顾，可以使用+连接任意字符串和其他数据类型，这样极大地方便了字符串的处理。例如：

          1 2 3 4 5 6 7 8

          public class Main { public static void main(String[] args) { String s1 = "Hello"; String s2 = "world"; String s = s1 + " " + s2 + "!"; System.out.println(s); } }

          如果用+连接字符串和其他数据类型，会将其他数据类型先自动转型为字符串，再连接：

          1 2 3 4 5 6 7

          public class Main { public static void main(String[] args) { int age = 25; String s = "age is " + age; System.out.println(s); } }

       3. 多行字符串

          如果我们要表示多行字符串，使用+号连接会非常不方便：
          
          从Java 13开始，字符串可以用”””…”””表示多行字符串（Text Blocks）了。举个例子：

          1 2 3 4 5 6 7 8 9 10 11

          public class Main { public static void main(String[] args) { String s = """ SELECT * FROM users WHERE id > 100 ORDER BY name DESC """; // 因为""" 换行了，所以相当于在 DESC 后面加了一个\n System.out.println(s); } }

          如果多行字符串的排版不规则，总是以最短的行首空格为基准。

       4. 不可变特性

          String s = “hello”;时，JVM虚拟机先创建字符串”hello”，然后，把字符串变量s指向它：紧接着，执行s = “world”;时，JVM虚拟机先创建字符串”world”，然后，把字符串变量s指向它：原来的字符串”hello”还在，只是我们无法通过变量s访问它而已。因此，字符串的不可变是指字符串内容不可变。

          理解了引用类型的“指向”后，试解释下面的代码输出：

          1 2 3 4 5 6 7 8

          public class Main { public static void main(String[] args) { String s = "hello"; String t = s; s = "world"; System.out.println(t); // t是"hello"还是"world"? } }

       5. 空值null

          引用类型的变量可以指向一个空值null，它表示不存在，即该变量不指向任何对象。例如：

          1 2 3 4

          String s1 = null; // s1是null String s2; // 没有赋初值值，s2也是null String s3 = s1; // s3也是null String s4 = ""; // s4指向空字符串，不是null

          注意要区分空值null和空字符串””，空字符串是一个有效的字符串对象，它不等于null。

18. 数组

    1. 定义一个数组类型的变量，使用数组类型 类型[]，例如，int[]。和单个基本类型变量不同，数组变量初始化必须使用new int[5]表示创建一个可容纳5个int元素的数组。

    2. Java的数组有几个特点：

       • 数组所有元素初始化为默认值，整型都是0，浮点型是0.0，布尔型是false；
       • 数组一旦创建后，大小就不可改变。

    3. 数组大小：数组变量.length

    4. 数组是引用类型，在使用索引访问数组元素时，如果索引超出范围，运行时将报错

    5. 在定义数组时直接指定初始化的元素，这样就不必写出数组大小，而是由编译器自动推算数组大小

    6. 对于数组ns来说，执行ns = new int[] { 68, 79, 91, 85, 62 };时，它指向一个5个元素的数组；再执行ns = new int[] { 1, 2, 3 };时，它指向一个新的3个元素的数组：但是，原有的5个元素的数组并没有改变，只是无法通过变量ns引用到它们而已。

    7. 字符串数组

       1 2 3

       String[] names = { "ABC", "XYZ", "zoo" };

       对names[1]进行赋值，例如names[1] = "cat";，原来names[1]指向的字符串”XYZ”并没有改变，仅仅是将names[1]的引用从指向”XYZ”改成了指向”cat”，其结果是字符串”XYZ”再也无法通过names[1]访问到了。

       相当于引用嵌套引用

    8. 遍历数组

       1. 方法1

          1 2 3 4

          for (int i=0; i<ns.length; i++) { int n = ns[i]; System.out.println(n); }

       2. 方法2: for each 循环

          1 2 3 4

          int[] ns = { 1, 4, 9, 16, 25 }; for (int n : ns) { System.out.println(n); }

          变量n直接拿到ns数组的元素，而不是索引。
          
          若想直接打印ns，可以这么做：System.out.println(Arrays.toString(ns));

    9. 排序数组

       1. 冒泡排序

       2. Java的标准库已经内置了排序功能: Arrays.sort()，例如：

          1 2 3 4 5 6 7 8 9 10 11 12 13

          import java.util.Arrays; public class Main { public static void main(String[] args) { int[] ns = { 28, 12, 89, 73, 65, 18, 96, 50, 8, 36 }; // 排序前: System.out.println(Arrays.toString(ns)); // 排序 Arrays.sort(ns); // 排序后： System.out.println(Arrays.toString(ns)); } }

          1. 当我们调用Arrays.sort(ns);后，变量ns指向的数组内容已经被改变了
          2. 如果对一个字符串数组(String[] ns = { "banana", "apple", "pear" };)进行排序，原来的3字符串在内存中均没有任何变化，但是ns数组的每个元素指向变化了

    10. 多维数组

        1. 例子

           1 2 3 4 5 6 7 8 9 10 11

           public class Main { public static void main(String[] args) { int[][] ns = { { 1, 2, 3, 4 }, { 5, 6, 7 }, { 9, 10, 11, 12 } }; int[] arr1 = ns[1]; System.out.println(arr0.length); // 4 } }

           实际上arr1就获取了ns数组的第1个元素。因为ns数组的每个元素也是一个数组，因此，arr1指向的数组就是{ 5, 6, 7 }

        2. 遍历

           1 2 3 4 5 6 7

           for (int[] arr : ns) { for (int n : arr) { System.out.print(n); System.out.print(', '); } System.out.println(); }

        3. 小结

           • 二维数组就是数组的数组，三维数组就是二维数组的数组；
           • 多维数组的每个数组元素长度都不要求相同；
           • 打印多维数组可以使用Arrays.deepToString()；
           • 最常见的多维数组是二维数组，访问二维数组的一个元素使用array[row][col]

19. 命令行参数

    Java程序的入口是main方法，而main方法可以接受一个命令行参数，它是一个String[]数组。
    
    这个命令行参数由JVM接收用户输入并传给main方法：

    1 2 3 4 5 6 7

    public class Main { public static void main(String[] args) { for (String arg : args) { System.out.println(arg); } } }

    我们可以利用接收到的命令行参数，根据不同的参数执行不同的代码。例如，实现一个-version参数，打印程序版本号：

    1 2 3 4 5 6 7 8 9 10

    public static void main(String[] args) { for (String arg : args) { System.out.println(arg); if ("-version".equals(arg)) { System.out.println("v 1.0"); } else if ("-test".equals(arg)) { System.out.println("test"); } } }

    上面这个程序必须在命令行执行，我们先编译它： javac Main.java
    
    然后，执行的时候，给它传递一个-version参数：java Main -version -version -test

20. I/O

    1. 输出

       1. 输出语句
          • System.out.println()
          • System.out.printf()
       2. 占位符

          占位符	说明
          %d	格式化输出整数
          %x	格式化输出十六进制整数
          %f	格式化输出浮点数
          %e	格式化输出科学计数法表示的浮点数
          %s	格式化字符串

          注意，由于%表示占位符，因此，连续两个%%表示一个%字符本身。

       占位符本身还可以有更详细的格式化参数。下面的例子把一个整数格式化成十六进制，并用0补足8位：

    2. 输入

       1. import语句导入java.util.Scanner，import是导入某个类的语句，必须放到Java源代码的开头
       2. 创建 Scanner 对象并传入 System.in。System.out 代表标准输出流，而System.in代表标准输入流。直接使用System.in读取用户输入虽然是可以的，但需要更复杂的代码，而通过Scanner就可以简化后续的代码。
       3. Scanner对象后，要读取用户输入的字符串，使用scanner.nextLine()，要读取用户输入的整数，使用scanner.nextInt()。Scanner会自动转换数据类型，因此不必手动转换。
          例如：

       1 2 3 4 5 6 7 8 9 10 11 12

       import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 创建Scanner对象 System.out.print("Input your name: "); // 打印提示 String name = scanner.nextLine(); // 读取一行输入并获取字符串 System.out.print("Input your age: "); // 打印提示 int age = scanner.nextInt(); // 读取一行输入并获取整数 System.out.printf("Hi, %s, you are %d\n", name, age); // 格式化输出 } }

    3. 使用占位符构建字符串，并打印

       1 2	String <name> = String.format("%-10d%d", 20, 25) System.out.println(<name>)