C++基础面试考点总结（持续更新）_c++技术面试必备知识

一、基础知识

1、基本知识

说一下C++和C的区别

设计思想上：C++是面向对象的，C是面向过程的

语法上：C++具有封装、继承和多态三种特性；C++相比C，增加了许多类型安全的功能，比如强制类型转换；C++支持范式编程，比如模板类、函数模板等

C++11的新特性

auto关键字、右值引用、初始化列表对类进行初始化、新增容器array和tuple、智能指针

inline函数的作用

加快函数的执行速度吧。因为内敛函数调用，是将调用表达式直接用内敛函数体来替换。

虚函数和纯虚函数的区别

声明不同：纯虚函数后面必须跟=0;

虚函数必须实现，纯虚函数一定没有实现

虚函数在子类里面可以不重载，但是纯虚函数必须重载

虚函数在子类里面也可以不重载的；但纯虚必须在子类去实现

说一下C++中static关键字的作用

1、修饰局部变量：
特点：有默认值0，只执行一次，运行一开始就开辟了内存，内存放在数据段
2、修饰全局函数和全局变量：
特点：只能在本源文件使用
3、修饰类里面的成员变量：

特点：和1差不多，定义多个类对象,但共用相同的静态成员变量,不进入类的大小计算，不依赖于类对象的存在而存在（可直接调用，要进行外置声明）（类名或对象直接访问）
4、修饰类的成员函数：

特点：f():括号里无this指针，只能调用他的本类静态函数和他的静态变量，即是用static修饰过的不依赖于类对象的存在而存在（可不进行外置声明，直接调用）（类名或对象直接访问）

说一说C++中的四种cast转换

C++中四种类型转换是：static_cast、dynamic_cast、const_cast、reinterpret_cast

1、dynamic_cast

用于动态类型转换。只能用于含有虚函数的类，用于类层次间的向上和向下转化。只能转指针或引用。向下转化时，如果是非法的对于指针返回NULL，对于引用抛异常。要深入了解内部转换的原理。

向上转换：指的是子类向基类的转换

向下转换：指的是基类向子类的转换

它通过判断在执行到该语句的时候变量的运行类型和要转换的类型是否相同来判断是否能够进行向下转换。

2、static_cast

​ 可以转换相关联的类，可以从子类转换成父类。也能从父类转向子类，但是如果转换的父类指针（或者父类引用）所指向的对象是完整的，那么是没有问题；但是如果所指向的对象并不完整，那么会出现runtime错误。

​ 用于各种隐式转换，比如非const转const，void*转指针等，static_cast能用于多态向上转化，如果向下转能成功但是不安全，结果未知。

3、reinterpret_cast

几乎什么都可以转，比如将int转指针，可能会出现问题，尽量少用。

​ 该操作不会去进行动态类型或者静态类型的检测，它仅仅将值强行赋值过去。从某种意义上对编译器进行了一种欺骗，同时也带来了一定的不安全性

4、const_cast

​ 常量转换，用于将const变量转为非const

指针和引用的区别？

1、指针是一个变量，引用是一个别名

2、指针可以为空，引用不可以为空，创建时候必须初始化

3、指针的值在初始化后可以改变，但是引用不可以改变

4、指针可以多级，但是引用只能一级

左值和右值引用的区别

左值与变量绑定一次，而右值只能和表达式绑定一起，且右值引用只能绑定到一个即将销毁的对象上

左值有持久性，右值一般是个临时变量或者字面常量

为什么要使用智能指针

智能指针的作用是管理一个指针，因为存在以下这种情况：申请的空间在函数结束时忘记释放，造成内存泄漏。使用智能指针可以很大程度上的避免这个问题，因为智能指针就是一个类，当超出了类的作用域是，类会自动调用析构函数，析构函数会自动释放资源。所以智能指针的作用原理就是在函数结束时自动释放内存空间，不需要手动释放内存空间。

请你说一下你理解的c++中的smart pointer四个智能指针

• auto_ptr（C++11已抛弃）

采用所有权模式，使用=将会给所有权传给对方。

auto_ptr< string> p1 (new string ("I reigned lonely as a cloud.”));
auto_ptr<string> p2;
p2 = p1; //auto_ptr不会报错.
1
2
3

此时不会报错，p2剥夺了p1的所有权，但是当程序运行时访问p1将会报错。所以auto_ptr的缺点是：存在潜在的内存奔溃问题！

• unique_ptr（独占的智能指针）

unique_ptr实现独占式拥有或严格拥有概念，保证同一时间内只有一个智能指针可以指向该对象。它对于避免资源泄露（例如“以new创建对象后因为发生异常而忘记调用delete”）特别有用。

unique_ptr<string> p3 (new string ("auto"));   //#4
unique_ptr<string> p4；                       //#5
p4 = p3;//此时会报错！！
1
2
3

编译器认为p4=p3非法，避免了p3不再指向有效数据的问题。因此，unique_ptr比auto_ptr更安全。另外unique_ptr还有更聪明的地方：当程序试图将一个 unique_ptr 赋值给另一个时，如果源 unique_ptr 是个临时右值，编译器允许这么做；如果源 unique_ptr将存在一段时间，编译器将禁止这么做，比如：

unique_ptr<string> pu1(new string ("hello world"));
unique_ptr<string> pu2;
pu2 = pu1;                                      // #1 not allowed
unique_ptr<string> pu3;
pu3 = unique_ptr<string>(new string ("You"));   // #2 allowed
1
2
3
4
5

注：如果确实想执行类似与#1的操作，要安全的重用这种指针，可给它赋新值。C++有一个标准库函数std::move()，让你能够将一个unique_ptr赋给另一个。例如：

unique_ptr<string> ps1, ps2;
ps1 = demo("hello");
ps2 = move(ps1);
ps1 = demo("alexia");
cout << *ps2 << *ps1 << endl;
1
2
3
4
5

• shared_ptr（共享的智能指针）

shared_ptr实现共享式拥有概念。多个智能指针可以指向相同对象，该对象和其相关资源会在“最后一个引用被销毁”时候释放。从名字share就可以看出了资源可以被多个指针共享，它使用计数机制来表明资源被几个指针共享。

• 可以通过成员函数use_count()来查看资源的所有者个数。
• 除了可以通过new来构造，还可以通过传入auto_ptr, unique_ptr,weak_ptr来构造。
• 当我们调用reset时，当前指针会释放资源所有权，计数减一。当计数等于0时，资源会被释放。
• shared_ptr 是为了解决auto_ptr在对象所有权上的局限性(auto_ptr是独占的), 在使用引用计数的机制上提供了可以共享所有权的智能指针。
• 对shared_ptr进行初始化时不能将一个普通指针直接赋值给智能指针，因为一个是指针，一个是类。可以通过make_shared函数或者通过构造函数传入普通指针。并可以通过get函数获得普通指针。

成员函数：

• use_count 返回引用计数的个数。
• unique 返回是否是独占所有权( use_count 为 1)。
• swap 交换两个 shared_ptr 对象(即交换所拥有的对象)。
• reset放弃内部对象的所有权或拥有对象的变更, 会引起原有对象的引用计数的减少。
• get 返回内部对象(指针), 由于已经重载了()方法, 因此和直接使用对象是一样的.如 shared_ptr<int> sp(new int(1)); sp 与 sp.get()是等价的。

• weak_ptr（弱引用的智能指针）

weak_ptr是一种不控制对象生命周期的智能指针，它指向一个shared_ptr管理对象。进行该对象的内存管理的是那个强引用的share_ptr.weak_ptr只是提供了对管理对象的一个访问手段。

• weak_ptr设计的目的是为配合 shared_ptr而引入的一种智能指针来协助 shared_ptr 工作, 它只可以从一个 shared_ptr或另一个 weak_ptr对象构造, 它的构造和析构不会引起引用记数的增加或减少。weak_ptr是用来解决shared_ptr相互引用时的死锁问题,如果说两个shared_ptr相互引用,那么这两个指针的引用计数永远不可能下降为0,资源永远不会释放。它是对对象的一种弱引用，不会增加对象的引用计数，和shared_ptr之间可以相互转化，shared_ptr可以直接赋值给它，它可以通过调用lock函数来获得shared_ptr。

class B;

class A
{
	public:
	shared_ptr<B> pb_;
	~A()
	{
	cout<<"A delete\n";
	}
};

class B
{
	public:
	shared_ptr<A> pa_;
	~B()
	{
	cout<<"B delete\n";
	}
};
void fun()
{
	shared_ptr<B> pb(new B());
	shared_ptr<A> pa(new A());
	
	pb->pa_ = pa;
	pa->pb_ = pb;
	
	cout<<pb.use_count()<<endl;
	cout<<pa.use_count()<<endl;
}
int main()
{
	fun();
	return 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
35
36
37

• 可以看到fun函数中pa ，pb之间互相引用，两个资源的引用计数为2，当要跳出函数时，智能指针pa，pb析构时两个资源引用计数会减一，但是两者引用计数还是为1，导致跳出函数时资源没有被释放（A B的析构函数没有被调用），如果把其中一个改为weak_ptr就可以了，我们把类A里面的shared_ptr pb_; 改为weak_ptr pb_; 运行结果如下，这样的话，资源B的引用开始就只有1，当pb析构时，B的计数变为0，B得到释放，B释放的同时也会使A的计数减一，同时pa析构时使A的计数减一，那么A的计数为0，A得到释放。
• 注意的是我们不能通过weak_ptr直接访问对象的方法，比如B对象中有一个方法print(),我们不能这样访问，pa->pb_->print();英文pb_是一个weak_ptr，应该先把它转化为shared_ptr,如：shared_ptr p = pa->pb_.lock(); p->print();
• 弱引用能检测到所管理的对象是否已经被释放，从而避免访问非法内存。

请你回答一下智能指针有没有内存泄露的情况

有，当两个对象相互使用一个shared_ptr成员变量指向对方，会造成循环引用，使引用计数失效，从而导致内存泄漏。

请你来说一下智能指针的内存泄漏如何解决

对象中使用weak_ptr弱指针对象，weak_ptr的构造函数不会修改引用计数的值，从而不会对对象的内存进行管理，其类似一个普通指针，但不指向引用计数的共享内存，但是其可以检测到所管理的对象是否已经被释放，从而避免非法访问。

如何判断内存泄露

程序里可以记一下申请的内存和释放的内存，看看是否一致

请你介绍下C++中的智能指针

智能指针是C++11 引入的，用于管理在堆上分配的内存，它将普通的指针封装为一个类对象。当类对象的生存周期结束后，会在析构函数中释放掉申请的内存，从而防止内存泄漏。包含在头文件中，其中包括：

请回答一下数组和指针的区别

数组是用于储存多个相同类型数据的集合。

指针相当于一个变量，但是它和一般变量不一样，它存放的是其它变量在内存中的地址。

数组是以某种类型为单位的连续的一段内存空间作为存储区域，其中存储相应的数据。其变量名代表数组起始空间地址，也就是首元素的地址。

指针是的本质是内存中某一字节的地址，其存储在变量名所对应的内存空间中。

之所以说数组的本质是指针，是因为在在具体实现上，数组是基于指针实现的，编译器只提供了数组首元素的地址，因此在访问时需要使用首地址+偏移量的形式，所谓的偏移量由下标决定。

请回答一下野指针是什么

野指针，也就是指向不可用内存区域的指针。通常对这种指针进行操作的话，将会使程序发生不可预知的错误。不是NULL指针，造成原因：1、指针变量没有被初始化；2、指针p被free或者delete之后没有置NULL

请你来说一下函数指针

函数指针本身首先是一个指针变量，该指针变量指向一个具体的函数。这正如用指针变量可指向整型变量、字符型、数组一样，这里是指向函数入口地址。

char *run(char *P){...}
char *(*pf)(char*p);
pf=run;
pf(p)
1
2
3
4

请你回答一下为什么析构函数必须是虚函数？为什么C++默认的析构函数不是虚函数

将可能会被继承的父类的析构函数设置为虚函数，可以保证当我们new一个子类，然后使用基类指针指向该子类对象，释放基类指针时可以释放掉子类的空间，防止内存泄漏。

C++默认的析构函数不是虚函数是因为虚函数需要额外的虚函数表和虚表指针，占用额外的内存。而对于不会被继承的类来说，其析构函数如果是虚函数，就会浪费内存。因此C++默认的析构函数不是虚函数，而是只有当需要当作父类时，设置为虚函数。

请你来说一下C++中析构函数的作用

用于释放资源，防止内存泄露

请你来说一下fork函数

创建与当前进程几乎一样的进程，两进程同时继续运行。如果父进程调用fork成功，返回子进程pid，子进程调用成功返回0，失败放回负值

用于创建一个进程，调用一次，返回两次。返回值为0时，为子进程；返回值大于0时，为父进程。采用写时复制技术，因此fork的速度极快…

请你来说一下fork函数与vfork函数的区别

1、fork( )的子进程拷贝父进程的数据段和代码段；vfork( )的子进程与父进程共享数据段

2、fork( )的父子进程的执行次序不确定；vfork( )保证子进程先运行，在调用exec或exit之前与父进程数据是共享的，在它调用exec或exit之后父进程才可能被调度运行

请你来说一下静态函数和虚函数的区别

静态函数在编译的时候就已经确定运行时机，虚函数在运行的时候动态绑定。虚函数因为用了虚函数表机制，调用的时候会增加一次内存开销

虚函数有什么作用？

实现子类与基类之间的多态，基类和子类调用同名的虚函数时，所调用的就不是同一个函数。

请你说一说你理解的虚函数和多态

多态的实现主要分为静态多态和动态多态，静态多态主要是重载，在编译的时候就已经确定；动态多态是用虚函数机制实现的，在运行期间动态绑定

虚函数表

虚函数表保存的是类中虚函数的地址

重载和覆盖有什么区别

1、重载是指不同的函数使用相同的函数名，但是函数的参数个数或类型不同。调用的时候根据函数的参数来区别不同的函数。是水平关系

2、覆盖（也叫重写）是指在派生类中重新对基类中的虚函数（注意是虚函数）重新实现。即函数名和参数都一样，只是函数的实现体不一样。是垂直关系

说一说strcpy和strlen

strcpy是字符串拷贝函数，从src逐字节拷贝到dest，直到遇到’\0’结束，因为没有指定长度，可能会导致拷贝越界，造成缓冲区溢出漏洞,安全版本是strncpy函数（加入了第三个参数拷贝长度）。

strlen函数是计算字符串长度的函数，返回从开始到’\0’之间的字符个数。

写一个函数在mian函数执行前先运行

__attribute((constructor))是gcc扩展，标记这个函数应当在main函数之前执行。同样有一个__attribute((destructor))，标记函数应当在程序结束之前（main结束之后，或者调用了exit后）

__attribute((constructor))void f(){
cout<<111<<endl;
}
int main()
{
cout<<"aaa"<<endl;
	return 0;
}
1
2
3
4
5
6
7
8

请你来说一下C++里是怎么定义常量的？常量存放在内存的哪个位置？

定义前面加const，局部常量存放在栈区，全局常量放在数据段中

请你说一说malloc的原理，另外brk和mmap系统调用的作用分别是什么？

malloc函数用于动态申请内存，malloc采用了内存池方法，先申请一个大块内存作为堆区，然后将堆区划分为若干个内存块，以内存块作为内存管理的基本单位。用户申请内存时，直接从堆区分配合适的空闲内存块。隐形链表将堆区分成连续的，大小不一的快，包含已分配和未分配的。采用显示链表管理所有空闲快。

申请内存小于128k时会使用brk申请内存，将数据段最高地址指针往高地址推；

申请内存大于128k时会使用mmap申请内存，在堆栈中间找一块空闲的虚拟内存；

malloc和new的区别

1、malloc需要给定申请内存的大小，返回的指针需要强转

2、new会调用构造函数，malloc不会

3、new是一个操作符可以重载，而malloc是一个库函数

const修饰成员函数的目的

表明函数不会对对象作出任何修改

allocator

用于封装STL的容器在内存管理上的底层细节，它将new，delete分为4个函数来实现，内存申请、对象构造、对象析构、释放内存

迭代器及其作用，遍历容器时怎么删除元素

提供了一种顺序访问一个聚合对象中各个元素，并不暴露该对象的内部表示的方法

vector来说，删除一个元素后，后面每个元素的迭代器都会失效，但每个元素都会往前移一个位置，erase返回下一个有效地址。

对于map和set，因为内部是红黑树，删除一个元素，不会影响其他元素位置，所以删erase之前，需要记录下一个迭代器

list两种方法都可以

deque的底层实现

deque采用一块所谓的map(注意,不是STL的map容器)作为主控。这里所谓map是一小块连续空间 ，其中每个元素(此处称为一个节点, node)都是指针，指向另一段(较大的) 连续线性空间，称为缓冲区。缓冲区才是deque的存储空间主体。

resize和reserve

resize可以更改容器中元素个数

reserve改变容器最大容纳元素个数

struct 和class的区别

struct成员与继承默认都是公有的，class则默认为私有。

class可以定义函数类模板，struct不行template<class t,int>

编译过程

预处理阶段：对源代码文件中的头文件，预编译语句进行分析和替换，生成预编译文件

编译阶段：将预编译文件转换成汇编代码生成汇编文件

汇编阶段：对汇编文件转换成机器码，生成可重定位目标文件

链接阶段：将多个目标文件及所需要的的库进行连接成最终的可执行文件

内存管理

C++中虚拟内存分为代码段、数据段、BSS段、堆区、文件映射区、栈区

代码段：只读存储区用于存放字符常量，文本区存放机器代码

数据段：用于存放初始化了的全局变量和静态变量

bss段：存放未初始化的全局变量和静态变量，初始化为0的全局变量和静态变量也存放在这

堆区：动态分配内存从堆区进行分配

文件映射区：mmap函数就是在这里分配内存，存储动态链接库

栈区：存放局部变量，函数返回地址、参数、返回值

红黑树和AVL平衡树

AVL平衡树，保证了每个子树的左右子树高度差绝对值不超过1。但是红黑树的话则没有这一要求，红黑树确保了没有一条路径会比其他路径长出两倍。

同时红黑树的根和叶子节点都为黑色，对于任意节点到其叶子节点的黑色节点数都相同。插入的节点是红色的。每一个红色节点儿子一定是黑色节点

插入最多扭转2次，删除最多3次扭转

当插入点的父红，叔为红色，父叔变为黑色，祖父变为红色，往祖父向上递归

当插入点的父红，叔不红且，父子不在同一边，可以以子节点进行左扭转，变成父子同一边

当插入点的父红，叔不红且，父子在同一边，可以以父节点进行右扭转

删除的话不太清楚

B+和B树

B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作

B+ 树是对B树的一种变形树，它与B树的差异在于：

有k个子结点的结点必然有k个关键码；

非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。

树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。

函数调用过程

1、根据调用的函数名找到函数入口；

2、在栈中申请调用函数中的参数及函数体内定义的变量的内存空间（保护现场，入口地址，参数从右到左）

4、函数执行完后，释放函数在栈中的申请的参数和变量的空间，最后返回值。（恢复现场）

二叉树反序列化

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution{
public:
TreeNode * Build(int pl,int pr,int vl,int vr,vector<int>&pre,vector<int>&vin){
  if(pl>pr||vl>vr)return NULL;
  TreeNode *head=new TreeNode(pre[pl]);    //前序第一个为根
  int root=0;
  for(int i=vl;i<=vr;++i){  //找到根在中序位置分左右儿子
      if(vin[i]==pre[pl]){
          root=i;
          break;
      }
  }
  head->left=Build(pl+1,pl+root-vl,vl,root-1,pre,vin);
  head->right=Build(pl+root-vl+1,pr,root+1,vr,pre,vin);
  return head;
}
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin){
  return Build(0,pre.size()-1,0,vin.size()-1,pre,vin);
}
};
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

快速排序

void Quick(int l,int r,int *a){
  if(l>=r)return;
  int key=a[l];
  int first==l;
  int last==r;
  while(first<last){
      while(first<last&&a[last]>=key)--last;
      a[first]=a[last];
      while(first<last&&a[first]<=key)first++;
      a[last]=a[first];
  }
  a[first]=key;
  Quick(l,first-1,a);
  Quick(first+1,r,a);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

归并排序

void Sort(int a[],int f[],int l,int mid,int r){
  int i=l,j=mid+1,k=l;
  while(i<mid&&j<=r){
      if(a[i]>a[j])f[k++]=a[j++];
      else f[k++]=a[i++];
  }
  while(i<=mid)f[k++]=a[i++];
  while(j<=r)f[k++]=a[j++];
}
void Merge(int a[],int f[],int k,int n){
  int i=0;
  while(i<=n-2*k){//每个快大小
      Sort(a,f,i,i+k-1,i+2*k-1);
      i+=2*k;
  }
  if(i<n-k+1)Sort(a,f,i,i+k-1,n-1);   //超过k个直接归并
  else for(int j=i;j<n;++j)f[j]=a[j]; //不超过
  for(int i=0;i<n;++i)a[i]=f[i];
}
void GSort(int a[],int n){
  int *f=(int *)malloc(sizeof(int)*(n+1));
  int i=1;
  while(i<n){
      Merge(a,f,i,n);
      i*=2;
  }
  free(f);
}
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

递归版本

void Merge(int a[], int l, int r, int mid){    //合并
	int *f = (int*)malloc((r - l + 1)*sizeof(int));
	int i = l, j = mid + 1, k = 0;
	while (i <= mid&&j <= r){
		if (a[i] <= a[j])f[k++] = a[i++];
		else f[k++] = a[j++];
	}
	while (i <= mid)f[k++] = a[i++]; //如果左边有没加入的则全部合并进来
	while (j <= r)f[k++] = a[j++];   //等同
	for (i = 0; i<k; i++){   //扔回给a
		a[i + l] = f[i];
	}
	free(f);
}
void MergeSort(int a[], int l, int r){    //拆分
	if (l >= r)return;
	MergeSort(a, l, (l + r) / 2);
	MergeSort(a, (l + r) / 2 + 1, r);
	Merge(a, l, r, (l + r) / 2);   //合并
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

堆排序

#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
#include <Windows.h>
using namespace std;//堆排序的核心是建堆,传入参数为数组，根节点位置，数组长度
void Heap_build(int a[],int root,int length)
{
int lchild = root*2+1;//根节点的左子结点下标
if (lchild < length)//左子结点下标不能超出数组的长度
{
  int flag = lchild;//flag保存左右节点中最大值的下标
  int rchild = lchild+1;//根节点的右子结点下标
  if (rchild < length)//右子结点下标不能超出数组的长度(如果有的话)
  {
      if (a[rchild] > a[flag])//找出左右子结点中的最大值
      {
          flag = rchild;
      }
  }
  if (a[root] < a[flag])
  {
      //交换父结点和比父结点大的最大子节点
      swap(a[root],a[flag]);
      //从此次最大子节点的那个位置开始递归建堆
      Heap_build(a,flag,length);
  }
}
}

void Heap_sort(int a[],int len)
{
for (int i = len/2; i >= 0; --i)//从最后一个非叶子节点的父结点开始建堆
{
  Heap_build(a,i,len);
}

for (int j = len-1; j > 0; --j)//j表示数组此时的长度，因为len长度已经建过了，从len-1开始
{
  swap(a[0],a[j]);//交换首尾元素,将最大值交换到数组的最后位置保存
  Heap_build(a,0,j);//去除最后位置的元素重新建堆，此处j表示数组的长度，最后一个位置下标变为len-2
}

}
int main(int argc, char **argv)
{
clock_t Start_time = clock();
int a[10] = {12,45,748,12,56,3,89,4,48,2};
Heap_sort(a,10);
for (size_t i = 0; i != 10; ++i)
{
   cout<<a[i]<<" ";
}
clock_t End_time = clock();
cout<<endl;
cout<<"Total running time is: "<<static_cast<double>(End_time-Start_time)/CLOCKS_PER_SEC*1000<<" ms"<<endl;
cin.get();
return 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
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

最长上升子序列

int a[maxn];
int dp[maxn];
int main(){
  int n;
  scanf("%d",&n);
  for(int i=1;i<=n;++i){
      scanf("%d",&a[i]);
  }
  int len=1;
  dp[len]=a[1];
  for(int i=2;i<=n;++i){
      if(a[i]>=dp[len])dp[++len]=a[i];
      else{
          int id=lower_bound(dp+1,dp+1+len,a[i])-dp;   //最长不下降为upper_bound
          dp[id]=a[i];
      }
  }
  printf("%d\n",len);
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

最长公共子序列

char a[maxn],b[maxn];
int dp[maxn][maxn];
int main(){
scanf("%s%s",a+1,b+1);
int lena=strlen(a+1),lenb=strlen(b+1);
for(int i=1;i<=lena;++i)dp[1][0]=0;
for(int i=1;i<=lenb;++i)dp[0][1]=0;
for(int i=1;i<=lena;++i){
  for(int j=1;j<=lenb;++j){
      if(a[i]==b[j])dp[i][j]=dp[i-1][j-1]+1;
      else dp[i][j]=max({dp[i][j],dp[i-1][j],dp[i][j-1]});
  }
}
printf("%d\n",dp[lena][lenb]);
return 0;
}

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

01背包

int w[maxn],v[maxn],dp[maxn];
int main(){
  int n,ww;
  scanf("%d%d",&n,&ww);
  for(int i=1;i<=n;++i)scanf("%d%d",&w[i],&v[i]);
  for(int i=1;i<=n;++i){
      for(int j=ww;j>=w[i];--j){
          dp[i]=max(dp[i],dp[i-w[i]]+v[i]);
      }
  }
  printf("%d\n",dp[ww]);
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

完全背包

int w[maxn],c[maxn];
int dp[2000];
int main(){
  int n,v;
  scanf("%d%d",&n,&v);
  for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&c[i]);
  for(int i=1;i<=n;i++){
      for(int j=w[i];j<=v;j++){   //设 f[v]表示重量不超过v公斤的最大价值
          dp[j]=max(dp[j-w[i]]+c[i],dp[i]);
      }
  }
  printf("%d\n",dp[v]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

多重背包

int w[maxn],v[maxn],num[maxn],dp[maxn];
int main(){
  int n,ww;
  scanf("%d%d",&n,&ww);
  for(int i=1;i<=n;++i)scanf("%d%d",&w[i],&v[i],&num[i]);
  for(int i=1;i<=n;++i){
      for(int k=1;k<=num[i];k<<=1){
          num[i]-=k;
          for(int j=ww;j>=w[i]*k;--j){
              dp[i]=max(dp[i],dp[i-w[i]*k]+v[i]*k);
          }
      }
      if(num[i])
          for(int j=ww;j>=w[i]*num[i];--j){
              dp[i]=max(dp[i],dp[i-w[i]*num[i]]+v[i]*num[i]);
          }
  }
  printf("%d\n",dp[ww]);
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20