C++ 基本语法复习

参照传智播客的黑马的教程 https://www.bilibili.com/video/BV1et411b73Z/?p=2

基础内容不多赘述。

单行注释多行注释 // /**/

变量、常量(宏常量 #define k 1, const 常量)、关键字、标识符(_、字母、数字)

short int long long long float double char bool

string 需要导入头文件 #include <string>

sizeof 可以获得变量或者基本数据类型锁占的内存空间数目(以字节为单位)

+ – * / % ++ — = == > < >= <= != && || * & …..算术运算符 赋值运算符 比较运算符 逻辑运算符

流程控制 if else do while for switch case default break continue goto(不常用)

数组的定义:

  • int arr [] = {1,2,3,4,5}; //推断数组长度
  • int arr[5] ;
  • int arr[10] = {1,2,3,4};//其余的自动补充初始化默认值 0

二维数组

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

函数的声明,函数的定义,函数参数值传递机制

函数的分文件编写:

创建.h头文件(写函数的声明)

创建.cpp源文件(写函数的定义)(在第一行写 #include “xxx.h” 关联两个文件(函数的定义和声明))

<>系统自带 “” 用户自定义

在主程序.cpp源文件中引入头文件就可以使用函数了 (第一行引入 #include “xxx.h)

指针

int a = 5;

int * p = & a;

指针也是一种数据类型,只不过存的内容是地址值, * 号和&号的意义。

空指针(NULL) 野指针 乱给的地址值

  • const int * p,指针指向可以改,指的内容不能改
  • int * const p 指针指向不能改,指的内容可以改
  • const int * const p 都不能改

数组的名称实际上就是一个指针

结构体

  • struct Student {int age; string name;};
  • struct Student stu;
  • Student stu1 = {10, “mingming”};
  • stu.age = 10;
  • stu.name = “lili”;
  • Student *p = &stu;
  • p->age = 11;

结构体变量作为函数的形式参数的时候,利用指针作为形式参数,节省空间(不会复制一份变量),const Student * stu 还可以避免函数内部的修改操作,保护原来的变量。

C++内存模型

代码区、全局区(全局变量、静态变量和常量)、栈区(编译器自动分配和释放)、堆区(用户分配和释放)

代码区就是程序编译之后的二进制机器指令,共享且只读

全局区: (全局变量、静态变量和常量) 和普通的函数内的局部变量存放地址存的区域不同

常量 :

  • 字符串常量 &“hello world”
  • 全局常量 :在全局区中
  • 局部常量:不在全局区中

程序运行之前分为代码区和常量区

栈区的数据是由编译器管理和释放的,切记不要返回局部变量的地址

堆空间的数据都是用户new出来的,使用用delete

  • int * a = new int (10);
  • delete a;
  • int * arr = new int[10];
  • delete [] arr;

引用:就是变量的别名

int a = 10;

int & b = a;

引用必须初始化,并且初始化之后不可以修改

区别 值传递、地址传递(本质还是值传递)、引用传递

不要返回局部变量的引用,如果一个函数返回值是引用,则函数调用可以作为左值

从底层的角度来看,引用的本质就是用指针常量来实现的。

int &b = a; ==> int * const b = &a;

b = 10; ==> *b = 10;

编译器会帮你做转换,相当于一种语法糖吧

const int & b = 10;

编译器会优化为 int tmp = 10;const int & b = tmp;

但是 int & b = 10;这样的语句是非法的。

const int & b 可以用在函数的形参,只读,防止值在函数内被改变

void fun(const int & a) {}

函数支持默认参数,一个位置由默认参数,则右边的参数都应该由。函数的声明和定义只能在一处写默认值,否则存在二义性。

函数的占位参数,运算符重载的时候会用到

void func(int a, int )

函数重载:同一个作用域,函数名相同,参数类型、个数、顺序不同,返回值不作为重载的条件(会产生歧义)。const和非const参数可能会导致重载,默认参数也可能导致一些重载错误,主要从是否存在歧义性进行分析。

面向对象三大特性:封装、继承、多态

封装:就是类class(成员方法、成员函数)

权限 public、protected、private(struct 默认是public, class 默认是private)

构造函数Person(){}、析构函数~Person(){}、拷贝构造函数Person(const Person & p){…},如果定义,编译器会自动加上

创建对象的三种方式:

  • Person p1, Person p1(10);//这种空参不能带括号,否则和函数声明一样歧义。
  • Person p1 = Person(10);
  • Person p1 = 10;

拷贝构造函数调用的时机:

  • 使用一个已经创建的对象初始化另个新对象
  • 值传递的方式给函数传参数
  • 值传递的方式在函数内返回

默认的拷贝函数是浅拷贝,内部的成员变量默认都是值传递,而new出来在堆区保存的地址,只会拷贝地址,析构的时候会重复释放报错。

构造函数可以有初始化列表Person(int a):age(a){}

静态成员变量和静态成员函数是所有对象共享的,可以 类名::变量/函数名 进行访问或者调用。静态方法只能访问静态变量(因为没有this指针)

C++对象模型

  • 成员变量和成员函数是分开存储的
  • 空对象默认占一个字节(占位置),普通对象占空间就是非静态成员变量所占的总大小。

this指针 指向对象本身,可以通过返回当前对象的引用实现链式编程

Person & doSomething(){return *this;}

空指针可以访问成员函数,只要函数里面不会用到this就不会报错。

常函数: void show()const {……;}

this指针本质上就是一个指针常量, Person * const this,指向不可修改。因此常函数可以理解为const Person * const this, 不可以修改。

常对象:const Person p;

常对象只能调用常函数

mutable 修饰的属性,即使在常函数/常对象里面也可以修改。

友元( 访问类的私有成员)

  • 全局函数做友元函数
  • 类也可以做友元
  • 成员函数做友元

运算符重载

通过成员函数重载

Person operator+(Person& p) { Person tmp; tmp.val= this->val + p.val; return tmp}

通过全局函数重载

Person operator+(Person &p1, Persion & p2) {Person tmp; tmp.val = p1.val + p2.val; return tmp;}

重载<<运算符

ostream & operator<<(ostream & cout, Persion &p) { cout<<p.val; return cout;}

满足调用顺序(只能用全局函数重载),链式调用(返回引用),访问私有(加友元)

重载递增运算符

前++ Person & operator++(){this->age ++; return *this;}

返回引用是为了支持链式调用

后++ Person operator++(int){Person tmp = * this; this->age ++; return tmp;}

int 是占位参数,返回方式是值返回,防止局部变量的返回

编译器自动给写的4个函数

  • 默认构造函数
  • 默认析构函数
  • 默认拷贝构造函数
  • 重载赋值运算符

重载赋值运算符

Person & operator =(Person & p){ this->age = p.age; return *this;}

赋值运算符会涉及深拷贝和浅拷贝的问题,需要注意

重载关系运算符 bool operator==(Person & p){} bool operator!=(Person & p){}

函数调用运算符重载(仿函数) void operator()(string str){ cout<<str<<endl;}

使用方式:

Person p;
p("hello word");//调用仿函数
Person()("hello word");//匿名对象调用仿函数

继承

继承有三种主要方式public、protected、private

父类的私有的成员子类不可访问,public继承父类权限保留;protected继承,父类全变protected;private继承父类全变private。

继承中的对象模型,对象的大小(sizeof)包括所有非静态的变量所占的大小,包括父类的私有属性。

构造函数的执行顺序:先祖先(继承),再朋友(组合),最后自己,析构顺序相反。

同名的成员处理方式,加作用域。 直接访问是访问子类的,访问父类:Base::属性(适用于属性和方法,静态(可以通过类名访问)非静态都是一样的访问思路)

c++支持多继承,实际一般不推荐这么用

class son: public base1, public base2 {}

多继承会存在菱形继承的问题,用虚继承的方式来解决,这样只会有一份爷爷类的变量,节省空间(具体是再两个父亲类中设置虚继承指针,指向同一个爷爷类变量的起始位置),虚继承写在父类上。

class grandpa{} class father1: virtual public grandpa{} class father2: virtual public grandpa{} class son: public father1,public father2{}

多态

静态多态(早绑定,编译时期就确定函数地址,如函数重载、运算符重载)

动态多态(晚绑定,运行时期才能确定函数地址)

多态的本质就是父类的引用/指针 指向 子类的对象。 需要virtual关键字(虚函数)来配合。

动态多态的必要条件:

  • 存在继承关系
  • 子类需要重写父类的虚函数

原理:虚方法会在对象模型中生成一个vfptr(虚函数指针),指向虚函数表

子类首先会继承一份vfptr和虚函数表, 当子类重写父类的虚方法时, 会覆盖掉子类虚函数表中的父类虚函数。

纯虚函数 virtual 返回值类型 函数名(参数列表)= 0;

有纯虚函数的类为抽象类,抽象类无法实例化,子类必须重写,否则也成为抽象类。

虚析构和纯虚析构函数

父类的指针指向子类的对象在析构的时候不会调用子类的析构函数,如果子类有在堆中申请空间,容易造成内存泄漏。

用虚析构就可以解决上述的问题

纯虚析构也可以解决,不过会导致该类成为抽象类,不能实例化而且需要有函数定义。

文件操作

需要引入头文件 #include<fstream>

文件流对象 ofstream ifstream fstream

ofstream ofs;
ofs.open("filepath", ios::out);
ofs<<“hello world"<<endl;
ofs.close();

ifstream ifs;
ifs.open("filepath", ios::is | ios::binary);
if (ifs.is_open()){
    //读取内容,有很多中方式
}
ifs.close();

模板

建立通用的工具,提升代码复用性

template<typename T> //或者写template<class T>
void swap(T& a, T& b){
    T tmp = a;
    a = b;
    b = a;
}

调用过程由自动类型或者显示指定推到来确定

int a = 1, b = 2;
swap(a,b);
swap<int>(a,b);

普通函数和模板函数的区别

  • 普通函数可以发生隐式类型转化(e.g. char -> int)
  • 自动推导不可以隐式自动类型推到
  • 显示指定可以

普通函数和模板函数调用规则(调用存在二义性时)

  • 优先调用普通函数
  • 用空模板参数列表强制调用函数模板 //swap<>(a,b);
  • 函数模板也可以重载
  • 如果模板更好匹配,优先调用函数模板 // 完全匹配>隐式类型推导(char->int)

类模板

template <class T>
class Person{
public:
    T a;
}

类模板没有自动类型推到的方式,必须显示指定 Person<string> p(“小米”);

类模板可以由默认参数 // template<class T, class F = int>

类模板中成员函数在调用时才创建(分文件编写的时候不同版本的编译器可能会产生链接问题,.h 文件(声明) 和 .cpp文件(实现))

类模板与继承

父类时模板,子类需要执行模板具体的类型,否则子类也变成模板类

class Son:public Base<int> {}

class Son:public Base<T> {}

类模板的成员函数的外联实现需要带上模板参数

练手题:实现一个数组的模板类实现数组创建在堆区,写构造函数、拷贝构造,赋值重载、析构函数,尾插函数、删除尾部函数、获得容量、获得大小、重载下表访问

腾讯视频后台实习面试20200605 0611 0615

第一场:0605

编程题:int数组,每个数在0-9之间,如果值允许交换一次,让交换之后的值最大,输出这个值。e.g. 99788 -> 99887

java什么样的东西可以叫做垃圾?

Treemap和Hashmap底层有什么区别?

什么是Hash冲突?

rehash是什么?什么时候扩容?

第二场:0611

在项目中有遇到过什么问题,如何解决的,效果如何,有什么收获和总结。

如果服务器并发任务过多的时候,如何处理保证服务器不容易崩溃?

数据库有几千个字段,要实现自定义导出的功能如何实现?

用户自定义的导出需求可能不会命中索引,会导致慢查询如何规避?

数据库的两种存储引擎的MYSIAM和InnoDB的区别?

B+树有什么特点,为什么不用红黑树?

在内存存储的时候为什么使用红黑树而不使用B+树呢?

B+树和红黑树查找的时间复杂度是多少?

离开框架来说,如果要开发一个服务,你需要开发的是单进程的服务还是多进程的服务,多线程的服务还是协程的服务,这几种选择有什么区别?如何选择?选择的原则是什么?

多进程和多线程如何选择?

TCP和UDP的差别,启动服务选择那种?选择的依据是什么?

TCP的四次回收的time wait阶段是什么?

time wait是主动发起方的状态还是被动方的状态?

编程题:实现字符串数组的排序(字符串比较函数和排序函数)

第三场:0615

上来就是简单介绍下几个项目,聊了聊硕士期间研究方向的东西

项目的问题:简单介绍一下项目(主要是增删改查)

日志的功能是如何实现的?

删除功能是真正使用delete的SQL语句吗?

项目中的权限管理的功能是如何实现的?权限如何指派,是否有从用户中抽象出角色的概念?

字节跳动-教育实习视频面试20200604

编程题1:输入一个数组,每个元素都是10以内的整数,连接在一起表示一个整数,通过调整顺序,获得一个比原来大的最小的数。

Leetcode 31. 下一个排列

编程题2: 3+3*5-1 表达式中只有三中运算符号,加号减号和乘号。在这个表达式中加上括号会产生多少种结果。

数据库用的是单库还是集群?有多少张表?

客户端发出SQL语句到收到结果大概都经历了那些过程?

数据库的客户端和服务器交互的过程中的是单工的还是双工的还是半双工的?

数据库建立的连接是TCP还是UDP?TCP连接有什么特点?可靠的连接怎么理解?可靠有哪些特点?滑动窗口主要用来解决什么问题?

什么时候需要选择TCP,什么时候选择UDP?

拓扑排序的BFS与DFS实现

以Leetcode 210. 课程表 II 为例题大致讲解一下两种搜索算法的思路。

广度优先搜索,实际上就要结合入度表来进行拓扑排序,入度表需要遍历整张图来计算得到。

之后需要维护一个队列,队列中入度为0的节点,当这个节点出队的时候就要将这个点所指向的所有节点的入度都减1,如果某个指向的节点入度为0了,则将它加入队列中。

可以用计数器记录出队的节点数目,用来最终判断是不是可拓扑排序的,如果是可拓扑排序的,按照出队的顺序也可以构成拓扑序列。

DFS广度优先搜索来处理拓扑排序不是特别好理解。首先说说如何用DFS判断是否可以进行拓扑排序。如果有向图中存在环,则无法拓扑排序。关键是如何判定存在环,那么使用dfs需要维护节点的三种状态,一种是未访问,一种是正在访问,一种是访问结束。

如果访问结束的话,就可以将这个节点,加入到结果中,由于最先访问结束的节点肯定是最后的,所以要用一个栈的数据结构来维护拓扑排序序列。如果当前访问的节点存在某个邻接节点处于正在被访问的一个状态,那么就可以说明存在环。具体的实现过程可以用DFS函数的返回值来巧妙的构造不同情况的判别。

        public int[] findOrder(int numCourses, int[][] prerequisites) {
        //构建邻接表、状态数组( 0:未访问 1:正在访问 2:访问结束)和存储拓扑序列的栈
        HashMap<Integer, ArrayList<Integer>> hm = new HashMap<> (numCourses);
        Deque <Integer> stack = new LinkedList<Integer> ();
        int [] visited = new int[numCourses];
        for (int i = 0; i < numCourses; i++) hm.put(i, new ArrayList<Integer> ());
        for (int[] prerequsity : prerequisites) {
            int to = prerequsity[0];
            int from = prerequsity[1];
            hm.get(from).add(to);
        }

        //DFS过程,DFS返回值是false说明存在环,全部为true的话,结果都存在stack里面
        for(int i = 0; i < numCourses; i++) {
            if (visited[i] == 0) {
                if (!dfs(hm, visited, stack, i)) return new int[0];
            }
        }
        //从栈中取出数据,为了省点空间直接塞到状态数据里面了
        int i = 0;
        while(stack.size() != 0){
            visited[i++] = stack.pollLast();
        }
        return visited;
    }

    public boolean dfs(HashMap<Integer, ArrayList<Integer>> hm, int [] visited, Deque<Integer> stack, int i) {
        //能进入这个函数的肯定是0状态(未访问)的节点,首先更新到1状态(正在访问)
        visited[i] = 1;
        for (int adj : hm.get(i)) {
            //邻接节点处于1状态则说明存在环
            if (visited[adj] == 1) return false;
            //邻接节点未访问,但是从该邻接节点开始的DFS搜索检测到环
            if (visited[adj] == 0 && !dfs(hm, visited, stack, adj)) return false;
            //邻接节点处于访问结束状态不处理
        }
        //顺利访问完成的结果入栈,更新结果状态,返回true
        stack.offerLast(i);
        visited[i] = 2;
        return true;
    }

Prim kruskal 最小生成树算法和并查集

prim算法的思路比较简单,是一种贪心策略,也有严格的数学证明,证明这种算法是正确的(反证和归纳)

思路:随机选一个点作为开始,每次选择权重最小的那条边和连接的节点加入最小生成树。

实现过程中需要可以利用优先队列这种数据结构来对动态添加的候选边进行临时存储以提高效率。

kruskal算法的思路也是贪心的,也有严格的数学证明。

思路:首先对所有的边按照权重进行排序,选择权重最小的那条边作为初始化的边集合。便利按照权重排序好的边,如果某条边的两个节点属于两个不同的联通分量,则将这条边加入最小生成树,并合并这两个连通分量。

具体的实现过程会用到并查集这种数据结构,也可以认为它是一颗二叉树,实际编码过程中可以用数组来存储这种并查集的结构,数组的值就代表父亲节点的索引。

并查集练习:Leetcode 990. 等式方程的可满足性

跟谁学 2020-0603 视频面试 java后台开发

解释变量的值传递和地址传递

static 修饰符有什么作用

jvm 堆栈结构有哪些,静态变量放在什么位置,虚拟机栈内部结构,基本数据类型变量值存放的具体位置

Hashmap底层数据结构、何时扩容,为什么用红黑树,数组长度为什么是2的幂次

Hashmap是线程安全的吗,成环的现象如何理解?ConcurrentHashmap的结构,JDK8中的改进是什么。

线程池有了解吗,线程池的参数都有哪些

解释一下BIO和NIO的区别,如何理解阻塞

AOP是什么解释一下

Spring中的对象生命周期是怎么样的

vim中如何撤销操作

Mysql默认的隔离级别是什么

简单介绍一下索引

最左匹配原则是什么意思

TCP的三次握手,为什么不是两次握手?

手撕算法:不用额外空间的前提下,删除一个int数组中的值为target的所有元素,并把剩余元素全部整理到数组前端,后段空余的位置补零