链表反转 原地反转、头插法、递归 LeetCode 206 剑指offer 24 Java实现

    //双指针法(原地反转)
    public ListNode reverseList1(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode pre = null, cur = head, next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    //头插法
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode();
        while (head != null) {
            ListNode next = head.next;
            head.next = dummy.next;
            dummy.next = head;
            head = next;
        }
        return dummy.next;
    }

    //递归法
    public ListNode reverseList3(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead =  reverseList(head.next);
        head.next.next = head;
        //这一句实际上执行一次就够了,
        head.next = null;
        return  newHead;
    }

    //递归法优化
    public ListNode reverseList4(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = helper(head);
        head.next = null;
        return newHead;
    }

    public ListNode helper(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = helper(head.next);
        head.next.next = head;
        return newHead;
    }

二分图(二部图)判别和最大匹配问题(匈牙利算法)

二分图(二部图)

如何判断一个图是否是二分图,二分图就是可以将图分为两个部分,边都是在两个部分之间,而每个部分内部不可以有边相连。

这样如果二部图中存在一个环,那么这个环中的边数必须是偶数,可以画图验证一下三角形、四边形和五边形就知道了。

那么环中的边数是偶数,就可以利用染色算法来进行判别,环是偶数则两种颜色可以交替,否则必定有两个相邻的节点颜色相同。

可以利用BFS算法(结合队列)对二分图进行判别。关键代码如下:

输入:

7
1 4
1 5
1 6
2 5
3 5
3 6
3 4
2 6
 public static void main(String[] args) throws Exception{
       
        Scanner sc = new Scanner(System.in);
        //读入数据,并构建邻接表
        int n = sc.nextInt();
        int [] colors = new int[n];
        HashMap <Integer, ArrayList<Integer>> hm = new HashMap<>();
        for (int i = 0; i < n; i++) {
            hm.put(i, new ArrayList<>());
        }
        while (sc.hasNext()) {
            int forward = sc.nextInt();
            int backward = sc.nextInt();
            hm.get(forward).add(backward);
            hm.get(backward).add(forward);
        }
        System.out.println(hm);
        //这里节点的标识与数组的下表一一对应,也是为了简化问题,如果不是一一对应的情况,可能还需要做一次 index -> node 的转换

        for (int i = 0; i < n; i++) {
            int color = colors[i];
            if (color == 0) {
                boolean valid = BFS(hm, colors, i);
                if (!valid) {
                    System.out.println("not valid");
                    System.out.println(Arrays.toString(colors));
                    return;
                }
            }
        }
        System.out.println("valid!");
        System.out.println(Arrays.toString(colors));
    }

    public static boolean BFS(HashMap<Integer, ArrayList<Integer>> hm, int [] colors, int node) {
        LinkedList<Integer> queue = new LinkedList<>();
        colors[node] = 1;
        queue.offerLast(node);
        while(queue.size() != 0) {
            int curNode = queue.pollFirst();
            for (int neighber : hm.get(curNode)) {
                if (colors[neighber] == 0) {
                    colors[neighber] = - colors[curNode];
                    queue.offerLast(neighber);
                } else if (colors[neighber] == colors[curNode]){
                    return false;
                }
            }
        }
        return true;
    }

二分图中一个很重要的问题就是最大匹配问题,最大匹配问题利用匈牙利算法进行求解。

输入:

8
1 1
1 2
2 2
2 3
3 1
3 2
4 3
4 4

关键代码如下:

    static int maxn = 100;
    //通过邻接矩阵进行图构建
    static int [][] matrix = new int[maxn][maxn];
    static boolean [] used = new boolean[maxn]; //表示某个轮次中女生是否被匹配过,每轮都初始化
    static int [] nxt = new int[maxn];  //表示整个过程中与女生匹配的男生id ,nxt[1]=2, 表示女1和男2匹配
    static int n = 5;  //表示男生数量为4(数值多1是为了和输入的id从1开始相匹配)
    static int m = 5;  //表示女生数量为4
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        //构建邻接矩阵
        int k = sc.nextInt();
        for (int i = 0; i < k; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            matrix[a][b] = 1;
        }
        
        //开始遍历每个男生,尝试为每个男生匹配女生
        int res = 0;
        for (int i = 1; i <= n; i++) {
            //每轮都要初始化女生是否匹配数组,因为dfs(递归)找增广路的时候需要标识来调整策略
            used = new boolean[m];
            if (DFS(i)) res ++;
        }
        System.out.println(res);
    }
    
    //这个方法是匈牙利算法的核心,函数标识在当前情况下,是否(返回值)能为男x成功匹配到女生。该函数还会修改每次初始化的used数组和nxt全局数组。
    public static boolean DFS(int x) {
        //遍历每个女生看看能不能和男生x匹配上
        for (int i = 1; i <= m; i++) {
            // 如果该女生和男生x存在可匹配的边,并且女生在这一轮没有匹配过
            if (matrix[x][i] == 1 && !used[i]) {
                //标识此轮中该女生被从尝试匹配过,防止递归找增广路的时候重复访问(增广路不是环,因此不能重复访问)
                
                used[i] = true;
                //如果这次循环没有找到,会对其他轮次的循环造成影响吗,因为你修改了used数组
                //不会,因为如果存在一条增广路,经过了上次不成立的增广路,那么上次的也是一条增广路,产生矛盾。

                //如果当前女生没有匹配的男生 || 当前女生有匹配的男生,并且可以让那个匹配的男生去找一个新的女生
                if (nxt[i] == 0 || DFS(nxt[i])) {

                    nxt[i] = x;
                    return true;
                }
            }
        }
        return false;
    }

单单看代码注释还是很难理解,可能过一阵子就忘了,结合代码单个步骤调试会更加形象,后面有空整一个视频讲解吧。

参考文献

私钥、公钥、数字签名、数字证书

一些概念:公钥 与 私钥 、摘要、数字签名、数字证书

利用一个公认的证书颁发机构记录信息发布者的公钥信息(防止公钥被伪造),同时这个信息用这个公信机构的私钥进行加密,信息发布者就在自己的签名(摘要+私钥加密)的基础上额外附带自己的数据证书。

接收方收到数据后,如果认可证书管理机构,就用改管理机构的公钥将数字证书解密,得到信息发布者的公钥,进一步通过改公钥解密数字签名获得摘要,最后通过摘要验证收到的信息是否一致。

公钥私钥的两种应用场景

  • 加密,那肯定是不希望别人知道发送给我的消息,所以只有我才能解密,所以可得出别人用公钥负责加密自己用私钥负责解密
  • 签名,那肯定是不希望有人冒充我发送消息,只有我才能发布这个签名,所以可得出自己用私钥负责签名,别人用公钥负责验证是我发送的消息

私钥和公钥是一对,谁都可以加解密,只是谁加密谁解密是看情景来用的:
第一种情景是签名,使用私钥加密,公钥解密,用于让所有公钥所有者验证私钥所有者的身份并且用来防止私钥所有者发布的内容被篡改(摘要用私钥加密,公钥持有者解密后可以验证摘要一致性).但是不能来保证内容不被他人获得(公钥大家都有)。
第二种情景是加密,用公钥加密,私钥解密,用于向公钥所有者发布信息,这个信息可能被他人篡改(中间截获信息进行修改),但是无法被他人获得(无法获取明文)。

https://blog.csdn.net/qq_23167527/article/details/80614454

https://blog.csdn.net/mengzuchao/article/details/78682060

数据库事务的ACID和隔离级别

数据库事务的ACID四个基本特性

  • 原子性(Atomicity)
  • 一致性(Consistency)
  • 隔离性(Isolation)
  • 持久性(Durability)

通俗解释:原子性就是一个事物,要么就全部都执行,要么到就全部都不执行;一致性是指执行事务前后数据库都要保持一致性状态(满足主键约束、业务逻辑约束等);隔离性是指数据库一个事务的执行不受=其他事务的影响, 持久性是指事务一旦提交所做的更改是永久的。

数据库事务并发的三种问题:

脏读:一个事务在执行的过程中读到了另一个事务还未提交的修改。

不可重复读:事务A读到了一个输入,然后事务B对这个数据进行修改并提交,事务A1重新读取这个数据的时候发现不一致(针对update)

幻度:事务A通过一定的条件读到了一批数据,在这期间事务B对符合这个条件的数据进行了删除或者插入,那么数据A重新读到某条件下的一批数据时,数据的条数变化了(针对delete和insert)

数据库事务的四种隔离级别

  • 读未提交(Read Uncommitted)
  • 读提交(Read Committed)
  • 可重复读(Repeated Read)
  • 串行化(Serializable)

读未提交:可以读到未提交的内容;会产生“脏读”、“不可重复读”、“幻读”。如无特殊情况,基本是不会使用这种隔离级别的。

读提交:只能读到已经提交的内容。是SQL Server和Oracle的默认隔离级别。这种隔离级别能够有效的避免脏读,无法避免“不可重复读”和“幻读”。

可重复读:专门针对“不可重复读”这种情况而制定的隔离级别,它就可以有效的避免“不可重复读”(加update锁)(是MySql的默认隔离级别),不能避免“幻读”,因为幻读是由于“插入或者删除操作(Insert or Delete)”而产生的。

串行化:这是数据库最高的隔离级别,这种级别下,事务“串行化顺序执行”,“脏读”、“不可重复读”、“幻读”都可以被避免,执行效率差,开销大。

总结下面内容摘自: https://baijiahao.baidu.com/s?id=1611918898724887602&wfr=spider&for=pc

为什么会出现“脏读”?因为没有“select”操作没有规矩。

为什么会出现“不可重复读”?因为“update”操作没有规矩。

为什么会出现“幻读”?因为“insert”和“delete”操作没有规矩。

“读未提(Read Uncommitted)”能预防啥?啥都预防不了。

“读提交(Read Committed)”能预防啥?使用“快照读(Snapshot Read)”,避免“脏读”,但是可能出现“不可重复读”和“幻读”。

“可重复读(Repeated Red)”能预防啥?使用“快照读(Snapshot Read)”,锁住被读取记录,避免出现“脏读”、“不可重复读”,但是可能出现“幻读”。

“串行化(Serializable)”能预防啥?排排坐,吃果果,有效避免“脏读”、“不可重复读”、“幻读”,不过效果谁用谁知道。

参考资料:

https://baijiahao.baidu.com/s?id=1611918898724887602&wfr=spider&for=pc

字节抖音客户端提前批一面20200712

设计模式有了解那些?

写单例模式的代码

Java的四种引用类型

进程和线程的区别

volitile关键字是什么意思

进程中的sleep/wait/join/yeild方法分别有什么作用

Android有了解吗?安卓上的MVC、M什么的有了解吗?

一个ArrayList<String str> 里面删除所有特定的字符串要怎么做

编程题:

求两个单链表的交叉点

常见排序算法的稳定性分析

稳定性简而言之就是带相同元素在排序前和排序后的相对位置是否保持一致。

默认从小到大的进行排序

1.冒泡排序

思想:每一轮都是将最大的一个元素冒到数组的结尾。

分析:当相邻的两个元素相等的时候,通常的做法应该是选择后面的那个相同元素继续做冒泡的比较,这样稳定性就不会被破坏。但是如果你在两个相邻元素相同的时,还是选择了交换两个相同的元素,这样稳定性就会遭到破坏,当然没有人会这么多此一举,所以通常默认情况下,因此冒泡排序就是一个稳定的排序算法。

2.选择排序

思想:每一轮选择最小的值所在的下边,确定之后交换到特定位置

分析:举个反例 5,4,5,3 排序,第一轮之后 3,4,5,5 。两个5的相对位置发生了变化,因此选择排序不稳定

3.插入排序

思想:维护数组前部分有序,当前元素插入到合适的位置。

分析:如果再向前找的过程中发现相同元素,则插再这个相同元素的后面,这样相同元素的相对位置不发生变化,是一种稳定的排序算法。但是如果你找到相同元素的时候,硬是要插入到前面,那么就是不稳定了,这里的稳定是默认你不会做这么无聊的操作了。

4.快速排序

思想:主元+分治

分析:举一个反例:3,2,2 第一轮3作为主元,变成 2,2,3 ,这样就可以认为排好序了。两个2的相对位置发生了变化,一种不稳定的排序算法。

5.归并排序

思想:分治与归并

分析:元素的交换只发生的归并的阶段,就是merge两个有序的小数组的过程。归并的过程中需要借助辅助数组。两个有序数组中,小的数排前面,当遇到相同的数的时候,则左边数组的数先排,这样就可以保持相对位置。因此是一种稳定的算法。如果你非要先排右边数组的元素,那么就破坏了稳定性,当然也是需要考虑到你不会这么做。

其他排序算法:

桶排序(基数、计数):稳定

堆、希尔:不稳定

上述提到的稳定算法基本上都是理想上可以达到的,当程序员的实现上不严谨的时候,会导致稳定的排序算法变成一种不稳定的排序算法。

工程中的排序算法

工程中类库提供的排序都是经过高度集成与优化的,时间复杂度O(NlogN)的算法都涉及到递归的操作,工程中是不允许出现递归,递归排序都被改写成了非递归的。

Java中的Arrays.sort方法会先判断数据的长度,如果数据在一定范围内,会直接使用插入排序,因为插入排序虽然是一个时间复杂为O(N²)的排序算法,但是如果数据量并不是很大,那么相对来讲很快,并且插入排序的特点就是如果一个数据近似有序,那么时间复杂度也近似O(N)。如果数据量较大,那么Arrays.sort方法会再判断排序的data是基础类型还是一个自己定义的对象,如果是基础类型,那么会使用快排,因为基础类型要保持稳定性是无意义的,如果是对象例如自己定义的类Student,那么就会使用归并排序,保证data的稳定性。无论是归并排序还是快速排序,当数据量被分解到一定范围时,会再次转换为插入排序 。

参考文献:

https://blog.csdn.net/wumenglu1018/article/details/106712801

https://www.jianshu.com/p/a5b5b5c4ee0f

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?