算法笔记（C++）

• 算法笔记
• • STL
  • • vector
    • set
    • string
    • map
    • algorithm头文件下的常用函数
    • • max()、min()和abs()
      • swap()
      • reverse()
      • next_permutation()
      • fill()
      • sort()
      • lower_bound()和upper_bound()
  • 排序
  • • 1、选择排序(简单选择排序)
    • 2、插入排序(直接插入排序)
    • 3、冒泡排序
    • 4、希尔排序
    • 5、快速排序
    • 6、归并排序(2-路归并)
    • 7、基数排序
    • 8、堆排序
    • 9、计数排序
    • 10、自带的排序函数
  • 散列/哈希(hash)
  • • 常用的构造哈希函数的方法
    • • 1、进制哈希
  • 递归
  • • 分治
    • 递归
    • 回溯法
  • 贪心
  • • 简单贪心
    • 区间贪心
  • 二分
  • • 二分查找(折半查找)
    • 二分查找改进
    • • 插值查找
    • 快速幂(二分幂)
  • 双指针
  • • 快慢指针
    • 对撞指针
  • 递推
  • 随机选择算法
  • 数论
  • • 1、简单数学
    • 2、最大公约数与最小公倍数
    • 3、分数
    • 4、质数
    • • **素数筛法**
      • 质因子分解
    • 5、大整数(高精度)
  • 树
  • • 二叉树
    • 二叉树的存储结构
    • 二叉树的基本操作
    • • 1、二叉树的创建
      • 2、结点的查找、修改和删除
      • 3、结点的插入(新增)
    • 二叉树的遍历
    • • 先序遍历
      • 中序遍历
      • 后序遍历
      • 层序遍历

语言：C++

C++中为使用者提供了标准模板库( Standard Template Library, STL)，在其中封装了很多功能。

STL都需要在命名空间std中

vector是变长数组，可以多维（套娃），需要头文件#include

（1）定义vector

vector<类型名> 变长数组名;

例子

vector a;
vector< vector > b;//最好加上空格，否则会被编译器看做移位符
vector array[100];//array数组的每个元素都是一个double型的vector

（2）元素访问

• 下标访问

vector a;
int temp=a[2];//下标范围是0~a.size()-1，和数组一样

• 迭代器访问

迭代器(iterator)类似于指针，即类似于数组名当指针用的时候。

vector<类型名>::iterator it;//定义了一个叫做it的迭代器，尚未初始化

例子

vector a;
vector::iterator it=a.begin();//获取a的首地址
for(i=0;i

因此，a[i]和*(a.begin()+i)等价，

在常用STL容器中，只有vector和string才允许使用a.begin()+i这种迭代器加上整数，即*(it+i)的写法。

（3）常用函数

vector a;

a.size();//获得元素个数，返回unsigned类型（对%d而言无所谓）
a.begin();//取首地址
a.end();//取末尾元素的下一个地址，美国人思维习惯左闭右开

a.push_back(x);//在vector变量a的末尾添加一个元素x
a.pop_back();//在vector变量a的末尾删除一个元素
a.clear();//清空a中的所有元素

a.insert(it,x);//向a的迭代器it处插入一个元素x
//比如：a中原先是 1 2 3 4
a.insert(a.begin()+2,99);//将99插入到a[2]的位置，结果是3 4往后移，变为 1 2 99 3 4

a.erase(it);//删除a的迭代器为it处的元素
a.erase(left,right);//删除区间[left,right)内的所有元素
a.erase(a.begin(),a.end());//删除a中的所有元素，当然直接用clear就好

set是集合，是内部自动有序且自动去除重复元素的容器，需要头文件#include

如果需要处理不唯一的数据，可以用multiset

（1）定义set（同vector）

set<类型名> 集合名;

例子

set a;
set< vector > b;//最好加上空格，否则会被编译器看做移位符
set array[100];//array数组的每个元素都是一个double型的set

（2）元素访问

只能通过迭代器访问。

set<类型名>::iterator it;
cout<<*it;

由于只有vector和string才允许使用a.begin()+i这种迭代器加上整数，即*(it+i)的写法，set只能通过如下方法

set a;
for(set::iterator it=a.begin;it!=a.end();it++){
    printf("%d ",*it);
}

（3）常用函数

inserterasebeginendsizeclear等//用法同vector
a.find(value);//返回a中对应值为value的迭代器

string需要头文件#include，注意string.h和string是不一样的头文件

如果需要处理不唯一的数据，可以用multiset

（1）定义string

stirng str;
stirng str="hello";

（2）输入输出

只能cin和cout

cin>>str;
cout< 
或者将string转换为字符数组，就可以用printf输出了
 
printf("%s",str.c_str());
 
（3）元素访问
 
下标访问
迭代器访问
 
//通过下标访问
char ch=str[1];//ch的值是e
//通过迭代器访问（insert和erase这些函数需要用迭代器作为参数）
用法同vector
 
（4）常用操作
 
str3 = str1 + str2; //将 strl和str2拼接，赋值给str3
str1 += str2; //将str2直接拼接到str1上
两个sring类型可以直接使用==、!=、<、<=、>、>=比较大小，比较规则是字典序
str.lenth()或str.size();//返回字符串长度
str.substr(pos,len);//返回从下标pos开始，长度为len的子串
str1.find(str2);//当str2是str1的子串时，返回其在str1中第一次出现的位置。失配时返回值为string::npos
str1.find(str2，pos);//当str2是str1的子串时，从下标pos开始检索，返回其在str1中第一次出现的位置。失配时返回值为string::npos
str.replace(pos, len, str2)把str从pos号位开始、长度为len的子串替换为str2。
str.replace(it1, it2, str2);把str的迭代器[it1, it2)范围的子串替换为str2。
inserteraseclear等用法同vector
 
map 
map是映射，可以将任何数据类型（包括STL容器）映射到任何数据类型（包括STL容器）。可以理解为一个通用的哈希表，由键值对(key->value)组成。
 
map内部会按照键key自动从小到大排序
 
在定义数组时其实就是将int型映射到其他数据类型的映射。
 
需要一个键对应多个值，用multimap；unordered_map不会自动排序，速度比map快很多
 
double arr[10];//int型数组其实就是int型到double型的映射
a[1]=3.14;//将1映射到4
 
（1）定义map
 
map map名;
 
例子
 
map mp;//如果是字符串到int的映射，必须用string不能用char，char不能做键值value
 
（2）元素访问
 
下标(key)访问（键key是惟一的）
 
map a;
a['c']=20;
a['c']=50;//20被50覆盖
cout<
 
迭代器访问
 
迭代器(iterator)类似于指针，即类似于数组名当指针用的时候。
 
map::iterator it;//定义了一个叫做it的迭代器，尚未初始化
 
例子
 
map a;
map::iterator it=a.begin();
cout<< it->first;//输出it指向的元素的key
cout<< it->second;//输出it指向的元素的value
 
（3）常用函数
 
map a;

a.find(key);//返回键为key的元素的迭代器
a.erase(it);//删除迭代器it指向的元素
a.erase(key);//删除键为key的元素
a.erase(left,right);//删除迭代器区间[left,right)的所有元素
a.size();//返回元素个数
a.clear();//清空所有元素

 
algorithm头文件下的常用函数 
max()、min()和abs() 
分别返回最大值、最小值和绝对值
max(x,max(y,z));//获得x,y,z的最大值
abs(x);//x必须是整数，如果x是浮点型需要使用math头文件中的fabs()
 
swap() 
swap(x,y);//交换x,y的值
 
reverse() 
reverse(it1, it2)可以将数组指针在[it1, it2)之间的元素或容器的迭代器在[it1, it2)范围内的元素进行反转。示例如下：
 
#include 
#include 
#include 
using namespace std;
int main()
{
    //将a[0]~a[3]反转
    int a[10] = {10, 11, 12, 13, 14, 15};
    reverse(a, a + 4);
    printf("将a[0]~a[3]反转:n");
    for (int i = 0; i < 6; i++)
        printf("%d ", a[i]);
    //将str[2]~str[5]反转
    string str = "abcdefghi";
    reverse(str.begin() + 2, str.begin() + 6);
    printf("n将str[2]~str[5]反转:n");
    for (int i = 0; i < str.length(); i++)
        printf("%c ", str[i]);
    return 0;
}
//运行结果
将a[0]~a[3]反转:
13 12 11 10 14 15
将str[2]~str[5]反转：
a b f e d c g h i
 
next_permutation() 
next_permutation()给出一个序列在全排列中的下一个序列。
 
例如，当n=3时的全排列为
123
132
213.
231
312
32 1
这样231的下一个序列就是312。
 
示例：
 
#include 
#include 
using namespace std;
int main()
{
    int a[3] = {1, 2, 3};// a[0]~a[2]之间的序列需要求解next_ permutation
    do//使用do while可以输出第一个1 2 3
    {
        printf("%d %d %dn", a[0], a[1], a[2]);
    } while (next_permutation(a, a + 3));
    return 0;
}
//运行结果
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
 
fill() 
fill()可以把数组或容器中的某一段区间赋为某个相同的值。和memset不同，这里的赋值可以是数组类型对应范围中的任意值。示例如下：
 
#include 
#include 
using namespace std;
int main()
{
    int a[5] = {1, 2, 3, 4, 5};
    fill(a, a + 5, 100); //将a[0]~a[4]均赋值为100
    for (int i = 0; i < 5; i++)
        printf("%d ", a[i]);
    return 0;
}
//运行结果
100 100 100 100 100
 
sort() 
sort是用来排序的函数，它根据具体情形使用不同的排序方法，效率较高。不推荐使用C语言中的qsort函数，原因是qsort用起来比较烦琐，涉及很多指针的操作。而且sort在实现中规避了经典快速排序中可能出现的会导致实际复杂度退化到
    
     
      
       
        O
       
       
        (
       
       
        
         n
        
        
         2
        
       
       
        )
       
      
      
       O(n^2)
      
     
    O(n2)的极端情况。
 
sort()不写比较函数，默认升序排序。
 
格式：
 
sort(首元素地址(必填),尾元素地址的下一个地址(必填),比较函数(非必填));
bool cmp(char a,char b){//比较函数
    return a>b;//按照a>b的顺序排练
}
//进阶写法
bool cmp(node a,node y){//先按x降序的顺序排，如果x相等则按照y升序的顺序排
    if(a.x!=b.x) return a.x>b.x;
    else return a.y
 
**在STL中，只有vector、 string、 deque 是可以使用sort的。**这是因为像set、map这种容器是用红黑树实现的(了解即可)，元素本身有序，故不允许使用sort排序。
 
#include 
#include 
#include 
using namespace std;
bool cmp(int a, int b)
{ //因为vector中的元素为int型，因此仍然是int的比较
    return a > b;
}
int main()
{
    vector vi;
    vi.push_back(3);
    vi.push_back(1);
    vi.push_back(2);
    printf("排序前：n");
    for (int i = 0; i < 3; i++)
        printf("%d", vi[i]);
    sort(vi.begin(), vi.end(), cmp); //对整个vector排序
    printf("n排序后：n");
    for (int i = 0; i < 3; i++)
        printf("%d", vi[i]);
    return 0;
}
//运行结果
排序前：
312 
排序后： 
321
 
lower_bound()和upper_bound() 
lower_bound()和upper_bound()需要用在一个有序数组或容器中。
 
lower_bound(first, last, val)用来寻找在数组或容器的[first, last)范围内第1个值大于等于val的元素的位置，如果是数组，则返回该位置的指针；如果是容器，则返回该位置的迭代器。
upper_bound(first, last, val)用来寻找在数组或容器的[first, last)范围内第1个值大于val的元素的位置，如果是数组， 则返回该位置的指针；如果是容器，则返回该位置的迭代器。
显然，如果数组或容器中没有需要寻找的元素，则lower_bound()和upper_bound()均返回可以插入该元素的位置的指针或迭代器(即假设存在该元素时，该元素应当在的位置)。
 
排序 
十大经典排序算法：冒泡排序、快速排序、插入排序、希尔排序、归并排序、选择排序、堆排序、基数排序、桶排序
 
O(1)的空间复杂度是指算法消耗的空间不随数据规模的增大而增大。
 
时间复杂度中 
    
     
      
       
        l
       
       
        o
       
       
        g
       
      
      
       log
      
     
    log 都指 
    
     
      
       
        l
       
       
        o
       
       
        
         g
        
        
         2
        
       
      
      
       log_2
      
     
    log2​
 
一般OJ系统一秒能承受的运算次数是 
    
     
      
       
        1
       
       
        
         0
        
        
         7
        
       
       
        −
       
       
        1
       
       
        
         0
        
        
         8
        
       
      
      
       10^7-10^8
      
     
    107−108
 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-v2XJTYY6-1657774124409)(assets/量级.jpg)]
 
排序算法
平均时间
最差时间
稳定性
空间复杂度
备注
冒泡排序
O(n2)
O(n2)
稳定
O(1)
n较小时好
交换排序
O(n2)
O(n2)
不稳定
O(1)
n较小时好
选择排序
O(n2)
O(n2)
不稳定
O(1)
n较小时好
插入排序
O(n2)
O(n2)
稳定
O(1)
大部分已有序时好
基数排序
O(logRB)
O(logRB)
稳定
O(n)
B是真数(0~9),R是基数(个十百)
希尔排序
O(nlogn)
O(ns)(1
不稳定
O(1)
s是所选分组
快速排序
O(nlogn)
O(n2)
不稳定
O(logn)
n较大时好
归并排序
O(nlogn)
O(nlogn)
稳定
O(1)
n较大时好
堆排序
O(nlogn)
O(nlogn)
不稳定
O(1)
n较大时好
选择排序快于冒泡（80000个数据，选择排序用了2s，冒泡用了20s）
 
1、选择排序(简单选择排序) 
将待排序序列划分为2个序列，已排序序列[1,i-1]和未排序序列[i,n]。
 
对一个序列A中的元素A[1] ~ A[n]，令i从1到n枚举，进行n趟操作，每趟从待排序部分[i, n]中选择最小的元素，令其与待排序部分的第一个元素A[i]进行交换，这样元素A[i]就会与当前有序区间[1, i-1]形成新的有序区间[1,i]。于是在n趟操作后，所有元素就会是有序的。
 
总共n趟交换，每趟要从i到n比较
时间复杂度O(n2)
 
#include 
using namespace std;
void selectSort(int a[], int n)
{ //传入数组和数组长度
    int i, j, k, temp = 0;
    for (i = 0; i < n-1; i++) //下标从0开始，最后一个元素(即未排序区间只剩下一个元素)无需排序
    {                      
        k = i;              //记录第一个元素作为初始min值
        for (j = i + 1; j < n; j++)
        { //每趟中要遍历未排序区间[i+1~n-1]找出最小的
            if (a[j] < a[i])
            {
                k = j; //记录当前查找到的最小元素(更新min值)
            }
        }
        //每趟中的交换(当i==k时，即第一个元素本来就是最小的，那就不用交换了，其实不做这个if判断也用不了多少时间)
        if (i != k)
        {
            temp = a[i];
            a[i] = a[k];
            a[k] = temp;
        }
    }
}
int main()
{
    int a[20] = {0}, i, n;
    cin >> n;
    for (i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    selectSort(a, n);
    for (i = 0; i < n; i++)
    {
        cout << " " << a[i];
    }
    return 0;
}
 
2、插入排序(直接插入排序) 
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
 
核心思想：将待插入元素一个个插入已有序序列中的过程。
 
将待排序序列划分为2个序列，已排序序列[1,i-1]和未排序序列[i,n]。
 
对序列A的n个元素A[1]~A[n]，假定第一个元素已经有序，所以令从2到n枚举，进行n-1趟操作。那么某一趟时， 序列A的前i-1个元素A[1]~ A[i- 1]已经有序，而范围[i, n]还未有序。第i趟需要将第i个元素排好序（即每趟从未排序序列中选第1个元素插入到有序序列中），那么该趟从范围[1,i- 1]中寻找某个位置j，使得将A[i]插入位置j后（此时A[j]~A[i-1]会后移-位至A[j+ 1]~A[i])，范围[1, i]有序。
 
一般从已排序序列从后往前遍历比较来确定插入位置。（这是为了解决如果待插入的元素与有序序列中的某个元素相等的情况——将待插入元素插入到相等元素的后面）
 
元素的移动是通过赋值来实现的
 
总共n-1趟插入
时间复杂度O(n2)
 
注意，函数中的temp变量不能省略(不能用a[i]代替)，原因未知
 
#include 
using namespace std;
void insertSort(int a[], int len)
{ //传入数组和数组长度
    int i, j, temp = 0;
    for (i = 1; i < len; i++)
    {                                              //总共len-1趟排序(从第2个元素起查找插入位置)
        temp = a[i];                               // temp保存一份未排序序列第1个元素的值
        for (j = i; j >= 1 && temp < a[j - 1]; j--) // temp< a[j - 1]就说明还没有找到插入位置，j>=1是因为如果temp正好是有序序列最小的元素，那么就会被插入到最前面，这时j=0,j-1就是负数了
        {                                          //对i~n的未排序序列的第1个元素在1~i-1的有序序列中查找插入位置(从后往前找)
            //如果发现temp小于插入位置的前一个元素，那么这个元素后一个位置就是插入位置
            a[j] = a[j - 1]; //将a[j-1]后移一位至a[j]
        }
        if (j != i)
            a[j] = temp; //将temp值(未排序序列第1个元素的值)插入a[j]的位置
    }
}
int main()
{
    int a[20] = {0}, i, n;
    cin >> n;
    for (i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    insertSort(a, n);
    for (i = 0; i < n; i++)
    {
        cout << " " << a[i];
    }
    return 0;
}
 
3、冒泡排序 
算法步骤
 
比较相邻的元素。如果第一个比第二个大（逆序），就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
一共进行了数组元素个数-1轮外层循环，且每轮外层循环中需要比较的元素越来越少。
优化：如果某轮外层循环，一次交换都没有发生，则证明已经有序，无需后续比较。
 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ADVIwzhK-1657774124410)(assets/冒泡排序.png)]
 
时间复杂度O(n2)
 
设len为待排序数组长
 
比较len-1轮
第i轮比较j次，j=len-1-i（即少比较末尾那i个已经有序的数）
 
#include 
using namespace std;
int arr[] = {2, 9, -1, 10, 20};
int len = 0;
int sum = 0; //比较的轮次
int bubleSort(int arr[], int len)
{
    int i, j, temp = 0;
    bool flag = true; //优化冒泡排序算法，如果某轮没有发生比较，那么说明数组已经有序
    for (i = 0; i < len - 1; i++)
    { //下标从0开始
        if (flag == false)
            break;
        else
            flag = false; //每轮都把flag置为false
        sum++;
        for (j = 0; j < len - 1 - i; j++)
        {
            if (arr[j] < arr[j + 1])
            { //这里降序排序
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
            }
        }
    }
    return sum;
}
int main()
{
    int len = sizeof(arr) / sizeof(arr[0]); //求数组长度
    int ans = bubleSort(arr, len);
    for (int i = 0; i < len; i++)
    {
        cout << arr[i] << " ";
    }
    cout << "n";
    cout << "Total rounds:" << sum;
    return 0;
}
 
4、希尔排序 
改进后的插入排序
 
核心思想：让元素最快地接近他们排好序后应该处在的位置。
 
将序列按照增量gap分成若干元素间有固定间隔的子序列，用直接插入排序算法对子序列排序，并循环此过程（增量要每次减小），当增量减少到1时，整个序列被分为1组，排序后算法结束。
 
开始时，gap取值较大，子序列中的元素较少，排序速度快，克服了直接插入排序的缺点；其次，gap值逐渐变小后，虽然子序列的元素逐渐变多，但大多元素已基本有序，所以继承了直接插入排序的优点，能以近线性的速度排好序。
 
算法步骤
 
选择一个增量序列t1（一般是数组长度/2），t2（一般是一个分组长度/2），……，tk，其中 ti > tj, tk = 1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
 
特点
 
一次移动，移动位置较大，跳跃式地接近排序后的最终位置
最后一次排序，元素间只需要少量移动
增量序列必须是递减的，且最后一次的增量必须是1
增量序列应该是彼此互质的一些数
不适合在链式结构上实现（毕竟有步长这个东西）
 
代码直接在插入排序的基础上改的，只改动了一丁点（真的是一丁点）
 
//采取二分的h
#include 
using namespace std;
void shellSort(int a[], int len)
{ //传入数组和数组长度
    int i, j, temp = 0,h=len/2;//h是步长
    while(h>=1){//h=1时是最后一次插入排序
        for (i = 1; i < len; i++)
        {                                               //总共len-1趟排序(从第2个元素起查找插入位置)
            temp = a[i];                                // temp保存一份未排序序列第1个元素的值
            for (j = i; j >= h && temp < a[j - h]; j-=h) // temp< a[j - h]就说明还没有找到插入位置，j>=h是因为如果temp正好是有序序列最小的元素，那么就会被插入到最前面，这时j=0,j-h就是负数了（for中第一条j=i不能写成j=i+1，因为j往前比较是靠减去下标，+1后就凑不到最前面了）
            {                                           //对i~n的未排序序列的第1个元素在1~i-1的有序序列中查找插入位置(从后往前找)
                //如果发现temp小于插入位置的前一个元素，那么这个元素后一个位置就是插入位置
                a[j] = a[j - h]; //将a[j-h]后移h位至a[j]
            }
            if (j != i)
                a[j] = temp; //将temp值(未排序序列第1个元素的值)插入a[j]的位置
        }
        h /= 2;//每次插入排序结束后，减小步长
    }
}
int main()
{
    int a[20] = {0}, i, n;
    cin >> n;
    for (i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    shellSort(a, n);
    for (i = 0; i < n; i++)
    {
        cout << " " << a[i];
    }
    return 0;
}
 
//采取knuth序列（h=h*3+1，即1 4 13...），比二分法好
void shellSort(int a[], int len)
{ //传入数组和数组长度
    int i, j, temp = 0;
    int h = 1; // h是步长
    int t = len / 3;
    while (h < t)
    { //先求出最大的h(因为h是递减序列)
        h = h * 3 + 1;
    }
    while (h >= 1)
    { // h=1时是最后一次插入排序
        for (i = 1; i < len; i++)
        {                                                  //总共len-1趟排序(从第2个元素起查找插入位置)
            temp = a[i];                                   // temp保存一份未排序序列第1个元素的值
            for (j = i; j >= h && temp < a[j - h]; j -= h) // temp< a[j - h]就说明还没有找到插入位置，j>=h是因为如果temp正好是有序序列最小的元素，那么就会被插入到最前面，这时j=0,j-h就是负数了
            {                                              //对i~n的未排序序列的第1个元素在1~i-1的有序序列中查找插入位置(从后往前找)
                //如果发现temp小于插入位置的前一个元素，那么这个元素后一个位置就是插入位置
                a[j] = a[j - h]; //将a[j-h]后移h位至a[j]
            }
            if (j != i)
                a[j] = temp; //将temp值(未排序序列第1个元素的值)插入a[j]的位置
        }
        h /= 3; //每次插入排序结束后，减小步长
    }
}
 
5、快速排序 
核心思想：找中位数作为枢轴(pivot)/基准，给其找正确索引位置，使之成为数列的中位数的过程。
 
每次取出第1个元素作为“中位数”（这个数相当于从数组中暂时剔除了，它的位置可以随便赋值覆盖，表示交换数据的第1步），然后在该轮寻找它的正确索引位置（low和high相撞的位置），并把中位数的值赋到该位置上（表示交换数据的第2步）。
 
中位数为什么打了引号——因为这个中位数并不是真正的中位数，只不过和中位数一样都是左边的数都更小，右边的数都更大
 
算法步骤
 
从数列中挑出一个元素，称为 “基准”（pivot）;
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
 
只能用于顺序存储的结构和双链表
 
//一般做法
#include 
#include 
using namespace std;
const int MAXN = 20;
int a[MAXN] = {0};
void quickSort(int a[], int left, int right)
{
    int l = left, r = right; //左闭右闭的区间
    int pivot = a[l];//令左边第1个元素为枢轴
    if(l>=r)//递归边界(注意l在递归式的while循环中跳出时，l已经大于r，所以>=号不能改成==号)
        return;
    while(ll&& a[r]>=pivot) //从右边找比枢轴小的
            r--;//前移r
        a[l] = a[r];//跳出循环说明找到了r位置比l位置元素小的，就赋值覆盖
        while (l < r && a[l] <= pivot) //从右边找比枢轴大的
            l++;//后移l
        a[r] = a[l]; //跳出循环说明找到了l位置比r位置元素大的，就赋值覆盖
    }
    //此时跳出循环，l==r，把中位数(枢轴)赋值回去即可
    a[l] = pivot;
    //递归左右两个分区,因为每次是以左边的第1个数为基数，所以右边分区递归需要在pivot的右侧开始
    quickSort(a,left,r-1);//左侧序列递归(左闭右闭)
    quickSort(a,r+1,right);//右侧序列递归(左闭右闭)
}
int main()
{
    srand((unsigned int)time(NULL));
    int i, n;
    // cin >> n;
    for (i = 0; i < MAXN; i++)
    {
        a[i] = rand() % 50;
    }
    for (i = 0; i < MAXN; i++)
    {
        cout << " " << a[i];
    }
    cout << "n";
    quickSort(a, 0, MAXN-1);
    for (i = 0; i < MAXN; i++)
    {
        cout << " " << a[i];
    }
    return 0;
}
 
//一种以中间为基准的方法
#include
using namespace std;
int n,a[1000001];
void qsort(int l,int r)//应用二分思想
{
    int mid=a[(l+r)/2];//中间数
    int i=l,j=r;//左闭右闭的区间
    do{
        while(a[i]mid) j--;//查找右半部分比中间数小的数
        if(i<=j)//如果有一组不满足排序条件（左小右大）的数
        {
            swap(a[i],a[j]);//交换
            i++;
            j--;
        }
    }while(i<=j);//这里注意要有=
    if(l>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    qsort(1,n);
    for(int i=1;i<=n;i++) cout<
 
//使之适用于单链表

 
6、归并排序(2-路归并) 
核心思想：分治思想
 
“分”之后，“治”时，假定传入2个已排序序列
 
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并序列temp，并移动指针到下一位置
重复上一步 直到某一指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列temp末尾
 
#include 
#include 
using namespace std;
const int MAXN = 10;
int a[MAXN] = {0};
void mergeSort(int arr[], int left, int right, int temp[]);
void combine(int arr[], int left, int mid, int right, int temp[]);
int main()
{
    srand((unsigned int)time(NULL));
    int i;
    int *temp = (int *)malloc(sizeof(int) * MAXN);
    for (i = 0; i < MAXN; i++)
    {
        a[i] = rand() % 50;
    }
    for (i = 0; i < MAXN; i++)
    {
        cout << " " << a[i];
    }
    cout << "n";
    mergeSort(a, 0, MAXN-1, temp);
    for (i = 0; i < MAXN; i++)
    {
        cout << " " << a[i];
    }
    return 0;
}
//归并排序的主函数（分割操作体现在递归中）
void mergeSort(int arr[], int left, int right, int temp[]) //升序排序
{
    //递归边界(分割——到达——递归边界——返回——合并)
    if (left >= right)
        return;
    int mid = left + (right - left) / 2; //(left+right)/2的另一种写法，采取这种写法可以防止在right超过int类型的一半时，left+right导致溢出int型数据范围
    //分割
    mergeSort(arr, left, mid, temp);
    mergeSort(arr, mid + 1, right, temp);
    //合并
    combine(arr, left, mid, right, temp);
}
//归并排序中的合并操作
void combine(int arr[], int left, int mid, int right, int temp[])
{
    // 1.拆成arrL[low~mid]和arrR[mid+1~high]2个子序列(注意是左闭右闭)
    int i = left;                  // arrL数组的左端点
    int j = mid + 1;               // arrR数组的右端点
    int k = left;                  // temp数组的下标哨兵
    while (i <= mid && j <= right) // 2.分成的2个子序列都边比较边拷贝
    {
        //数字小的拷贝到temp数组中
        if (arr[i] <= arr[j]) //对arrL子序列
        {
            temp[k] = arr[i];
            k++;
            i++;
        }
        else //对arrR子序列
        {
            temp[k] = arr[j];
            k++;
            j++;
        }
    }
    while (i <= mid) // 3.对还有剩余元素的子序列把剩余元素拷贝到temp数组
    {
        temp[k] = arr[i];
        k++;
        i++;
    }
    while (j <= right) // 3.对还有剩余元素的子序列把剩余元素拷贝到temp数组
    {
        temp[k] = arr[j];
        k++;
        j++;
    }
    // 4.别忘了把temp数组中添加的k个元素拷贝到arr数组中
    for (i = left; i <= right; i++) //注意是左闭右闭区间
        arr[i] = temp[i];
    return;
}
 
7、基数排序 
基本思想：将整数按位切割为单个数字，然后按位分别比较。
 
将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后从最低位开始依次进行排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
 
特点：
 
空间换时间
仅支持正整数
数列中最大的数有几位，就要进行几轮排序
 
算法步骤
 
获得待排序数列中最大数的位数num（JAVA可以通过包装类将最大数变为String类型，再求得它的长度即可。C/C++还是直接打擂台算法吧）
从最低位（个位）开始排序到最高位（最大数的位数num），共num轮排序
每轮排序按照该轮对应比较的位上的数字，将数字放入桶中，入桶有先后顺序
每轮入桶完毕后，再按照该位上的数字从0到9的顺序从桶中取出数据存入原来的待排序数组，完成一轮排序
循环此过程，直到num轮排序完成。
 
改进
 
每次桶取完数据后本来是要置0的，也就是说桶中没有数据我们是用0表示的。但是这样导致无法对一位数0排序。但是可以用-1表示桶中没有数据，这样可以对0排序。(当然0肯定是最小的，不这么做，最后一步合并把0插入最前面也可以)
 
void radixSort(int arr[], int len)
{
    int i, j, k, index, pos, max = 0, num = 0;
    // 0.找出数列中最大元素的值，求出它有几位
    for (i = 0; i < len; i++)
    {
        if (max < arr[i])
            max = arr[i];
    }
    while (max > 0)
    {
        max /= 10;
        num++;
    }
    int maxlen = pow(10, num);
    int bucket[10][len]; // 10是指0~9共10个数，len是每个桶在数列是极端情况——常数列时的容量
    memset(bucket, 0, sizeof(bucket));
    // 1.每轮把数组中的数放入对应的桶
    for (k = 10; k <= maxlen; k *= 10) //从最低位(个位)排到最高位
    {
        for (i = 0; i < len; i++) //每轮遍历arr数组
        {
            pos = (arr[i] % k) / (k / 10); //求出对应的位上的数字pos (k/10相当于k少一位数字)
            j = 0;
            while (bucket[pos][j] != 0)
                j++;
            //将数字放到对应的桶的最后一个位置
            bucket[pos][j] = arr[i];
        }
        index = 0; //重置下标index
        // 2.每轮从桶中取出数
        for (i = 0; i < 10; i++) // 10个桶
        {
            for (j = 0; j < len; j++) // i号桶的内部
            {
                if (bucket[i][j] != 0) //桶中有数字才需要取
                {
                    arr[index] = bucket[i][j];
                    index++;
                    bucket[i][j] = 0; //记得把桶置零
                }
                else break; //找完最后一个位置，以后的就全是0，没必要找了
            }
        }
    }
}
 
8、堆排序 
9、计数排序 
算法思想：创建一个长度为待排序数组arr中最大元素值+1的临时计数数组temp。遍历arr数组中的元素，按照元素的值将temp数组中下标为该元素的值的元素值计数+1（如arr[2]=5，那么就temp[5]++;）当遍历完arr数组后，按下标从小到大的顺序输出temp数组中的下标，下标个数为它指向的数组元素值。（如arr中有3个5，那么temp[5]=3，于是输出时5输出3次），得到的结果即为排序好的数列。
 
void countSort(int arr[], int len)
{
    int i, j, k = 0, max = 0, maxSize;
    for (i = 0; i < len; i++)
        if (max < arr[i])
            max = arr[i];
    maxSize = max + 1; //临时计数数组的长度由待排序数组中最大元素决定
    int temp[maxSize];
    memset(temp, 0, sizeof(temp));
    // 1.将待排序数组中的元素在temp临时计数数组中计数
    for (i = 0; i < len; i++)
        temp[arr[i]]++;
    // 2.将temp临时计数数组中的数据按频数取出
    for (i = 0; i < maxSize; i++)
        for (j = 0; j < temp[i] & temp[i] != -1; j++) //有计数就取出
            arr[k++] = i;
}
 
10、自带的排序函数 
C语言：qsort函数
C++：sort函数，时间复杂度n*log2(n)、nth_element
 
以sort为例：C++ sort()排序详解_AC-fun的博客-CSDN博客_c++ sort
 
sort()函数可以对给定区间所有元素进行排序。它有三个参数sort(begin, end, cmp)，其中begin为指向待sort()的数组的第一个元素的指针，end为指向待sort()的数组的最后一个元素的下一个位置的指针，cmp参数为排序准则，cmp参数可以不写，如果不写的话，默认从小到大进行排序。
 
在 STL 里有一个神奇的函数 nth_element。
 
它的用法是 nth_element(a+x,a+x+y,a+x+len);。
 
执行之后数组 aa 下标 xx 到 x+y-1x+y−1 的元素都小于 a[x+y]a[x+y]，下标 x+y+1x+y+1 到 x+len-1x+len−1 的元素 都大于 a[x+y]a[x+y]，但不保证数组有序。此时 a[x+y]a[x+y] 就是数组区间 xx 到 x+len-1x+len−1 中第 yy 小的数，当然也可以自己定义 cmpcmp 函数。
 
结论：差不多就是将我们的思路 2 做了一遍。
 
nth_element 的时间复杂度是 O(n)O(n) 的，不过 STL 常数普遍较大……但还是能过此题。
 
散列/哈希(hash) 
 
 
问题：查询某数是否输入或某数的出现次数。
 
 
方案：空间换时间。使用大数组，初始化为0，输入某数，数组对应下标的元素++，实现计数。该方法受限于数组长度和输入数据类型，如果输入的数太大，而数组开不了那么大或者输入的数是字符串，则无法直接作为数组下标。可以通过散列(hash)将这些元素转化为整数。
 
 
哈希(hash)：通过哈希函数将某元素转化为整数，使得该整数能唯一代表这个元素。
 
一般可以用STL标准模板库种的map来直接使用哈希表的功能。（C++11以后可以用unordered_map，速度更快）
 
常用的构造哈希函数的方法 
1、进制哈希 
进制哈希的核心便是给出一个固定进制base，将一个串的每一个元素看做一个进制位上的数字，所以这个串就可以看做一个base进制的数，那么这个数就是这个串的哈希值；则我们通过比对每个串的的哈希值，即可判断两个串是否相同
 
注意：进制转换时建议不要把任意字符对应到数字0。比如假如把a对应到数字0，那么将不能只从Hash结果上区分ab和b（虽然可以额外判断字符串长度，但不把任意字符对应到数字0更加省事且没有任何副作用），一般而言，把a-z对应到数字1-26比较合适。又比如本题字符串是大小写字母(共26*2个)+数字(共10个)的组合，因此需要转成26*2+10=62进制。对于这个62进制，建议是1~62，而不是0~61，因为假设有字符串ab和b，那么包含数字0的将无法分辨。
 
代码示例：
 
typedef unsigned long long ULL;
ULL hashFunc(char a[])
{
    ULL len = strlen(a);
    ULL id = 0, i;
    for (i = 0; i < len; i++)
    {
        if (a[i] >= 'A' && a[i] <= 'Z')
        {
            id = id * 62 + (a[i] - 64) + 26; // 11~36(共26个数字)
        }
        else if (a[i] >= 'a' && a[i] <= 'z')
        {
            id = id * 62 + (a[i] - 96) + 26 * 2; // 37~62(共26个数字)}
        }
        else
        {
            id = id * 62 + (a[i] - 47); // 1~10(共10个数字)
        }
    }
    id %= MOD;
    return id;
}
 
递归 
分治 
分治(Divide and Conquer)：全称分而治之，将原问题分解为若干个规模小而结构与原问题相似的子问题，然后逐个击破，最后合并问题的解。
 
分治的思想：
 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FLybdMyN-1657774124411)(assets/分治思想.png)]
 
步骤：
 
分解（分治法分解出的子问题必须是相互独立的，如果子问题间存在交叉，说明没有分干净，还不能用分治解决）
解决
合并
 
例子：求解斐波那契数列F(n)通过递归分解为求解F(n-1)和F(n-2)的问题
 
递归 
递归的核心：反复调用自身，但是每次调用都把问题范围缩小，直到范围缩小到能直接得到边界数据的结果，然后再沿路返回求出解。
 
两个概念：
 
递归边界：跳出递归的条件。（例如斐波那契数列递归边界是F(0)==1和F(1)==1）
通项公式（递归式）：包含函数自身的通项公式，每次调用能减小问题范围。（例如斐波那契数列通项公式是F(n)=F(n-1)+F(n-2)）
 
 
 
我自己在刚开始解决递归问题的时候，总是会去纠结这一层函数做了什么，它调用自身后的下一层函数又做了什么…然后就会觉得实现一个递归解法十分复杂，根本就无从下手。
 
 
相信很多初学者和我一样，这是一个思维误区，一定要走出来。既然递归是一个反复调用自身的过程，这就说明它每一级的功能都是一样的，因此我们只需要关注一级递归的解决过程即可。
 
 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QRCtBTNV-1657774124412)(assets/递归误区.png)]
 
 
写递归时问自己三个问题：
 
 
递归的终止条件是什么
每次递归要做什么
每次递归要返回什么
 
 
具体例题和解题步骤详见：递归解题三部曲
 
 
回溯法 
到达递归边界前的某层时，由于某些条件/推理导致其实不需要继续递归了，于是可以直接返回上一层
 
回溯有点像栈
 
N皇后问题
 
算法思想
 
逐行放置皇后，对n行，每行放置一个皇后。因此，n个皇后的行不会相同。（规定第n个皇后放在第n行）
但是，列可能相同，或者放置的皇后会出现在之前放置好的皇后的对角线上。
所以，放置皇后时，对每一行，遍历每一列，判断该位置是否和先前放置好的皇后位置冲突，若不冲突，放置皇后。
 
#include 
#include 
using namespace std;
int n;                       //皇后个数
int x[1000];                 //摆放方案
int sum = 0;                 //方案总数
bool canPlace(int queen_pos) //判断能否放入该位置，即是否和现有的皇后位置冲突，若不冲突，表示可以放置
{
    for (int i = 1; i < queen_pos; i++)
    { //逐个逐个和现有已经摆好的皇后比较
        if (x[i] == x[queen_pos] || abs(queen_pos - i) == abs(x[queen_pos] - x[i]))
        {                 //列相等或在对角线上
            return false; //冲突返回false
        }
    }
    return true; //不冲突返回true
}
void placeQueen(int queen_pos)
{                      //第queen_pos个皇后，即第queen_pos行
    if (queen_pos > n) //递归边界，n个皇后已经处理完了
    {
        for (int i = 1; i <= n; i++)
        {
            cout << x[i] << " ";
        }
        sum++;
        cout << "n";
        return; //在回溯阶段，这个return直接跳到第35行，由于下面没有语句了，所以直接跳到main函数了
    }
    else
    {
        for (int i = 1; i <= n; i++) //这个for循环会执行n次，从而每一列都能寻找方案，因此能找到所有方案
        {                            //从棋盘第1列到第n列，逐列尝试
            x[queen_pos] = i;        //先把第queen_pos+1个皇后放在第queen_pos行第i列（注意x数组是全局的）
            if (canPlace(queen_pos))
            {                              //如果第queen_pos个皇后的位置和之前摆放好的皇后位置（通过x全局数组，canPlace函数可以知道放置的列坐标）不冲突
                placeQueen(queen_pos + 1); //在现有基础上继续摆queen_pos + 1个皇后
            }
            //如果冲突的话，i就++了，x[queen_pos] = i;这句又把皇后摆到了i+1列
        }
    }
}
int main()
{
    cin >> n;
    placeQueen(1); //这里queen_pos从1开始，即范围是1~n
    cout << "Total number of methods:" << sum;
    return 0;
}
 
8
1 5 8 6 3 7 2 4 
1 6 8 3 7 4 2 5 
1 7 4 6 8 2 5 3 
1 7 5 8 2 4 6 3 
2 4 6 8 3 1 7 5 
2 5 7 1 3 8 6 4 
2 5 7 4 1 8 6 3 
2 6 1 7 4 8 3 5
2 6 8 3 1 4 7 5
2 7 3 6 8 5 1 4
2 7 5 8 1 4 6 3
2 8 6 1 3 5 7 4
3 1 7 5 8 2 4 6 
3 5 2 8 1 7 4 6
3 5 2 8 6 4 7 1
3 5 7 1 4 2 8 6
3 5 8 4 1 7 2 6
3 6 2 5 8 1 7 4
3 6 2 7 1 4 8 5
3 6 2 7 5 1 8 4
3 6 4 1 8 5 7 2
3 6 4 2 8 5 7 1
3 6 8 1 4 7 5 2
3 6 8 1 5 7 2 4
3 6 8 2 4 1 7 5
3 7 2 8 5 1 4 6
3 7 2 8 6 4 1 5
3 8 4 7 1 6 2 5 
4 1 5 8 2 7 3 6
4 1 5 8 6 3 7 2
4 2 5 8 6 1 3 7
4 2 7 3 6 8 1 5
4 2 7 3 6 8 5 1
4 2 7 5 1 8 6 3
4 2 8 5 7 1 3 6
4 2 8 6 1 3 5 7
4 6 1 5 2 8 3 7
4 6 8 2 7 1 3 5
4 6 8 3 1 7 5 2
4 7 1 8 5 2 6 3
4 7 3 8 2 5 1 6
4 7 5 2 6 1 3 8
4 7 5 3 1 6 8 2
4 8 1 3 6 2 7 5
4 8 1 5 7 2 6 3
4 8 5 3 1 7 2 6 
5 1 4 6 8 2 7 3
5 1 8 4 2 7 3 6
5 1 8 6 3 7 2 4
5 2 4 6 8 3 1 7
5 2 4 7 3 8 6 1
5 2 6 1 7 4 8 3
5 2 8 1 4 7 3 6
5 3 1 6 8 2 4 7
5 3 1 7 2 8 6 4
5 3 8 4 7 1 6 2
5 7 1 3 8 6 4 2
5 7 1 4 2 8 6 3
5 7 2 4 8 1 3 6
5 7 2 6 3 1 4 8
5 7 2 6 3 1 8 4
5 7 4 1 3 8 6 2
5 8 4 1 3 6 2 7
5 8 4 1 7 2 6 3 
6 1 5 2 8 3 7 4
6 2 7 1 3 5 8 4
6 2 7 1 4 8 5 3
6 3 1 7 5 8 2 4
6 3 1 8 4 2 7 5
6 3 1 8 5 2 4 7
6 3 5 7 1 4 2 8
6 3 5 8 1 4 2 7
6 3 7 2 4 8 1 5
6 3 7 2 8 5 1 4
6 3 7 4 1 8 2 5
6 4 1 5 8 2 7 3
6 4 2 8 5 7 1 3
6 4 7 1 3 5 2 8
6 4 7 1 8 2 5 3
6 8 2 4 1 7 5 3
7 1 3 8 6 4 2 5
7 2 4 1 8 5 3 6 
7 2 6 3 1 4 8 5
7 3 1 6 8 5 2 4
7 3 8 2 5 1 6 4
7 4 2 5 8 1 3 6
7 4 2 8 6 1 3 5
7 5 3 1 6 8 2 4
8 2 4 1 7 5 3 6
8 2 5 3 1 7 4 6
8 3 1 6 2 5 7 4
8 4 1 3 6 2 7 5
Total number of methods:92
 
从运行结果也可以看出算法的步骤，即对于每一个皇后，都把当前位置的所有解法全部求出，再把该皇后往下移一个位置
 
贪心 
思想：选择每一阶段的局部最优，从而达到全局最优。
 
证明思路：
 
法一（不常用）：反证法和数学归纳法。（假设策略不能得到最优解，然后推导得出矛盾，以此证明策略是最优的，再用数学归纳法保证全局最优）
法二：举反例。如果找不到反例，就认为是贪心。
 
不能通过套路看出是不是贪心，所以只能手推模拟一遍，如果模拟可行，就可试下贪心；不行，则可能是动态规划
 
简单贪心 
最常规的贪心，直接想到的就是简单贪心。
 
区间贪心 
贪心策略：在一定的顺序下，每次选取最小的区间
 
具体分析：问题的关键在于起始边界。最开始选取的区间端点一定是**最终结果（选出的不相交区间序列）**的最外围的区间端点，因为最外围的区间一定有一部分与其他任何区间有重叠，而限定在最终结果是为了保证这个区间最终选上了。因此排序的规则是按照左端点从小到大排或者按照右端点从大到小排【即排成一个梯形的形状】。
 
如果出现区间包含，那么必然选更小的那个区间
如果出现区间部分重合，说明两区间的必有一个包含了另一个的一个端点。那么按照排序顺序，继续寻找（题目要求选不相交的）
如果出现区间不相交，那么必选（毕竟已经排好序了），选择后将记录右端点的变量值更新为选中的区间的右端点
 
把每一段区间按照右端点进行排序，然后开始依次遍历，res代表答案，ed是本区间的右端点，如果存在下一个区间的左端点大于本区间的右端点，那么证明这两个区间内没有交集，就让res ++;，然后把ed更新成下一个区间的右端点。
 
代码：
 
#include 
#include 
using namespace std;
const int MAXN = 100 + 10;
struct INTERVAL
{
    int l, r;
} I[MAXN];
bool cmp(INTERVAL a, INTERVAL b)
{
    if (a.r != b.r)
        return a.r > b.r;
    else
        return a.l < b.l;
}
int main()
{
    int i, sum = 1, n;
    cout << "Please input the number of Interval:n";
    cin >> n;
    for (i = 0; i < n; i++)
    {
        cout << "Please input the Interval:n";
        cin >> I[i].l >> I[i].r;
    }
    // 1. 按照右端点从大到小，左端点从小到大的顺序排序
    sort(I, I + n, cmp);
    // 2. 确定边界（这里采用右边界）
    int lastR = I[0].r;
    // 3. 从右端边界开始，往左寻找，如果找到不相交的(当前左端点<=lastR右端点)就选中(更新lastR,sum++)
    for (i = 1; i < n; i++)
    { //直接从第2个开始就行，第1个已经作为边界了
        if (I[i].r <= lastR)
        { //这里没有用<是因为题目提供的都是开区间
            lastR = I[i].l;
            sum++;
        }
    }
    cout << sum;
    return 0;
}
 
二分 
二分查找(折半查找) 
进行二分查找的数组必须为有序数组（且顺序方向和mid是+1还是-1有关）
 
以下以递增序列为例：
 
设置一个指向中间元素下标的变量mid，mid=(left + right)/2
让要查找的元素和数组mid下标的元素进行比较 
  
如果查找的元素大于arr[mid]，则left变为mid后面一个元素的下标，即left=mid+1
如果查找的元素小于arr[mid]，则right变为mid前一个元素的下标，即left=mid-1
如果查找的元素等于arr[mid]，则mid就是要查找元素所在的位置，可以返回位置跳出循环（跳出的时机1）
 
当left = rigtht时，还没有找到该元素，说明元素不在该数组中
当left > right时，求mid的循环应该跳出（跳出的时机2）
 
时间复杂度：
    
     
      
       
        O
       
       
        (
       
       
        l
       
       
        o
       
       
        g
       
       
        n
       
       
        )
       
      
      
       O(logn)
      
     
    O(logn)
 
二分查找的过程与序列的下标从0开始还是从1开始无关
 
求mid的写法：mid = left + (right - left) / 2;
 
这是(left+right)/2的另一种写法，采取这种写法可以防止在right超过int类型的一半时，left+right导致溢出int型数据范围
 
（1）这种写法在数列中有多个相同元素时，只能找到其中的一个
 
//循环写法
int binarySearch(int x, int arr[], int left, int right) //左闭右闭区间
{
    if(xarr[MAXN]) return-1;//因为数组有序，所以特判一下
    int mid;
    while (left <= right)
    {
        mid = left + (right - left) / 2;
        // if (arr[mid] != x && left == right)
        //     return -1;
        if (arr[mid] == x)
            return mid;
        else if (arr[mid] < x)
            left = mid + 1;
        else if (arr[mid] > x)
            right = mid - 1;
    }
    return -1;
}
 
//递归写法
int binarySearch(int x, int arr[], int left, int right) //左闭右闭区间
{
    int mid = left + (right - left) / 2;
    if (left > right)
        return -1;
    if (arr[mid] == x)
        return mid;
    else if (arr[mid] < x)
        return binarySearch(x, arr, mid + 1, right);
    else
        return binarySearch(x, arr, left, mid - 1);
}
 
（2）针对（1）的局限性，做出改进
 
问题：求出序列中第一个等于x的元素的位置L以及第一个大于x的元素的位置R，这样元素x在序列中的存在区间就是左闭右开区间[L,R)
 
例如：{1,3,3,3,6}，找3，返回[1,4)；找5，返回[5,5)。即如果寻找序列中不存在的元素x，那么[L,R)应当理解为假设序列中存在x的话，x应该处于的位置
 
于是问题分解为：
 
 
查找第一个等于x的元素的位置，步骤如下（以递增序列为例）：
 
因为是递增序列，所以当mid正好指向一串x的中间时，应该往左侧找，而arr[mid]大于x也应该往左找，因此>和=放在一起
 
  
如果arr[mid] >= x，说明第一个等于x的元素在mid处或mid的左侧，令right=mid，查找区间应当变为[left,mid]
如果arr[mid] < x ，说明第一个等于x的元素在mid的右侧，令left=mid+1，查找区间应当变为[mid+1,right]
注意传入参数中的上下界 
    
之前是[0,len-1]，是因为查找的区间是左闭右闭区间
现在是[0,len]，是因为当查找的数不存在且大于所有数时，应该放在最后，这个多出来的位置是让left==right用的
 
注意循环跳出的条件是left>=right。 
    
之前是left>right跳出，因为当left==right时是leftmidright三者重合，当left>right时是说明不存在该元素
现在是要求对于不存在的元素也查找其位置，所以当left==right时，只剩下左右边界夹出的那个位置，这个位置就是所求
 
 
 
查找第一个大于x的元素的位置
 
因为是递增序列，所以当mid正好指向一串x的中间时，应该往右侧找，而arr[mid]小于x也应该往右找，因此<和=放在一起
 
  
如果arr[mid] > x，说明第一个大于x的元素在mid的左侧，令right=mid，查找区间应当变为[left,mid]
如果arr[mid] <= x，说明第一个大于x的元素在mid处或mid的右侧，令left=mid+1，查找区间应当变为[mid+1,right]
 
 
int binarySearchLeft(int x, int arr[], int left, int right) //左闭右闭区间
{
    int mid;
    while (left < right) //这里条件是<号是因为假设了当x不存在时也要找出它如果在的话应该在的位置
    //所以当left==right时，这时确定出了唯一一个元素，这个位置就是我们所需要的
    {
        mid = left + (right - left) / 2;
        if (arr[mid] >= x)
            right = mid;
        else
            left = mid + 1;
    }
    return left;
}
int binarySearchRight(int x, int arr[], int left, int right) //左闭右闭区间
{
    int mid;
    while (left < right) //这里条件是<号是因为假设了当x不存在时也要找出它如果在的话应该在的位置
    //所以当left==right时，这时确定出了唯一一个元素，这个位置就是我们所需要的
    {
        mid = left + (right - left) / 2;
        if (arr[mid] <= x)
            left = mid + 1;
        else
            right = mid;
    }
    return right;
}
int binarySearch(int x, int arr[], int left, int right)
{
    int l = binarySearchLeft(x, arr, left, right);
    int r = binarySearchRight(x, arr, left, right);
    printf("%d is locate in[%d,%d)n", x, l, r);
}
 
一个用二分求解
    
     
      
       
        
         n
        
       
      
      
       sqrt{n}
      
     
    n
           ​，精度
    
     
      
       
        e
       
       
        p
       
       
        s
       
       
        =
       
       
        1
       
       
        e
       
       
        −
       
       
        5
       
      
      
       eps=1e-5
      
     
    eps=1e−5的例子：
 

    
     
      
       
        
         n
        
       
      
      
       sqrt{n}
      
     
    n
           ​可以看作是方程
    
     
      
       
        f
       
       
        (
       
       
        x
       
       
        )
       
       
        =
       
       
        
         x
        
        
         2
        
       
       
        =
       
       
        n
       
      
      
       f(x)=x^2=n
      
     
    f(x)=x2=n的解，因此mid便是x，只要求出满足精度
    
     
      
       
        e
       
       
        p
       
       
        s
       
       
        =
       
       
        r
       
       
        i
       
       
        g
       
       
        h
       
       
        t
       
       
        −
       
       
        l
       
       
        e
       
       
        f
       
       
        t
       
       
        <
       
       
        =
       
       
        1
       
       
        e
       
       
        −
       
       
        5
       
      
      
       eps=right-left<=1e-5
      
     
    eps=right−left<=1e−5的mid即可
 
double f(double x)
{
    return x * x;
}
double binarySolve(int n)
{
    double mid = 0, eps = 1e-5, right = 2, left = 1; //估一下上下界
    while (right - left > eps)
    {
        mid = (right + left) / 2;
        if (f(mid) < n)
            left = mid;
        else if (f(mid) > n)
            right = mid;
        else
            return mid;
    }
    return mid;
}
 
二分查找改进 
如果查找第一个或最后一个元素的值，这种情况下二分查找的查找效率是很低的。改进方法是插值查找。
 
插值查找 
插值查找与二分查找的区别是：插值查找使用了一种自适应算法，用这种算法来计算mid。
 
mid的值在两种查找算法中的求法：
 
 
二分查找：mid = (left + right)/2=left+(right-left)/2
 
 
插值查找：这个公式其实就是按比例的意思
 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HI9StFwm-1657774124413)(assets/插值查找mid系数公式.png)]
 
mid = left + (right - left) * (key - arr[left]) / (arr[right] - arr[left])
 
  
其中key为要查找的数的值
 
 
插值查找的局限
 
对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找, 速度较快
关键字分布不均匀的情况下，该方法不一定比折半查找要好
 
int insertValueSearch(int x,int arr[],int left, int right){
    int mid;
    while(left<=right){
        mid = left + (right - left) * (x - arr[left]) / (arr[right] - arr[left]);
        if(arr[mid]==x)
            return mid;
        else if(arr[mid] 
快速幂(二分幂) 
 
 
问题背景：给定3个正整数 
     
      
       
        
         a
        
        
         、
        
        
         b
        
        
         、
        
        
         m
        
        
         (
        
        
         a
        
        
         <
        
        
         1
        
        
         
          0
         
         
          9
         
        
        
         ,
        
        
         b
        
        
         <
        
        
         1
        
        
         
          0
         
         
          1
         
        
        
         8
        
        
         ,
        
        
         1
        
        
         <
        
        
         m
        
        
         <
        
        
         1
        
        
         
          0
         
         
          9
         
        
        
         )
        
       
       
        a、b、m (a<10^9,b<10^18,1 
 
采取暴力循环的话肯定大大超时，因此使用快速幂，这是基于二分的算法。
 
 
 
快速幂基于以下显然的事实：
 
 
如果 
      
       
        
         
          b
         
        
        
         b
        
       
      b 是奇数，那么有 
      
       
        
         
          
           a
          
          
           b
          
         
         
          =
         
         
          a
         
         
          ∗
         
         
          
           a
          
          
           
            b
           
           
            −
           
           
            1
           
          
         
        
        
         a^b=a*a^{b-1}
        
       
      ab=a∗ab−1
如果 
      
       
        
         
          b
         
        
        
         b
        
       
      b 是偶数，那么有 
      
       
        
         
          
           a
          
          
           b
          
         
         
          =
         
         
          
           a
          
          
           
            b
           
           
            /
           
           
            2
           
          
         
         
          ∗
         
         
          
           a
          
          
           
            b
           
           
            /
           
           
            2
           
          
         
        
        
         a^b=a^{b/2}*a^{b/2}
        
       
      ab=ab/2∗ab/2
如果 
      
       
        
         
          b
         
        
        
         b
        
       
      b 是奇数，那么 
      
       
        
         
          b
         
         
          −
         
         
          1
         
        
        
         b-1
        
       
      b−1 为偶数
0 是偶数
 
 
因此，b是偶数总可以在下一步转换成b是偶数的情况，b是偶数总可以在下一步转换为b/2的情况，这样用数字2将奇数和偶数联系起来，并最终转化为1，最后b可以变为0，此时 
     
      
       
        
         
          a
         
         
          b
         
        
        
         =
        
        
         1
        
       
       
        a^b=1
       
      
     ab=1 恒成立。
 
 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3hskTbs4-1657774124414)(assets/快速幂例子.png)]
 
 
 
快速幂目的：用递归或循环的方式将 
     
      
       
        
         
          a
         
         
          n
         
        
       
       
        a^n
       
      
     an 二分转化为 
     
      
       
        
         
          a
         
         
          
           n
          
          
           ÷
          
          
           2
          
         
        
        
         ×
        
        
         
          a
         
         
          
           n
          
          
           ÷
          
          
           2
          
         
        
       
       
        a^{ndiv 2}times a^{ndiv 2}
       
      
     an÷2×an÷2 ，从而将 
     
      
       
        
         O
        
        
         (
        
        
         n
        
        
         )
        
       
       
        O(n)
       
      
     O(n) 优化为 
     
      
       
        
         O
        
        
         (
        
        
         l
        
        
         o
        
        
         g
        
        
         n
        
        
         )
        
       
       
        O(logn)
       
      
     O(logn)。
 
 
于是有求 
    
     
      
       
        
         a
        
        
         b
        
       
       
        %
       
       
        m
       
      
      
       a^b%m
      
     
    ab%m 快速幂的递归写法，时间复杂度为 
    
     
      
       
        O
       
       
        (
       
       
        l
       
       
        o
       
       
        g
       
       
        b
       
       
        )
       
      
      
       O(logb)
      
     
    O(logb)
 
注意：
 
如果题目数据范围过大，不能在算出 
     
      
       
        
         
          a
         
         
          b
         
        
       
       
        a^b
       
      
     ab 后再取模，而是要步步取模
sum *= x % z; 的意思是：sum = sum * (x % z) 正确的取模方式是 sum = sum * x % z
 
#include 
using namespace std;
long long binaryPow(int a, int b, int m) //使用long long 一是为了防止结果装不下，二是为了防止两个int型相乘溢出int的范围
{
    if (b == 0) //递归边界
        return 1;
    else
    {
        if (b % 2 != 0) // b是奇数，需要转成偶数的情况(b=b-1，少的那个a再补乘回去)
            return a * binaryPow(a, b - 1, m) % m;
        else // b是偶数，需要转成b/2的情况
        {
            long long temp = binaryPow(a, b / 2, m);
            return temp * temp % m;//这步不能写成binaryPow(a, b / 2, m)*binaryPow(a, b / 2, m)%m;，因为这样执行时会两次递归，时间复杂度2的指数级飙升
        }
    }
}
int main()
{
    int a, b, m;
    cin >> a >> b >> m;
    cout << binaryPow(a, b, m);
    return 0;
}
 
同一个例子快速幂的迭代写法：
 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CiHH12UT-1657774124415)(assets快速幂迭代写法.png)]
 
#include 
using namespace std;
long long binaryPow(int a, int b, int m) //使用long long一是为了防止结果装不下，二是为了防止两个int型相乘溢出int的范围
{
    long long ans = 1; //用于累乘
    int i;
    while (b > 0)//分割b的二进制位
    {
        i = b & 1;//i为1时说明数位选中，累乘一下
        if(i==1){
            ans = ans * a % m;
        }
        a = a * a;//更新每位对应的a(a是累计的)
        b >>= 1;  //将b的二进制右移一位，即b=b>>1，也可以理解为b=b/2;
    }
    return ans;
}
int main()
{
    int a, b, m;
    cin >> a >> b >> m;
    cout << binaryPow(a, b, m);
    return 0;
}
 
建议参考博客：快速幂取模（a^b%mod）详细解析__Zebra的博客-CSDN博客
 
MOD求余运算法则：
 
结合律
((a+b) mod p + c)mod p = (a + (b+c) mod p) mod p
((ab) mod p * c)mod p = (a * (bc) mod p) mod p
交换律
(a + b) mod p = (b+a) mod p
(a × b) mod p = (b × a) mod p
分配律
((a +b)mod p × c) mod p = ((a × c) mod p + (b × c) mod p) mod p
(a×b) mod c=(a mod c * b mod c) mod c
(a+b) mod c=(a mod c+ b mod c) mod c
(a-b) mod c=(a mod c- b mod c) mod c
双指针 
双指针(Two Pointers)，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个**相同方向（快慢指针）或者相反方向（对撞指针）**的指针进行扫描，从而达到相应的目的。
 
双指针是充分使用了数组有序这一特征，从而在某些情况下能够简化一些运算。
 
快慢指针 
两个指针从同一侧开始遍历数组，将这两个指针分别定义为快指针（fast）和慢指针（slow），两个指针以不同的策略移动，直到两个指针的值相等（或其他特殊条件）为止，如fast每次增长2个，slow每次增长1个。
 
典型例子就是序列合并问题。详见《算法笔记》P139
 
对撞指针 
在有序数组中，将指向最左侧的索引定义为左指针(left)，最右侧的定义为右指针(right)，然后从两头向中间进行数组遍历。
 
 
 
对撞数组适用于有序数组，也就是说当你遇到题目给定有序数组时，应该第一时间想到用对撞指针解题。
 
 
典型例子就是快速排序和判断2数之和。详见《算法笔记》P139
 
递推 
递推：根据一些条件，后一位的结果可以由前一位或前若干位计算而来。
 
顺推
逆推
 
随机选择算法 
使用随机数选择下标，避免顺序查找在某些情况下的低效率。
 
数论 
1、简单数学 
问题难度通常不大，主要考察数理逻辑。
 
2、最大公约数与最小公倍数 
最大公约数(公因数)：自然数a和b的公因数中最大的那个。
 
用 
    
     
      
       
        g
       
       
        c
       
       
        d
       
       
        (
       
       
        a
       
       
        ,
       
       
        b
       
       
        )
       
      
      
       gcd(a, b)
      
     
    gcd(a,b) 来表示a和b的最大公约数。
 
求解最大公约数常用欧几里得算法(即辗转相除法)。
 
 
 
若a、b均为正整数，则 
     
      
       
        
         g
        
        
         c
        
        
         d
        
        
         (
        
        
         a
        
        
         ,
        
        
         b
        
        
         )
        
        
         =
        
        
         g
        
        
         c
        
        
         d
        
        
         (
        
        
         b
        
        
         ,
        
        
         a
        
        
         %
        
        
         b
        
        
         )
        
        
         ,
        
        
         a
        
        
         >
        
        
         b
        
       
       
        gcd(a, b) = gcd(b, a % b),a>b
       
      
     gcd(a,b)=gcd(b,a%b),a>b
 
 
0 和任意一个整数a的最大公约数都是a（注意不是0）
 
 
因此可以写出求最大公约数的辗转相除法递归算法：
 
递归式：gcd(a,b)=gcd(b, b%a);
递归边界：gcd(a,0)=a;
 
int gcd(int a,int b){
    if(a 
最小公倍数：自然数a和b的公倍数中最小的那个。
 
用 
    
     
      
       
        l
       
       
        c
       
       
        m
       
       
        (
       
       
        a
       
       
        ,
       
       
        b
       
       
        )
       
      
      
       lcm(a,b)
      
     
    lcm(a,b) 表示a和b的最小公倍数。
 
求解最小公倍数是在求出最大公约数的基础上进行。
 
 
 
若a、b均为正整数，则 
     
      
       
        
         l
        
        
         c
        
        
         m
        
        
         (
        
        
         a
        
        
         .
        
        
         b
        
        
         )
        
        
         =
        
        
         a
        
        
         ∗
        
        
         b
        
        
         /
        
        
         g
        
        
         c
        
        
         d
        
        
         (
        
        
         a
        
        
         ,
        
        
         b
        
        
         )
        
       
       
        lcm(a.b)=a*b/gcd(a,b)
       
      
     lcm(a.b)=a∗b/gcd(a,b)
 
 
由于a*b在计算机中计算可能溢出，所以采取等价写法 (a/gcd(a, b))*b
 
int lcm(int a,int b){
    if(a
        int temp=a;
        a=b;
        b=temp;
    }
    return (a/gcd(a, b))*b;
}
 
3、分数 
（1）分数的表示
 
采取假分数的形式，用结构体。
 
struct Fraction{
	int up,down;//分子分母
};
 
若分数为负，则令分子为负
若分数为0，则令分子为0，分母为1
分子分母没有除了1以外的公约数
 
（2）分数的化简
 
如果分母down为负数，那么令分子up和分母down都变为相反数
如果分子up为0，那么令分母down为1
约分：求出分子绝对值与分母绝对值的最大公约数d，然后令分子分母同时除以d
 
4、质数 
除了1和自身，没有其他因数。
 
1不是质数也不是合数。
 
bool isPrime(int n){
    if(n==1) return false;
    int temp=sqrt(n);
    for(int i=2;i<=temp;i++){
        if(n%i==0) return false;
    }
    return true;
}
 
素数筛法 
Eratosthenes(埃拉托色尼)筛法：简单粗暴的一种筛法，从小到大枚举所有数，每找到一个素数，就划去它的所有倍数（像筛子一样过滤掉了），没有被前面的步骤划去的数就是素数，同样也要划去它的所有倍数。事先只需要确定查询下边界的第一个素数，其他的素数都是划出来的。
 
详见《算法笔记》P162
 
质因子分解 
质因子分解：把正整数n写成一个或多个质数相乘的形式。
 
如 
    
     
      
       
        180
       
       
        =
       
       
        2
       
       
        ×
       
       
        2
       
       
        ×
       
       
        3
       
       
        ×
       
       
        3
       
       
        ×
       
       
        5
       
      
      
       180=2times2times3times3times5
      
     
    180=2×2×3×3×5 ，可也写成指数形式 
    
     
      
       
        180
       
       
        =
       
       
        
         2
        
        
         2
        
       
       
        ×
       
       
        
         3
        
        
         2
        
       
       
        ×
       
       
        
         5
        
        
         1
        
       
      
      
       180=2^2times3^2times5^1
      
     
    180=22×32×51
 
 
 
数字 1 没有质因子，因此往往需要特判。
 
 
可采取指数表示法存放质因子及其个数。因为前10个质因子的乘积 
    
     
      
       
        2
       
       
        ×
       
       
        3
       
       
        ×
       
       
        5
       
       
        ×
       
       
        7
       
       
        ×
       
       
        11
       
       
        ×
       
       
        13
       
       
        ×
       
       
        17
       
       
        ×
       
       
        19
       
       
        ×
       
       
        23
       
       
        ×
       
       
        29
       
       
        =
       
       
        6
       
       
        ,
       
       
        469
       
       
        ,
       
       
        693
       
       
        ,
       
       
        230
       
      
      
       2times3times5times7times11times13times17times19times23times29=6,469,693,230
      
     
    2×3×5×7×11×13×17×19×23×29=6,469,693,230 已经超过了int的范围，因此对于int型的数据，结构体数组只需要最多10个长度即可
 
struct Factor{
    int x,cnt;
}fac[10];
 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-F2yehHCi-1657774124416)(assets/质因子分解.png)]
 
 
 
最后指出，如果要求1个正整数N的因子个数，只需要对其质因子分解，得到各质因子 
     
      
       
        
         
          p
         
         
          i
         
        
       
       
        p_i
       
      
     pi​ 的个数分别为 
     
      
       
        
         
          e
         
         
          1
         
        
        
         ,
        
        
         
          e
         
         
          2
         
        
        
         ,
        
        
         .
        
        
         .
        
        
         .
        
        
         ,
        
        
         
          e
         
         
          k
         
        
       
       
        e_1,e_2,...,e_k
       
      
     e1​,e2​,...,ek​ ，于是N的因子个数就是 
     
      
       
        
         (
        
        
         
          e
         
         
          1
         
        
        
         +
        
        
         1
        
        
         )
        
        
         ×
        
        
         (
        
        
         
          e
         
         
          2
         
        
        
         +
        
        
         1
        
        
         )
        
        
         ×
        
        
         .
        
        
         .
        
        
         .
        
        
         ×
        
        
         (
        
        
         
          e
         
         
          k
         
        
        
         +
        
        
         1
        
        
         )
        
       
       
        (e_1+ 1)times(e_2+1)times...times(e_k+1)
       
      
     (e1​+1)×(e2​+1)×...×(ek​+1)
 
 
5、大整数(高精度) 
（1）大整数的存储
 
使用数组，整数的高位存储在数组的高位，整数的低位存储在数组的低位。
 
即：358，d[0]=8,d[1]=5,d[2]=3
 
为了方便随时获取大整数的长度，需要附带一个len变量存长度，于是使用结构体
 
struct bigInt{
    int d[1000];
    int len;
    //使用默认构造函数初始化
	bigInt(){
        memset(d,0,sizeof(d));
        len=0;
    }
};
 
（2）大整数的四则运算
 
树 
由于机考的原因，这里只简要说明一些必要的树的基本常识
 
 
空树：没有结点的清况
 
 
根结点：没有父节点的结点
 
 
结点的度：该结点的子树棵树
 
 
结点的深度：从根结点（深度为1）自顶向下算起
 
 
结点的高度)：从最底层叶子节点（高度为1）自顶向下逐层累加至该结点时的高度值
 
 
树的深度：该树中结点的最大深度
 
 
树的高度：该树中结点的最大高度
 
 
树的度/宽度：该树中结点的最大的度
 
 
树的层次：从根结点所在层（第1层）自顶向下算起
 
 
森林：多棵树组合在一起
 
 
  
亲缘关系
说明
A结点的孩子
A结点子树的根结点
B孩子的双亲
A结点（双亲是1个结点，不是2个）
兄弟
同一双亲的孩子之间互称兄弟
祖先
从根结点到该结点所经分支上的所有结点
子孙
以该结点为根结点的子树中的所有结点
 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-P9szpjTK-1657774124417)(assets/树的结构.png)]
 
一些通用的性质：
 
结点数=边数+1
满足连通、结点数=边数+1的结构一定是一棵树
叶子结点度=0（注意当树只有一个结点时，根结点同时也是叶子节点）
树的深度=树的高度，但是对于结点没有这个性质
 
二叉树 
二叉树定义：每个节点最多只能有两个子结点的树。
 
二叉树与度为2的树的的区别：二叉树的左右子树的有顺序的，而树的没有顺序。
 
附上递归定义，以便使用递归算法：
 
名称
定义
二叉树
二叉树要么没有结点，要么由根结点、左子树、右子树构成，且左右子树都是二叉树
二叉树的性质：
 
第 
     
      
       
        
         i
        
       
       
        i
       
      
     i 层上至多有 
     
      
       
        
         
          2
         
         
          
           i
          
          
           −
          
          
           1
          
         
        
       
       
        2^{i-1}
       
      
     2i−1 个结点 
     
      
       
        
         (
        
        
         i
        
        
         ≥
        
        
         1
        
        
         )
        
       
       
        (ige1)
       
      
     (i≥1)
深度为 
     
      
       
        
         k
        
       
       
        k
       
      
     k 的二叉树至多有 
     
      
       
        
         
          2
         
         
          k
         
        
        
         −
        
        
         1
        
       
       
        2^k-1
       
      
     2k−1 个结点 
     
      
       
        
         (
        
        
         k
        
        
         ≥
        
        
         1
        
        
         )
        
       
       
        (kge1)
       
      
     (k≥1)
叶子节点数=度为2的结点数+1
 
2种特殊的二叉树：
 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PtPtFDj2-1657774124418)(assets/完全二叉树和满二叉树的关系.png)]
 
满二叉树：每一层的结点都达到了该层能达到的最大结点数
完全二叉树：满二叉树在最底层从右往左依次连续地去掉几个结点得到的二叉树
 
二叉树的存储结构 
二叉树一般使用链表存储。链表结点结构如下：
 
左指针lchild
Data
右指针rchild
指针指向相应子树的根结点地址，如果子树不存在，则指向NULL（可用于结点初始化）
 
顺序存储结构：
 
对于完全二叉树，可以采取层序遍历的方式存储（不是完全二叉树不要用，不然会多出很多空结点，浪费空间），这样使用数组就行了。
 
 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-puBIRCY4-1657774124419)(assets/完全二叉树使用层序遍历存储.png)]
 
二叉树的基本操作 
1、二叉树的创建 
二叉树的创建其实就是插入一个个结点的过程。结点的数据可以存储在数组中，然后传入事先写好的insert()函数插入二叉树中，最终返回根结点指针root
 
当然也可以一边输入结点数据一边插入，这跟题目要求有关。
 
NODE* createTree(int data[],int n){//提供n个数据
    NODE* root=NULL;//新建并初始化根结点
    for(int i=0;i 
2、结点的查找、修改和删除 
先判断当前结点是否是需要查找的结点，如果是则终止递归
如果不是，则分别往该结点的左孩子和右孩子递归，直到当前结点为NULL为止递归结束
对于删除，由于二叉树是单链表构成，我们要判断当前结点的子结点是否是要删除的结点，而不是去判断当前这个结点是不是要删除的结点
 
int search(NODE* root,int x,int newData){
    if(root==NULL) return-1;
    if(root->data==x){
        root->data=newData;
    }
    searchAndEdit(root->lchild,x,newData);
    searchAndEdit(root->rchild,x,newData);
}
 
3、结点的插入(新增) 
二叉树结点的插入位置就是其数据域在二叉树中查找失败的位置（递归跳出条件）。
 
//根结点指针root要使用引用，否则插入不会成功
void insert(NODE* &root,int x){
    if(root==NULL){
        root=newNode(x);
        return;
    }
    if(由于某种条件，x应插在左子树中)//去左子树中找
        insert(root->lchild,x);
	else insert(root->rchild,x);//去右子树中找
}
 
在上述代码中，很关键的一点是根结点指针root使用了引用&。引用的作用即在函数中修改root会直接修改原变量。这么做的原因是，在insert函数中新建了结点，并把新结点的地址赋给了当层的root。如果不使用引用，root = newNode这个语句对root的修改就无法作用到原变量（即上一层的rootl->child与root->rchild）上去， 也就不能把新结点接到二叉树上面，因此insert函数必须加引用。
 那么为什么前面的search 函数不需要加引用呢?这是因为search函数中修改的是指针root指向的内容，而不是root本身，而对指针实现的结点内容的修改是不需要加引用的。
 那么，如何判断是否要加引用呢? 一般来说，如果函数中需要新建结点，即对二叉树的结构做出修改，就需要加引用；如果只是修改当前已有结点的内容，或仅仅是遍历树，就不用加引用。至于判断不出来的情况，不妨直接试下加引用和不加引用的区别再来选择。最后再特别提醒一句， 在新建结点之后，务必令新结点的左右指针域为NULL，表示这个新结点暂时没有左右子树。
 
二叉树的遍历 
这块如果搞不懂的话，仔细研究《算法笔记》，上面讲的很好。以下内容是总结。
 
先序遍历 
先遍历父结点，再遍历左子树，最后遍历右子树
 
先序遍历，就是在第一次经过这个结点的时候访问它。
 
性质：先序遍历序列的第1个一定是整棵二叉树的根结点。
 
void preOrder(NODE* root){
    if(root==NULL) return;
    printf("root=%dn", root->data);
    preOrder(root->lchild);
    preOrder(root->rchild);
}
 
 
 
先序遍历可以想象为，一个小人从一棵二叉树根节点为起点，沿着二叉树外沿，逆时针走一圈回到根节点，路上遇到的元素顺序，就是先序遍历的结果
 
 
先序遍历结果为：A B D H I E J C F K G
 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nRHpIiX6-1657774124419)(assets/先序遍历动图.gif)]
 
中序遍历 
先遍历左子树，再遍历父结点，最后遍历右子树
 
中序遍历，就是在第二次经过这个结点的时候访问它。
 
性质：中序遍历序列中，只要知道根结点，那么根结点左边的便是左子树，右边的便是右子树
 
void inOrder(NODE* root){
    if(root==NULL) return;
    inOrder(root->lchild);
    printf("root=%dn", root->data);
    inOrder(root->rchild);
}
 
 
 
中序遍历可以看成，二叉树每个节点，垂直方向投影下来（可以理解为每个节点从最左边开始垂直掉到地上），然后从左往右数，得出的结果便是中序遍历的结果
 
 
中遍历结果为：H D I B E J A F K C G
 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Wed8BQni-1657774124420)(assets/中序遍历动图.gif)]
 
后序遍历 
先遍历左子树，再遍历右子树，最后遍历父结点
 
后序遍历，就是在第三次经过这个结点的时候访问它。
 
性质：后序遍历序列的最后1个一定是整棵二叉树的根结点。
 
void postOrder(NODE* root){
    if(root==NULL) return;
    postOrder(root->lchild);
    postOrder(root->rchild);
    printf("root=%dn", root->data);
}
 
 
 
后序遍历就像是剪葡萄，我们要把一串葡萄剪成一颗一颗的。
 
 
就是围着树的外围绕一圈，如果发现一剪刀就能剪下的葡萄（必须是一颗葡萄）（也就是葡萄要一个一个掉下来，不能一口气掉超过1个这样），就把它剪下来，组成的就是后序遍历了。
 
 
后序遍历中，根节点默认最后面
 
后序遍历结果：H I D J E B K F G C A
 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6XRu2K0x-1657774124421)(assets/后序遍历动图.gif)]
 
总结：
 
无论是先序遍历还是后序遍历序列，都必须知道中序遍历序列才能唯一确定一棵树。
 
给定先序遍历序列和中序遍历序列，重建二叉树：
 
层序遍历 
按层次的顺序从根结点向下逐层遍历，同一层的结点从左到右遍历。
 
 
 
层次遍历很好理解，就是从根节点开始，一层一层，从上到下，每层从左到右，依次写值就可以了
 
 
层次遍历结果：A B C D E F
 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GbbxG8sC-1657774124422)(assets/层序遍历图.png)]
 
广搜步骤和代码见《算法笔记》P293
 
也可以用数组模拟队列写：
 
void LevelorderTraversal(NODE* root)
{
    if (root == NULL) //提交后最后一个测试点是空树
        return;
    NODE* arr[110] = {NULL};
    int rear = 0, front = 0;
    arr[rear++] = root; //从队尾入队
    while (front < rear)
    {
        if (arr[front]->Left)
            arr[rear++] = arr[front]->Left;
        if (arr[front]->Right)
            arr[rear++] = arr[front]->Right;
        printf(" %c", arr[front]->Data); //队首出队
        front++;
    }
}
 
遍历类型
实现方法
先序、中序、后序遍历
深搜(DFS)
层序遍历
广搜(BFS)
一张二叉树遍历的样例图：
 

                
                
                
        
        

  
    
      
        
      
      
        
          暑期编程PK赛
          
        
        得CSDN机械键盘等精美礼品！