注释：

1. 单行注释：//注释内容

(VS Code中，用鼠标选中ctrl+k+c注释，ctrl+k+u解除注释)

2. 多行注释：/*注

释

内

容 */

常量：

1. #define 宏常量 写在函数体外

2. const修饰的常量 const 数据类型 常量名=常量值

通常在变量定义前加关键字const，修饰该变量为常量，不可修改

写在函数体中

关键字

定义变量时，不要使用关键字

标识符命名规则

1. 不可以是关键字

2. 标识符只能由字母、数字、下划线组成

3. 标识符中字母区分大小写

4. 标识符中第一个字符只能是字母或下划线

数据类型

整型 

short 2字节 int 4字节 long 8字节

sizeof :数据类型所占内存大小

浮点型 float（4字节） double（8字节）

在数字后面加上f后，数字变成float型，如num=3.14f

科学计数法

float f2=3e2 //意思为3*10^2

float f2=3e-2 //意思为3*0.1^2

字符型

char 占用1个字节

创建字符型变量时，要用单引号

单引号中只能用1个字符

ASCII字符

转义字符：用于表示一些不能显示出来的ASCII字符

\n 换行

\t 水平制表 同\t前的字符共占用8个字符，作用是输出字符更整齐

\\ 代表一个反斜线字符’\’

字符串类型

1.char str[]=”hello world”;

char 字符串名 [];带双引号

2 string 变量名=“字符串值”

注意添加头文件#include<string>，也可添加#include<bits/stdc++.h>,其包含所有头文件

布尔类型 占用内存为1

true “1” 非0的值都代表真

false “0”

数据的输入

cin >> 要输入的变量;

cout << 输出内容;

运算符

除数不为0，则不可以做取模运算

两个小数不可以做取模运算

前置递增 先让变量+1，然后进行表达式运算 

后置递增 先让进行表达式运算，然后变量+1

赋值运算符

a=10; a+=2;  则a=a+2；a为12

比较运算符

>= 大于等于

比较时加括号，如（a==b），若a和b不相等，则其值为0

逻辑运算符

！非 真变假，假变真

&& 与，同时为真才为真，其余为假

|| 或，同时为假才为假，其余为假

其实就相当于有理数运算中的负负得正↓

!1 = 0 !0 = 1 0 && 1 = 0 1 && 1 = 1

程序流程结构

顺序

If语句

1. 单行if

2. 多行if

3. 多条件if

4. 嵌套if （三只小猪案例）

5. 三目运算符 表达式1？表达式2：表达式3

如果表达式1的值为真，执行表达式2，并返回表达式2的结果

三目运算符中如果返回的是变量，则可以继续赋值

6. switch语句

switch(表达式）

{

case结果1:执行语句;break;

case结果2:执行语句;break;

...

default:执行语句;break;

}

switch语句中表达式类型只能是整型或字符型

循环语句

while循环结构

while(执行条件)

{

执行语句；

}

//srand()和rand()函数在<bits/stdc++.h>文件

do while 循环结构

do

{

执行语句；

}

while(执行条件)

//do while和while的区别是do while会先执行一次循环语句

for循环结构

for(变量；执行条件；变量加加/减减)

{

执行语句；

}

嵌套循环（多层for循环）

for(变量；执行条件；变量加加/减减)

{

执行语句；

for(变量；执行条件；变量加加/减减)

{

执行语句；

或更多for循环

执行语句；

}

执行语句；

}

跳转语句

break 语句

使用时机：1.switch语句2.循环语句中，跳出当前新婚换3.嵌套语句中，跳出最近的内层循环语句

continue语句

退出本次循环中余下尚未执行的语句，直接进入下次循环

goto语句

无条件跳转语句，要设置标记，标记后添加：

数组

一维数组定义方式

1.数组类型 数组名[数组长度]

int arr[5];

arr[1]=20;

2.数组类型 数组名[数组长度]={值1，值2，值3.....}

在初始化时未全部赋值，用0填写

int arr2[5]={1,2,3,4,5};

3.数组类型 数组名[]={值1，值2...}

int arr3[]={1,2,3,4} 

数组名作用

//统计数组在内存中的长度

int arr[4]={1,2,3,4};

cout << "整个数组占用的内存空间为： " << sizeof(arr) <<endl;

cout << "每个元素占用内存为： " << sizeof(arr[0]) << endl; 

//确定数组名查看数组的首地址 

cout << "数组首地址： " << arr << endl;

cout << "数组第一个元素的地址为： " << &arr[0] << endl;

}

二维数组定义方式

1.数据类型 数组名[行数][列数];

int arr[2][3];

int arr[0][0]=1;//赋值 

2.数据类型 数组名[行数][列数]={{数据1，数据2}，{数据3，数据4}};

int arr[2][3]=

{

{1,2,3},

{4,5,6}

}; 

3.数据类型 数组名[行数][列数]={数据1，数据2，数据3，数据4};

int arr[2][3]={1,2,3,4,5,6};

4.数据类型 数组名[][列数]={数据1，数据2，数据3，数据4};

int arr[][3]={1,2,3,4,5,6};

二维数组名用途

1. 统计占用空间大小

2. 查看首地址

函数

函数定义语法

返回值类型 函数名（参数列表） {函数体语句 return 表达式}

int add(int num1,int num2)

{

int sum=num1+num2;

return sum;

}

如果函数不需要返回值时，可以不写return,声明写void

值传递

形参发生改变，实参不发生改变

即函数体内部数字发生改变，调用函数后数字未发生改变

函数常见样式

1.无参无返

void test1()

{

cout << "this is test1" << endl; 

} 

2.有参无返

void test2(int a)

{

cout << "this is test2 a=" << a << endl; 

}

3.无参有返

int test3()

{

cout << "this is test3" << endl;

return 1000; 

}

4.有参有返

int test4(int a)

{

a=a+100;

cout << "this is test4 b=" << a <<endl;

return a;

}

函数声明

提前高数编译器函数的存在，可以利用函数的声明

int max(int a,int b);//声明

函数的声明可以多次，但是函数的定义只能一次

函数的分文件编写

1. 创建.h后缀名的头文件

文件名为swap.h

#include<iostream>

using namespace std;

//函数的声明

void swap(int a,int b); 

2. 创建.cpp后缀名的源文件

#include "swap.h"

void swap(int a,int b)

{

int temp=a;

a=b;

b=temp;

cout << "a=" << a <<endl;

cout << "b=" << b <<endl;

}

3. 在头文件中写函数的声明

4. 在源文件中先函数的定义

创建一个test文件，在此文件中运行

#include<iostream>

using namespace std;

#include "swap.h"

int main()

{

int a=10;

int b=20;

swap(a,b);

}

指针

指针的定义和使用

指针的定义的语法：数据类型 * 指针变量名

int a=10;

int *p;

p=&a;

cout << "a的地址为：" << &a << endl;

cout << "p的地址为：" << p << endl; 

指针的使用

可以通过解引用的方式找到指针指向的内存

指针前加*代表解引用，找到指针指向的内存中的数据

//找到地址中的内容然后去修改所指地址的内容 

*p=1000; 

cout << "a为：" << a << endl;

cout << "*p为：" << *p << endl；

指针所占内存的空间

在32位系统中，指针占用4个字节大小

在64位系统中，指针占用8个字节大小

空指针

int *p=NULL;

指针变量指向内存中编号为0的空间

用处：初始化指针变量

注意：空指针指向的内存空间是不可以访问的（0-255）

野指针：

指向非法内存空间的变量

int *p=(int *)0x1100;

野指针和空指针用户均不可访问

const修饰指针三种情况：

1. const修饰指针。——常量指针

例：const int *p=&a; //常量指针，特点：指针的指向可以修改，但是指针指向的值不可以修改

2. const修饰常量。——指针常量

int * const p=&a;

特点：指针的指向不可以改，指针指向的值可以改

3. const既修饰指针，又修饰常量

const int * const p=&a;

特点：指针的指向不可以改，指针指向的值也不可以改

指针和数组

利用指针访问数组

int arr[]={1,2,3,4,5,6,7,8,9,10};

int *p=arr;

cout << "第一个元素为：" << arr[0] <<endl;

cout << "指针访问的第一个元素为：" << *p <<endl;

for(int i=0;i<10;i++)

{

cout << *p << " ";

p++; 

} 

指数和函数

地址传递：加上&，可以修饰实参

void swap(int *p1,int *p2)

{

int temp=*p1;

*p1=*p2;

*p2=temp;

}

int main()

{

int a=10;

int b=20;

swap(&a,&b);

cout << "a=" << a << endl;//a=20

cout << "b=" << b << endl;//b=10

}

结构体（用户自定义的数据类型）

结构体的定义和使用

struct 结构体名 {结构体成员列表名}；

例如：

//创建学生类型 

struct Student

{

string name;

int age;

int score;

 }; 

// 1.struct Student s1;

struct Student s1;

s1.name="小红" ;

s1.age=19;

s1.score=100;

//2.struct Student s2={...}//赋初值 

struct Student s2={"小明",24,99};

//3.在定义结构体时顺便创建结构体变量

struct Student

{

string name;

int age;

int score;

 }s3;

s3.name="小红" ;

s3.age=18;

s3.score=98;

结构体数组

 struct 结构名 数组名[元素个数]={ {},{},{},....{} }

1.//创建学生结构体类型 

struct Student

{

string name;

int age;

int score;

}; 

//2、创建数组结构体

struct Student stuarray[3]=

{

{"小红",21,99},

{"小兰",18,89},

{"小明",30,79}

}; 

//3.给结构体数组中的数值赋值

stuarray[2].name="张三";

stuarray[2].age=24;

stuarray[2].score=90;

//4.遍历输出

for(int i=0;i<3;i++)

{

cout << " 姓名：" << stuarray[i].name 

<< " 年龄："<< stuarray[i].age 

<< " 分数：" << stuarray[i].score <<endl;

} 

结构体指针

利用操作符->可以通过结构体指针访问结构体属性

struct Student

{

string name;

int age;

int score;

}; 

（struct） Student s={"小兰",34,79};

（struct） Student * p=&s;

cout <<" 名字："<<p->name<<" 年龄："<<p->age<<" 分数："<<p->score<<endl; 

结构体嵌套结构体

结构体中的成员可以是另一个结构体

//创建学生类型 

struct student

{

string name;

int age;

int score;

}; 

//创建教师类型

struct teacher

{

string name;

int age;

struct student stu;

};

//结构体嵌套结构体

teacher t;

t.name="老王";

t.age=46;

t.stu.name="jay";

t.stu.age=18;

结构体做函数参数

将结构体作为参数向函数中传递

传递方式：

值传递

地址传递 

//值传递 

void print1(struct student s)

{

s.name="jay";

cout<<"学生姓名："<<s.name <<" 年龄：" <<s.age <<" 分数：" <<s.score<<endl;

} 

Print1(s); 

//地址传递

void print2(struct student * p)

{

p->name="judy";

cout<<"学生姓名："<<p->name <<" 年龄：" <<p->age <<" 分数：" <<p->score<<endl;

}  

print2(&s);

结构体中const使用场景    

void print2( const struct student * p)

{

p->name="judy";//这句将会报错，因为该变量加入const，只读不可修改

cout<<"学生姓名："<<p->name <<" 年龄：" <<p->age <<" 分数：" <<p->score<<endl;

}  

print2(&s);

OK如果你已经看到这里，那么恭喜你C++的基础知识已经基本掌握了，下面进入

算法入门章节

模拟与高精度

模拟

自然界和日常生活中的有些事物，若用计算机很难建立起枚举、贪心等算法，甚至没法建立数学模型。我们解决这类问题可用模拟法。所谓模拟法，就是用计算机模拟某个过程，通过改变数学模型的各种参数，进而观察变更这些参数所引起的过程状态的变化，然后从中得出解答。

 

由于模拟法往往是从实际工程应用中提取出来的一些核心问题，或者本身就是某个工程的简化模型，所以解答模拟题特别需要有良好的理解能力、分析能力和规划能力。模拟题的算法一般都不太复杂，关键是所有条件都不能遗漏并要把条件分析清楚。求解模拟题一般都比较繁琐，编程前一定要预先规划好各个模块的功能和结构，以免具体编程时注意了局部而遗漏了某些重要的方面。解答模拟题通常的步骤是：

（1）认真仔细的读懂题目。模拟题的描述通常都比较详细，篇幅一般都比较长，应该边阅读边将有关的条件一条条地记录下来，阅读完成后要反复核对，绝对不能有错漏。

（2）建立各个条件之间的关系，最好用一些简明的表格列出。

（3）认真分析这些关系，并建立这些关系的数学模型。

（4）规划各个模块的结构，用相应的语言、逐步求精的方法描述具体的算法。

（5）编写程序，调试并运行。

（6）检查题目给出的样例能否通过。竞赛题目中一般都会给出输入输出样例，以便检查程序的输入输出格式是否正确，但这些样例往往会比竞赛时评判所用的测试数据简单，所以你不能满足于通过这些样例，还要尽量自拟一些更复杂、更全面的测试数据来检查程序的正确性。经过反复的调试、检查，才算完成该题。

原文地址：https://blog.csdn.net/qq_36257171/article/details/95651331

高精度

当我们利用计算机进行数值计算，有时候会遇到这样的问题： n！的精确结果是多少？

当n小于30的时候，我们当然可以通过电脑自带的计算器计算出来。但是当我们遇到 100! 的时候就没有办法直接计算出精确的结果。

这是由于计算机的特点是运算速度超级快，精确度高，因此利用计算机进行高精度的计算和处理是计算机的一个重要应用。所谓高精度运算，是指参与运算的数（加数，减数，因子……）范围大大超过了标准数据类型（整型，实型）能表示的范围的运算。

（注：①n!=1 * 2 * 3 * ……* (n-1) * n ，例如 5！=1 * 2 * 3* 4 * 5 = 120 ）

高精度处理，实际上就是模拟法，模拟手算，它的原理与我们用竖式计算时一样的，不过在处理过程中要注意高精度数据的读入、转换储存、数据的计算、结果位数的计算、输出等几个问题。

 

高精度计算中需要处理如下几个问题：

 

（1）数据的输入：

数据的输入，需要考虑输入的位数问题（可能上百上千位），也要考虑输入的数可能带字母（可能是16进制）等问题。所有我们选用字符串输入。

 

string s;

cin>>s;

 

若输入的数据可能有负数，就加上下面的语句，删掉第一个字符，记录负号。

 

if(s[0]==‘-’) 

{

s.erase(0,1);     //erase是字符串中的删除，s.erase(0,1)表示在0位置删除1个字符

fuhao=-1;

}

 

（2）数据的转换储存：

数据是通过字符串输入的，不能够直接进行计算，需要转换成数字。我们选用最基本的转换储存方式，字符串的一个字符对应数组中的一个元素，把字符串的数字全部转换到一个数组中，其中数组下标为1对应输入数的个位，数组下标为2的对应输入数的十位，以此类推。

 

int a[10002];         //建议放在全局变量,默认为0。也可以用 memset函数清0;

len=s.size();         //len表示输入的数据的位数

for(i=1;i<=len;i++)

a[i]=s[len-i]-48;     //将数串s转换为数组a,并倒序存储。

如果数据是16进制的，还需要补充一句：

if(a[i]>=10)a[i]=a[i]-7;

通过这样，我们就可以把输入的数据很好的放入数组当中了。

（3）数据的计算

①加法：

两大正整数相加，a数组=a数组+b数组（注：a[1]表示a数据的个位）

对应位置相加并加上低位的进位数。得到的新数字如果超过9，把个位留下，高位进上去。

 

x=0;

for(i=1;i<=10000;i++)     //最终结果不超过10000位的整数的加法

{

a[i]=a[i]+b[i]+x;

x=a[i]/10;

a[i]=a[i]%10;

}

 

②减法：

两大正整数相减，a数组=大a数组-小b数组

模拟普通的减法，从低位开始对应的减，不足就向高位借一。

 

for(i=1;i<=10000;i++)    //一万位以内的整数的减法

{

if(a[i]<b[i])

{

a[i]+=10;

a[i+1]--;

}

a[i]=a[i]-b[i];

}

 

③乘法

这里有2种方法：

 

1：

一大正整数乘以小正整数，a数组=a数组*k;

同加法类似，每一位都乘以k，再加上之前的进位，如果新得到的数字超过了10，哪么个位留下，高位进上去。

 

x=0;

for(i=1;i<=10000;i++) //最终结果不超过10000位

{

a[i]=a[i]*k+x;

x=a[i]/10;

a[i]=a[i]%10; 

 

两大正整数相乘，c数组=a数组*b数组

模拟普通乘法。

 

x=0;

for(i=1;i<=lena+1;i++)     //lena为a的数位

for(j=1;j<=lenb+1;j++)     //lenb为b的数位

{

c[i+j-1]=a[i]*b[j]+x+c[i+j-1]; 

x=c[i+j-1]/10;

c[i+j-1]=c[i+j-1]%10;

}

}

④除法

这里也有2种方法：

 

1：

大正整数除以小正整数，c数组=a数组÷b数

 

x=0;

for(i=1;i<=len;i++)      //a的数位

{

c[i]=(x*10+a[i])/b;

x=(x*10+a[i])%b;

}

 

2：两大正整数相除，c数组=a数组÷b数组

 

（4）结果位数的计算

 

len=10000; //取最高位

while(a[len]==0) 

len--;          //最高位为0时候就舍去

 

如果结果可能为0，就需要改成：

 

while(a[len]==0&&len>1) 

len--;

（5）结果的输出

 

for(i=len;i>=1;i--)

cout<<a[i];

排序

sort排序

注意：头文件 <algorithm>

用法：

sort(数组名称 + 起始下标 , 数组名称 + 结束下标 + 1);

可以说非常便捷。

冒泡排序：

已经讲过，在此不再多说。

桶排序：

桶排序思想：

桶排序工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间。但桶排序并不是比较排序O(n)，他不受到 下限的影响。

 

桶排序以下列程序进行：

 

设置一个定量的数组当作空桶子;

寻访序列，并且把数据一个一个放到对应的桶子去;

对每个不是空的桶子进行排序;

从不是空的桶子里把项目再放回原来的序列中。

如果：理论上来讲，桶的数量越多，时间复杂度就越低，当然空间复杂度就越高。而且和计数排序很相似，如果桶的数量是 max - min + 1，这个时候，桶排序和计数排序几乎就是一样的。

快速排序(快排)

快排的实现思想：

• 先从数列中取出一个数作为基准数(通常取第一个数)。
• 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
• 再对左右区间重复第二步，直到各区间只有一个数。

 

 

参考代码

#include <iostream>

using namespace std;

int A[1010101];

int n;

void bug(int l,int r)

{

int i,j,t,tamp;

tamp = A[l];

i = l;

j = r;

if(l >= r)return;

while(i != j)

{

while(A[j] >= tamp && i < j)

{

j--;

}

while(A[i] <= tamp && i < j)

{

i++;

}

if(i < j)

{

t = A[i];

A[i] = A[j];

A[j] = t;

}

}

A[l] = A[i];

A[i] = tamp;

bug(l,i - 1);

bug(i + 1,r);

}

int main()

{

cin >> n;

int i,j,t;

for(i = 1;i <= n;i++)

{

cin >> A[i];

}

bug(1,n);

for(i = 1;i <= n;i++)

{

cout << A[i] << " ";

}

return 0;

}

 

选择排序：

选择排序（O(n^2)、不稳定）

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置（或末尾位置），

直到全部待排序的数据元素排完。

选择排序不稳定的原因：

 

    选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，

    依次类推，直到第n-1个元素，第n个 元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，

    如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么 交换后稳定性就被破坏了。

    比较拗口，举个例子，序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被     破坏了，所以选择排序不是一个稳定的排序算法。

选择排序第一种写法：

int a[10] = { 3,5,1,7,2,4,6,9,8,0 };

//选择排序，从i开始往后找，找到一个最小的，将a[i]与其交换，即放到数组的第一个位置，然后i++，继续

//从i开始往后找最小的，找到后与a[i]交换，即放到数组的第二个位置，如此循环，直到i为最后一个元素的位置，则数组排好序

int min, i,j,t;

for (i = 0;i < 10 ;i++) {

min = i;

for (j = i;j < 10;j++) {

if (a[j] < a[min]) {

min = j;

}

}

if(j!=min){

t = a[min];

a[min] = a[i];

a[i] = t;

}

 

}

//输出排序结果

for (int i = 0;i < 10;i++) {

cout << a[i] << endl;

}

 

选择排序第二种写法：

 

int a[10] = { 3,5,1,7,2,4,6,9,8,0 };

/*选择排序，从每一次从前j个数中找出最大的数，再跟a[j]交换，然后j--，再重新查找前j个数中最大的数，如此循环，直到j=0,全部排完。*/

int max, i,j,t;

for (j = 9;j > 0;j--) {

max = j;

for (i = 0;i <= j;i++) {

if (a[i] > a[max]) {

max = i;

}

}

if(j!=max){

t = a[max];

a[max] = a[j];

a[j] = t;

}

 

}

//输出排序结果

for (int i = 0;i < 10;i++) {

cout << a[i] << endl;

}

二分查找与二分答案：

首先明确二分查找与二分答案有何区别?

二分查找：在一个已知的有序数据集上进行二分地查找

二分答案：答案有一个区间，在这个区间中二分，直到找到最优答案

以在一个升序数组中查找一个数为例。它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。

二分查找

当我们要从一个序列中查找一个元素的时候，最快想到的方法就是暴力查找法（即：从前到后依次查找）。但这种方法过于无脑，适用于元素较少的时候，一旦元素个数多起来，效率是非常低下，所以在实际中这种查找的方法是被摒弃的。

 

这里就不得不介绍一种简单且效率较高的查找方法了：二分查找法，又称折半查找法。但该方法是建立在有序的前提下的。

 

二分查找法的前提条件是：查找的序列必须是有序的。即该序列中的所有元素都是按照升序或者降序排列好的，元素与元素只间的差值虽然是随机的，但始终是在递增或递减。

模板一（基本的二分查找）

这个场景是最简单的，肯能也是大家最熟悉的，即搜索一个数，如果存在，返回其索引，否则返回 -1

 

int check(int num[],int size,int t){

  int left=0,right=size-1;  // 定义了t在左闭右闭的区间内，[left, right]

  while(left<=right){  //当left==right时，区间[left, right]仍然有效

    int mid=left+((right-left)/2);//等同于(left+right)/2，防止溢出

    if(num[mid]>t){

      right=mid-1;   //t在左区间，所以答案在[left, mid-1]

    }else if(num[mid]<t){

      left=mid+1;     //t在右区间，所以答案在[mid+1,right]

    }else{       //num[mid]==t，找到答案

      return mid;

    }

  }

  return -1;      //没有找到目标值

}

声明一下，计算 mid 时需要防止溢出，代码中left+(right-left)/2就和(left+right)/2的结果相同，但是有效防止了left和right太大直接相加导致溢出

 

总结

因为我们初始化right=size-1

所以决定了我们的查找区间是[left, right]

所以决定了while (left<=right)

同时也决定了left=mid+1和right=mid-1

 

因为我们只需找到一个t的索引即可

所以当num[mid]==target时可以立即返回

 

模板二（寻找左侧边界的二分查找）

int check(int num[],int size,int t){

  int left=0,right=size;

  while(left<right){  //每次循环的查找区间是[left,right)左闭右开

    int mid=(left+right)/2;

   if(nums[mid]<t){

      left=mid+1;

    }else if(nums[mid]>t){

      right=mid; 

    }else{  //两个条件可以合并为一个 

     right=mid;

}

  }

  return left; //终止的条件是left==right，此时搜索区间[left,left)为空，可以正确终止

}

总结

因为我们初始化right=size

所以决定了我们的查找区间是[left, right)

所以决定了while (left < right)

同时也决定了left=mid+1和right=mid

 

因为我们需找到t的最左侧索引

所以当num[mid]==t时不要立即返回

而要收紧右侧边界以锁定左侧边界

 

模板三（寻找右侧边界的二分查找）

int check(int num[],int size,int t){

  int left=0,right=size;

  while(left<right){ //每次循环的查找区间是[left, right)

    int mid=(left+right)/2;

    if(num[mid]<t){

      left=mid+1;

    }else if(nums[mid]>target){

      right=mid;

    }else{ //两个条件可以合并为一个

      left=mid+1; 

    }

  }

  return left-1; //终止的条件是left==right，此时搜索区间(right,right]为空，可以正确终止

}

总结

因为我们初始化right=size

所以决定了我们的查找区间是[left, right)

所以决定了while (left < right)

同时也决定了left=mid+1和right=mid

 

因为我们需找到t的最右侧索引

所以当num[mid]==t时不要立即返回

而要收紧左侧边界以锁定右侧边界

 

又因为收紧左侧边界时必须left=mid+1

所以最后无论返回left还是right，必须减一

 

对于寻找左右边界的二分搜索，常见的手法是使用左闭右开的查找区间，我们还根据逻辑将查找区间全都统一成了两端都闭，便于记忆，只要修改两处即可变化出三种写法：

 

int check(int num[],int size,int t){

  int left=0,right=size-1; 

  while(left<=right){

    int mid=left+(right-left)/2;

    if(num[mid]<t){

      left=mid+1;

    }else if(num[mid]>t){

      right=mid-1; 

    }else{

      return mid;// 直接返回

    }

  }

  return -1;

}

 

int check(int num[],int size,int t){

  int left=0,right=size-1;

  while(left<=right){

    int mid=left+(right-left)/2;

    if(num[mid]<t){

      left=mid+1;

    }else if(num[mid]>t) {

      right=mid-1;

    }else{

      right=mid-1; //别返回，锁定左侧边界

    }

  }

   

  if (left>=size||num[left]!=t){

   return -1; // 最后要检查 left 越界的情况

}    

  return left;

}

 

 

int check(int num[],int size,int t){

  int left=0,right=size-1;

  while(left<=right){

    int mid=left+(right-left)/2;

    if(num[mid]<t) {

      left=mid + 1;

    }else if(num[mid]>t) {

      right=mid-1;

    }else{ 

      left=mid+1;// 别返回，锁定右侧边界

    }

  }

  if (right<0||num[right]!=t){

   return -1;// 最后要检查 right 越界的情况

}

  return right;

}

如果以上内容你都能理解，那么恭喜你，二分查找也不过如此。。。

 

二分答案

什么是二分答案？

答案属于一个区间，当这个区间很大时，暴力超时。但重要的是——这个区间是对题目中的某个量有单调性的，此时，我们就会二分答案。每一次二分会做一次判断，看是否对应的那个量达到了需要的大小。

判断：根据题意写个check函数，如果满足check，就放弃右半区间（或左半区间），如果不满足，就放弃左半区间（或右半区间），一直往复，直至到最终的答案。

 

如何判断一个题是不是用二分答案做的呢?

 

典型特征:

 

求...最大值的最小 、 求...最小值的最大。

1.求...最大值的最小时，我们二分答案（即二分最大值）的时候，判断条件满足后，尽量让答案往前来（即：让right=mid）

2.求...最小值的最大时，我们二分答案（即二分最小值）的时候，判断条件满足后，尽量让答案往后走（即：让left=mid）

二分答案用在的地方

1、答案在一个区间内（一般情况下，区间会很大，暴力超时）

 

2、直接搜索不好搜，但是容易判断一个答案可行不可行

 

3、该区间对题目具有单调性，即：在区间中的值越大或越小，题目中的某个量对应增加或减少。

递归&分治：

 

引入

要理解递归，就得先理解什么是递归。

递归的基本思想是某个函数直接或者间接地调用自身，这样原问题的求解就转换为了许多性质相同但是规模更小的子问题。求解时只需要关注如何把原问题划分成符合条件的子问题，而不需要过分关注这个子问题是如何被解决的。

以下是一些有助于理解递归的例子：

递归在数学中非常常见。例如，集合论对自然数的正式定义是：1 是一个自然数，每个自然数都有一个后继，这一个后继也是自然数。

递归代码最重要的两个特征：结束条件和自我调用。自我调用是在解决子问题，而结束条件定义了最简子问题的答案。

 

4

int func(传入数值) {

if (终止条件) return 最小子问题解;

return func(缩小规模);

}

为什么要写递归

1. 结构清晰，可读性强。例如，分别用不同的方法实现 归并排序：
2. C++
3. Python

 

1. 18

// 不使用递归的归并排序算法

template <typename T>

void merge_sort(vector<T> a) {

int n = a.size();

for (int seg = 1; seg < n; seg = seg + seg)

for (int start = 0; start < n - seg; start += seg + seg)

merge(a, start, start + seg - 1, std::min(start + seg + seg - 1, n - 1));

}

 

// 使用递归的归并排序算法

template <typename T>

void merge_sort(vector<T> a, int front, int end) {

if (front >= end) return;

int mid = front + (end - front) / 2;

merge_sort(a, front, mid);

merge_sort(a, mid + 1, end);

merge(a, front, mid, end);

}

1. 显然，递归版本比非递归版本更易理解。递归版本的做法一目了然：把左半边排序，把右半边排序，最后合并两边。而非递归版本看起来不知所云，充斥着各种难以理解的边界计算细节，特别容易出 bug，且难以调试。
2. 练习分析问题的结构。当发现问题可以被分解成相同结构的小问题时，递归写多了就能敏锐发现这个特点，进而高效解决问题。

递归的缺点

在程序执行中，递归是利用堆栈来实现的。每当进入一个函数调用，栈就会增加一层栈帧，每次函数返回，栈就会减少一层栈帧。而栈不是无限大的，当递归层数过多时，就会造成 栈溢出 的后果。

显然有时候递归处理是高效的，比如归并排序；有时候是低效的，比如数孙悟空身上的毛，因为堆栈会消耗额外空间，而简单的递推不会消耗空间。比如这个例子，给一个链表头，计算它的长度：

 

12

// 典型的递推遍历框架

int size(Node *head) {

int size = 0;

for (Node *p = head; p != nullptr; p = p->next) size++;

return size;

}

 

// 我就是要写递归，递归天下第一

int size_recursion(Node *head) {

if (head == nullptr) return 0;

return size_recursion(head->next) + 1;

}

 

递归的优化

主页面：搜索优化 和 记忆化搜索

比较初级的递归实现可能递归次数太多，容易超时。这时需要对递归进行优化。1

 

分治

 

过程

分治算法的核心思想就是「分而治之」。

大概的流程可以分为三步：分解 -> 解决 -> 合并。

 

1. 分解原问题为结构相同的子问题。
2. 分解到某个容易求解的边界之后，进行递归求解。
3. 将子问题的解合并成原问题的解。

分治法能解决的问题一般有如下特征：

 

• 该问题的规模缩小到一定的程度就可以容易地解决。
• 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质，利用该问题分解出的子问题的解可以合并为该问题的解。
• 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

注意

如果各子问题是不独立的，则分治法要重复地解公共的子问题，也就做了许多不必要的工作。此时虽然也可用分治法，但一般用 动态规划 较好。

以归并排序为例。假设实现归并排序的函数名为 merge_sort。明确该函数的职责，即 对传入的一个数组排序。这个问题显然可以分解。给一个数组排序等于给该数组的左右两半分别排序，然后合并成一个数组。

 

6

void merge_sort(一个数组) {

if (可以很容易处理) return;

merge_sort(左半个数组);

merge_sort(右半个数组);

merge(左半个数组, 右半个数组);

}

传给它半个数组，那么处理完后这半个数组就已经被排好了。注意到，merge_sort 与二叉树的后序遍历模板极其相似。因为分治算法的套路是 分解 -> 解决（触底）-> 合并（回溯），先左右分解，再处理合并，回溯就是在退栈，即相当于后序遍历。

merge 函数的实现方式与两个有序链表的合并一致。

 

要点

写递归的要点

明白一个函数的作用并相信它能完成这个任务，千万不要跳进这个函数里面企图探究更多细节， 否则就会陷入无穷的细节无法自拔，人脑能压几个栈啊。

以遍历二叉树为例。

 

5

void traverse(TreeNode* root) {

if (root == nullptr) return;

traverse(root->left);

traverse(root->right);

}

这几行代码就足以遍历任何一棵二叉树了。对于递归函数 traverse(root)，只要相信给它一个根节点 root，它就能遍历这棵树。所以只需要把这个节点的左右节点再传给这个函数就行了。

同样扩展到遍历一棵 N 叉树。与二叉树的写法一模一样。不过，对于 N 叉树，显然没有中序遍历。

 

4

void traverse(TreeNode* root) {

if (root == nullptr) return;

for (auto child : root->children) traverse(child);

}

区别

递归与枚举的区别

递归和枚举的区别在于：枚举是横向地把问题划分，然后依次求解子问题；而递归是把问题逐级分解，是纵向的拆分。

 

递归与分治的区别

递归是一种编程技巧，一种解决问题的思维方式；分治算法很大程度上是基于递归的，解决更具体问题的算法思想。

贪心：

引入

贪心算法（英语：greedy algorithm），是用计算机来模拟一个「贪心」的人做出决策的过程。这个人十分贪婪，每一步行动总是按某种指标选取最优的操作。而且他目光短浅，总是只看眼前，并不考虑以后可能造成的影响。

可想而知，并不是所有的时候贪心法都能获得最优解，所以一般使用贪心法的时候，都要确保自己能证明其正确性。

 

解释

适用范围

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。1

 

证明

贪心算法有两种证明方法：反证法和归纳法。一般情况下，一道题只会用到其中的一种方法来证明。

 

1. 反证法：如果交换方案中任意两个元素/相邻的两个元素后，答案不会变得更好，那么可以推定目前的解已经是最优解了。
2. 归纳法：先算得出边界情况（例如 ）的最优解 ，然后再证明：对于每个 ， 都可以由  推导出结果。

要点

常见题型

在提高组难度以下的题目中，最常见的贪心有两种。

 

• 「我们将 XXX 按照某某顺序排序，然后按某种顺序（例如从小到大）选择。」。
• 「我们每次都取 XXX 中最大/小的东西，并更新 XXX。」（有时「XXX 中最大/小的东西」可以优化，比如用优先队列维护）

二者的区别在于一种是离线的，先处理后选择；一种是在线的，边处理边选择。

 

排序解法

用排序法常见的情况是输入一个包含几个（一般一到两个）权值的数组，通过排序然后遍历模拟计算的方法求出最优值。

 

后悔解法

思路是无论当前的选项是否最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃掉这个选项；否则，正式接受。如此往复。

 

区别

与动态规划的区别

贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。