八股
1、数组和链表的区别
2、Hashmap的实现
3、什么是线程
4、什么是线程安全
5、进程的通信方式
6、什么是死锁,造成死锁的条件
算法
1、删除链表倒数第k个结点(注意边界条件,倒数第一个,第一个)
2、判断括号的合法性
3、多次买卖的股票最大利润
答案
八股
1、数组和链表的区别
1)数组连续空间,链表非连续空间
2)数组查找O(1),链表查找O(n)
3)数组增删O(n),链表增删O(1)
4)数组适合多查找少增删,链表适合多增删少查找
2、Hashmap的实现
1)对key作哈希计算,决定存储在哪个数组
2)不同元素会计算到相同的值,造成哈希冲突
3)哈希冲突的解决办法,开链法,随机探寻,再次哈希
4)STL的Hashmap达0.75容量进行2倍扩容
3、什么是线程
1)一个进程有多个线程
2)进程是资源分配的单位,线程是资源调度的单位
3)线程只有很少属于自己的数据结构
4)同个进程的线程通过读写同一块内存空间进行通信
4、什么是线程安全
多个线程对同个内存空间进行读写时,保证内存空间数据的一致性
线程同步的方式:互斥量,条件变量,互斥锁,读写锁
5、进程的通信方式
管道、消息管道、共享内存、信号、信号量、套接字
6、什么是死锁,造成死锁的条件
1)进程无法得到资源而循环等待
2)系统资源不足,分配不当,进程推进顺序不当
3)互斥,请求保持,占有不剥夺,循环等待
7、C++的特性
1)封装——代码模块化
2)继承——代码重用
3)多态——基类指针指向不同子类实现相同函数不同动作
算法
1、删除链表倒数第k个结点(注意边界条件,倒数第一个,第一个)
快慢指针,一个while循环
虚拟头结点防止删除的是头结点 pre slow fast fast移动到k fast移动到链表尾部 slow指向删除元素 pre->next=slow->next;
2、判断括号的合法性
左括号入栈,右括号判断是否为空,不为空判断栈顶是否匹配
3、多次买卖的股票最大利润
贪心解决,只要股票升就买
if(prices[i]>prices[i-1]) ans+=prices[i]-prices[i-1]
全部评论
(7) 回帖