C++ 复习 STL库

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

Standard Template Library(标准模板库)

STL从广义上分为:容器、算法和迭代器 (container、algorithm、iterator)

容器之vector

三种遍历方法

#include<vector>
vector<int> v;
v.push_back(10);
vector<int>::iterator itBegin = v.begin(); //第一个元素的地址(指针)
vector<int>::iterator itEnd = v.end();    //最后一个元素的下一个元素的地址(指针)
while (itBegin != itEnd) {
    cont << * itBegin << endl;
    itBegin++;
}

for (vector<int> ::iterator it = v.begin(); it != v.end(); it++){
    cout<<*it<<endl;
}
#include <algorithm> //标准算法头文件
void myPring(int val){ cout<<val<<endl;}
for_each(v.begin(), v.end(), myPrint); //这里采用了回调函数的技术

自定义类型的容器

vector<Person> v;
for(vector<Person>::iterator it = v.begin(); it != v.end(); it++){
    cout << (*it).name << endl;
}
vecter<Person*>v;
for(vector<Person*>::iterator it = v.begin(); it != v.end(); it++){
    cout << (*(*it)).name << endl;
    cout << (*it)->name <<endl;
}

容器可以嵌套

vector<vector<int>> v;
for (vector<vector<int>>::iterator outerIt = v.begin(); outerIt != v.end(); outerIt ++) {
    for (vector<int> ::iterator innerIt = (*outerIt).begin(); innerIt != (*outerIt).end(); innerIt ++ ) {
        cout << *innerIt << " ";
    }
    cout<<endl;
}

string类,底层就是通过char*来实现的(字符串的字面量实际上时const char * 类型的)

string的四种构造函数

  • string()
  • string (const char * c)
  • string(const & string str)
  • string(int n, char a)

string类内部重载=赋值运算符,还重载了多个,还有提供了assign以及重载的多个方法。

string类内部还重载+=等拼接字符串的方法,还提供了append一些列重载函数。

string类的查找函数find,rfind,一个从左往右找,一个从右边往左边查,并且重载了一系列。

string类的替换函数replace,详细函数的定义需要查查文档。

字符串比较 int compare(const & str)

字符串重载[]实现字符的读写,也提供了at函数提供访问。(这和java不同)下面两种都是合法的。

  • str[1] = ‘a’;
  • str.at(1) = ‘b’;

字符串插入删除 insert() erase()方法

字符串的字串 subStr()

vector

是一个动态的数组,有以下四种方式的构造函数

  • vector()
  • vector(v.begin(), v.end())
  • vector(int n, element)
  • vector(const vector & v)

vector容器可以赋值(重载了operator=),也可以调用assign方法

vector的size() capacity() empty() resize()方法

vector的插入和删除

push_back() pop_back() insert() erase()

vector元素存储 重载[]运算符,调用at(), front() 第一个元素,back()最后一个元素

vector容器的swap()方法

看得懂这个代码吗 vector<int>(v).swap(v)

调用拷贝构造函数创建匿名对象并实现vector的内容交换,一定程度上会节省v中capacity多余的空间浪费,而匿名对象会被系统回收。

reserve()函数,预留空间,减少动态扩容是的复制数据的开销。

deque容器

双端队列 #include<deque>

头部插入的效率高于vector,具体需要数据结构看底层源码

vector访问元素的速度会比deque快

API基本和vector类似,只是多了一些在头部的方法

deque没有capacity()方法,和底层实现有关(中控器)

//deque容器的排序
#include <algorithm>
sort(d.begin(), d.end())

stack容器

#include<stack>

stack<T> stk; stack<T>(const & stack stk); 普通构造和拷贝构造

pop push top 三个方法

size empty 方法

queue容器

#include<queue>

queue<T> que; queue<T>(const & queue que);

pop push front back 方法

size empty 方法

list容器

list表示链表(注意和java中的区别),c++底层实现是双向循环列表

多数的API和vector差不多,但是没有capacity的概念,不支持[] 和at访问,l.begin() 只能++或者– 不能 +=1 +=2 之类的(不支持随机访问)

反转和排序 list<int> l; l.reverse(); l.sort()

所有不支持随机访问迭代器的容器,不可以使用标准算法,(#include <algorithm>),一般来说这种容器的内部会提供对应的成员方法。

bool compare(int v1, int v2){ return v1 > v2; }
l.sort(compare);   //降序排序

自定义数据类型排序需要指定排序规则。

set/multiset

#include<set>

底层是用二叉树来实现的数据结构,是一种关联式容器

set不允许重复元素,multiset允许重复元素

插入元素只能用insert函数,删除erase,清空clear

find函数返回的是迭代器,count函数非1即0(multiset可能是其他值)

    set<int> s;
    pair<set<int>::iterator, bool> res = s.insert(100);
    if (res.second) {
        cout << "successful insertion!" << endl;
    } else {
        cout << "inserted failed!" << endl;
    }
    res = s.insert(100);
    if (res.second) {
        cout << "successful insertion!" << endl;
    } else {
        cout << "inserted failed!" << endl;
    }

set 的函数返回的结果是pair<iterator, bool> 第二个参数表示是否插入成功。

pair队组

两种创建队组的方式

  • pair<string, int> p(“Amy”, 17);
  • pair<string, int> p2 = make_pair(“Jerry”, 30);

cout << p.first << ” ” << p.second << endl;

set的排序(仿函数)

class MyCompare {
    public:
        bool operator()(int a, int  b) const{
            return a > b;
        }
};

int main() {
    cout << 'a' << endl;
    set<int, MyCompare> s;
    s.insert(1);
    s.insert(2);
    s.insert(3);
    s.insert(4);
    s.insert(5);
    for (set<int, MyCompare>::iterator iter = s.begin(); iter != s.end(); iter ++) {
        cout << *iter << endl;
    }

}

自定义数据类型装入set中必须在创建set的时候,指定仿函数比较器,或者在自定义类中重载比较运算符。

Map容器

#include <map> //一种关联式容器

map里面存的都是队组pair

int main() {
    map<int, int> m;
    m.insert(pair<int, int>(10,10));
    m.insert(make_pair(30,10));
    m.insert(pair<int, int>(20,10));
    for (map<int, int>::iterator iter = m.begin(); iter != m.end(); iter++) {
        cout << iter->first << " " << iter->second <<endl;
    }
}

empty size swap erase(重载多个) clear

查找元素

map<int, int>::iterator iter pos = m.find(key);

函数对象(仿函数)

特点

  • 函数对象在使用时,像普通函数一样调用
  • 函数对象超出普通函数的概念,可以有自己的状态
  • 函数对象可以作为参数传递

谓词

仿函数返回值是bool数据类型,称为谓词。(有些类似java中的函数式接口或者python中的filter)

一元谓词(有一个形式参数)–过滤

二元谓词(有两个形式参数) –排序

内建函数对象

算术仿函数

#include <functional>
negate<int>n; //一元
cout<<n(50)<<endl;
plus<int> q;  //二元
cout<<q(10,5)<<endl;

关系仿函数(greater 最常用)

#include<vector>
#include<functional>
vector<int>v;
sort(v.begin(), v.end(), greater<int>());  //关键在这里
for(vector<int>::iterator it = v.begin(); it != v.end(); it ++) {
     cout << (*it) << endl;
}

逻辑仿函数(基本用不到)

STL常用算法

  • #include<algorithm>
  • #include <numeric>
  • #include <functional>

遍历

for_each(v.begin(), v.end(), 函数或者仿函数);

搬运、转换(类似java8的stream或者python的列表表达式)

trandform(s.begin(), s.end(), d.begin(), 函数或者仿函数); //目标容器需要提前开辟空间

查找:

find (v.begin(), v.end(), int val); //自定义类型需要重写运算符==方法。

find_if(v.begin(), v.end(), 仿函数); //

adjacent_find 查找重复相邻元素的地址

binary_search(v.begin(), v.end(), int val);

count(v.begin(), v.end(), int val);

count_if(v.begin(), v.end(), 一元谓词);

排序

sort(v.begin(), v.end(), 二元谓词);

random_shuffle(v.begin(), v.end());//记得加随机数种子

merge(v1.begin(), v1.end(), v2.begin(), v2.end(), target.begin()); //target需要先开辟,v1,v2需要有序

reverse(v1.begin(), v2.begin());

拷贝和替换

copy(v1.begin(), v1.end(), target.begin()); //先开辟空间

replace(v1.begin(), v2.end(), int old, int new);

replace_if(v.begin(), v.end(), 一元谓词, int new);

swap(v1,v2);//同种类型的容器才能交换

算术生成算法

#include <numeric>
int total = accumulate(v.begin(), v.end(), int start_sum);
fill(v.begin(), v.end(), 100);

“集合”算法

set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), target.begin()) //target的容量需要先开辟,前提必须是两个有序的序列

set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), target.begin()) //target的容量需要先开辟, 要求有序

set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), target.begin()) //target的容量需要先开辟, 要求有序 ,差集有先后顺序关系

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的所有元素,并把剩余元素全部整理到数组前端,后段空余的位置补零

JAVA复习:GC垃圾收集器

学习内容来自尚硅谷宋红康老师的JVM教程

https://www.bilibili.com/video/BV1PJ411n7xZ/

垃圾是什么?指运行程序中没有任何指针指向的对象

不清理垃圾有什么后果?垃圾对象占用内存空间,容易内存溢出。

内存溢出和内存泄露的区别,

  • 内存溢出很容易来理解, 内存不够用,是指在程序申请内存时,没有足够的内存提供就出现了内存溢出
  • 内存泄漏 但是程序在申请内存后,无法释放已申请的内存空间 如java的数据库连接或者网络连接没有及时close。
  • 当内存泄露越来越多的时候,最终会导致内存溢出

JAVA 的垃圾回收机制

自动内存管理,(分配和回收)开发人员就不同过多关注内存的分配和释放,降低了内存的泄露和溢出。

java堆是垃圾回收的重点。青年区->老年区->永久代 回收频率依次减少

垃圾回收的算法

垃圾标记阶段:引用计数算法和可达性分析算法

引用计数器算法,每个对象保存一个整形的应用计数器,记录对象自身被引用的次数。

优点:实现简单,垃圾对象容易识别,判定效率高,回收没有延迟

缺点:额外的空间,更新计数器额外的时间开销。无法处理循环引用的情况(内存泄露,致命的缺点,因此java没有采用)

可达性分析/根搜索/追踪性垃圾收集算法

对象的finalization机制

对象要被gc回收之前会执行finalize方法,定义在Object类中的方法。可以在里面重写一些资源释放的方法。

但是不要主动去调用这个方法。

对象的三种状态

清除阶段的三种算法:

  • 标记-清除算法
  • 复制算法
  • 标记-压缩算法

标记-清除算法

标记从Gc roots开始遍历,标记所有可达到的对象(在对象的Header中记录为可达对象)

对堆中所有对象进行遍历,清除没有标记的对象。

缺点:效率不高,在进行GC的时候,需要停止整个应用程序,影响用户体验(Stop the world),容易产生内存碎片。需要维护一个空闲列表。

清空就是将对象的地址记录到空闲列表上。

复制算法:

优点:没有标志和消除过程,高效,不会产生碎片问题

缺点:需要两倍内存空间,需要维护对象之间的引用关系,如果大部分对象都不是垃圾,移动对象的时间开销也会很大

标记-压缩(标记-整理)算法

复制算法高效性的前提是垃圾对象多,存活对象少。而这很符合年轻代中数据的特点。但是老年代就不一样了,老年代的数据大部分是存活数据。

优点:没有内存碎片,不需要维护空闲列表,比复制算法空间利用率高

缺点:效率低,要维护对象间的引用,需要STW,影响用户体验

对比

分代收集算法:具体问题具体分析

青年代用复制算法,同时设置伊甸园区和幸存者区缓解内存的浪费。

老年代用标记-清除和标记-整理混合的方法。

增量收集算法:

缺点:造成垃圾回收总体成本提高,系统吞吐量下降。因为切换线程和上下文转换有额外开销。

分区算法:

一些概念:

System.gc() /Runtime.getRuntion().gc(),可能触发Full GC,对老年代和青年代进行回收。但是无法保证立刻调用垃圾收集器,会在程序执行的某个不确定时间节点进行调用。

System.runFinalization(); 会强制调用失去引用对象的finalize方法。

内存溢出 OOM:没有空闲空间,并且垃圾回收之后还是不够。

内存泄露 Memory Leak:对象不会再被程序使用了,但是GC又无法回收了。通常是编码过程的疏忽,导致某些对象的生命周期过长。

内存泄露的两个例子。

STW stop the world 所有的垃圾收集器都会有这个情况。就是把所有用户进程停止,执行垃圾回收。

并发(concurrent)实际上就是同步,某个时刻只有一个程序在执行,只是CPU快速地切换,让我们感觉同时在执行。

并行(Parallel) 同一个时刻,多个程序在真正运行。

  • 垃圾回收的并行:多条垃圾回收线程并行执行。
  • 垃圾回收的串行:只有一个垃圾回收器线程执行。
  • 垃圾回收器的并发:用户线程和垃圾回收线程同时执行。

安全点:

安全区域:

引用(前提都是可达的对象引用)

强引用对象不会被gc回收,也是内存泄露的主要原因。

软引用,内存足够不会回收,内存不够时,在二次gc时被回收。

弱引用:被gc就回收

JDK更新可以从三个层面区关注:

  • 语法层面
  • API层面
  • 底层优化

垃圾回收器的分类:

  • 按线程数分:串行gc和并行gc
  • 按照工作模式:并发式和独占式
  • 按碎片分:压缩式和非压缩式
  • 按工作内存:年轻代gc和老年代gc

GC的性能评估指标

上面标红的三项是主要的,但也是互相制约的。

主要关注前两项

吞吐量与暂停时间的矛盾。

可以在JVM参数中设置Parallel GC的吞吐量或者暂停时间的参数。

JAVA中的数组、链表、队列、栈

首先说一下Java中的集合框架collection是一个接口,、

下面有两大类型的子接口,分别是List和Deque

List下有三大常见的实现类,ArrayList、LinkedList、Vector

其中 ArrayList、Vector 底层都是用数组来实现的, LinkedList底层是用链表实现的

ArrayList非线程安全,Vecotr虽然是线程安全的但是已经被弃用了。

Stack类是早期JAVA为了栈数据结构而设计的一个类,它是vector的子类,但是早期设计的时候考虑的不是特别的完美,因为父类vector是一个线程安全的,意味着效率比较低,同时Vector的上层接口List里面有一个add(index, Element)的方法,被调用会破坏stack的结构,就是在这栈的中间可以随意的插入元素。因此Stack这个类也被弃用了。

Deque 接口顾名思义就是为了实现队列而提供的接口。双端队列。

下面有很多有用的实现类,ArrayDeque、LinekList、PriorityQueue 里面也封装了很多有用的方法。

LinkedList即使List的实现类又是Deque的实现类(底层是链表)因此可以使用它来作为队列或者栈来进行使用。

虽然LinkedList的功能很强大,但是它也是List的实现类,避免不了被错误调用

破坏了栈只能在栈顶操作数据的原则

操作队列或者栈用的方法主要带有offer poll peek + First/Last,而最好不是用add/remove之类的方法或者push/pop之类的方法,容易搞混乱。

这篇文章讲得很好。

https://mp.weixin.qq.com/s/Ba8jrULf8NJbENK6WGrVWg

复习:深度底层理解Java的String

学习内容来自尚硅谷宋红康老师的JVM教程

https://www.bilibili.com/video/BV1PJ411n7xZ/

String的两种创建方式:

  • String s = “abc”; //字面量初始化
  • String s = new String(“abc”); //对象的形式初始化

String类是final的,不可继承

JDK8以及以前版本String的底层是用char[]来进行存储的

JDK9以及以后底层改变为了用byte[]数据进行存储

修改底层结构的字符:String在程序中很常用,并且字符中大部分是拉丁文,即用一个字节就能进行存储,而cahr类型是两个字节的,因此会造成内存空间的浪费。

char[]就改变成了byte[]和对应的编码类型

StringBuilder、StringBuffer、JVM底层处理String的方式自JDK9都做了相应的修改。

String代表不可变的字符序列。

字符串常量池中不会存储相同的字符串。

StringPool 实际是一个固定大小的Hashtable,不能动态修改,常量过多的话Hash冲突会增加。大小可以在JVM的参数上进行定制。

常量池就类似java系统级别的一个缓存,可以让运行速度更快、更节省内存。

JDK6 的时候 字符串常量池在永久代的常量池中,JDK7和JDK8之后都在堆中。

为什么调整?

  • 永久代默认空间比较小,容易溢出
  • 永久代的垃圾回收的频率比较低(或者不回收),字符串回收效率低,也容易溢出

进阶知识

String s = “a” + “b” + “c”;

String s = “abc”

这两句在编译之后是等价的,常量字符串拼接(包括final修饰的变量)是在编译时期进行优化的。即在生成的字节码文件里面是两个一样的字面量“abc”

如果字符串的拼接符号的前后出现了变量,相当于在堆中new了一个String对象。

  • String s1 = “ab”;
  • String s2 = “cd”;
  • String s3 = s1 + s2;
  • String s4 = “abcd”;
  • System.out.println(s3 == s4); // false
  • String s3 = s1 + s2;这一句代码查看底层的字节码可以解释为
    • String tmp = new String();
    • tmp.append(s1);
    • tmp.append(s2);
    • s3 = tmp.toString();

以上导致了对象引用和常量池引用的地址不一致问题。

        String s = "";
        for (int i = 0; i < 10000; i++) {
            s = s + i;
        }
        
        StringBuilder s1 = new StringBuilder();
        for (int i = 0; i < 10000; i++) {
            s1.append(i);
        }

上述代码展示的两种字符串拼接方案,效率千差万别

  • append的方式只有一个StringBuilder对象,而字符串拼接的方式每次拼接都会产生一个新的StringBuilder对象以及String对象
  • 其次 ,第一中方式内存中存在过多stringBuilder和String垃圾,如果进行gc需要花费额外的时间。

进一步提高,StringBuilder可以在初始化的时候指定char[]数组的容量,可以避免扩容过程中带来的性能损耗。即如果逻辑大致确定,可以指定一个capacity的上界,就不会扩容了。

intern函数,返回字符串是字符串常量池中的地址(有就直接返回,没有就“创建”,JDK版本有差别)

new String(“ab”); 这条语句会创造几个对象?

一个对象是new 关键字创建的,另一个对象是字符串常量池中的对象。

new String(“a”) + new String(“b); 呢?从字节码的角度看一共有5个对象

  • new StringBuilder()
  • new String()
  • 字符串常量池中的对象“a”
  • new String()
  • 字符串常量池中的对象”b”

StringBuilder的toString方法中 return new String(value, 0, count);分析对应的字节码,得知并没有在常量池中创建“ab”,

字符串常量池的HashTable中放到是什么?现在的理解存到的就是一个完整的String对象的引用,该对象引用和字面量引用是等价的。而new出来的对象是在堆中的。

面试题:

String s1 = new String("1");
s1.intern();
String s2 = "1";
System.out.println(s1 == s2);           //false

String s3 = new String("1") +  new String("1");
s3.intern();
String s4 = "11";
System.out.println(s3 == s4);       //jdk6:false   jdk7/8:ture

第1部分比较简单,就是s1在对空间中创建了一个字符串一的对象,同时字面量一也在字符串常量池里面创建了一个一的对象,而第2句s1.intern();就相当于什么都没做,第3句的S2通过字面量初始化,指向字符串常量池中的那个对象,所以两个地址是不一样。

第2题就比较难,因为它的输出结果和jdk的版本有关,执行intern语句之前,如果字符串常量池中已经有了,就没什么区别。当字符串不存在常量池中的时候,intern方法在1.6中会在永久代中复制一份String对象,并返回相应的地址。而在JDK7/8中,字符串常量池的位置调整到了堆中,调用intern方法的时候如果常量池中没有,则直接指向堆中已有的那个对象,节省空间。

String s = String.valueOf(123);
System.out.println(s == s.intern());    //jdk8 true
String s3 = new String("1") +  new String("1");
String s4 = "11"; 
s3.intern();
System.out.println(s3 == s4);       //jdk7/8:false
String s1 = new String("a") +  new String("b");
String s2 = s1.intern(); 
System.out.println(s1 == "ab");    //jdk6:false   //jdk7/8:true
 System.out.println(s2 == "ab");   //jdk6:true    //jdk7/8:true

在代码中何时的位置加上intern函数可以在一定程度上节省内存空间。因为字符串常量池中的数据可以复用,重复的String对象就可能被gc回收。