1.青蛙叫class Solution {public:int minNumberOfFrogs(string croakOfFrogs) {if(croakOfFrogs.size()%5!0)return -1;vectorintcounts(5,0);unordered_mapchar,inthash{{c,0},{r,1},{o,2},{a,3},{k,4}};int res0;int curr0;for(int i0;icroakOfFrogs.size();i){if(croakOfFrogs[i]c){counts[0];curr;resmax(res,curr);}else{int khash[croakOfFrogs[i]];if(counts[k-1]0)return -1;counts[k-1]--;counts[k];if(k4){curr--;counts[k]--;}}}if(counts[0]0||counts[1]||counts[2]||counts[3])return -1;return res;}};总结这里的hash的初始化方法不是用:学到了另外得判断最后的这个。2.最长回文串class Solution {public:string longestPalindrome(string s) {int low0,high0,max_len0;int ns.size();vectorvectorbooldp(n,vectorbool(n));for(int in-1;i0;i--){for(int ji;jn;j){if(s[i]s[j](j-i1||dp[i1][j-1])){dp[i][j]true;if(j-imax_len){max_lenj-i;lowi;highj;}}}}string res;for(int ilow;ihigh;i)ress[i];return res;}};总结这里可以不使用dp可以对每个位置当成中间点去判断奇数回文串、偶数回文串是不是可以八股总结1.B树和红黑树的区别是什么为什么mysql索引不使用红黑树红黑树是二叉平衡搜索树B树是多路平衡搜索树b树相比红黑树可以减少磁盘io次数便于范围查找顺序查询。2.为什么b树的叶子节点有双向链表非叶子节点有吗b树的叶子节点存储数据或者指针按照key有序排列使用双向链表便于按照两个方向的顺序查找便于范围查找非叶子节点是用于向下索引叶子节点没有横向查找的场景不需要双向链表。3.事务的四个特性是什么都是怎么保证的事务的四个特性是原子性、一致性、隔离性、持久性原子性是通过undolog实现的存储旧值或者反向操作隔离性 通过mvcc临键锁等实现mvcc保证了快照读临键锁是为了当前读持久性是通过redolog实现的是预写日志是可以用来掉电恢复。一致性是通过aid通过数据库约束和业务逻辑实现的。4.关于死锁的四个条件和解决方法四个条件分别是互斥、请求和保持、不剥夺、循环等待解决方法有死锁预防破坏四个条件之一比如固定顺序申请资源、一次申请资源破坏请求和保持死锁避免可以通过银行家算法死锁检测和恢复可以使用资源分配图检测然后终止进程回收资源回滚事务除此之外也可以用鸵鸟策略忽略死锁。5.静态库和动态库的区别静态库和动态库的区别主要是链接时机和共享方式不同静态库在链接时被复制到可执行文件可能在多个程序重复包含文件更大更新需要重新编译动态库在链接时只记录依赖在运行时加载动态库多个程序可以共享可能出现动态库缺失或者版本不兼容的问题。6.staticstatic的作用static作用于局部变量会使得变量具有静态存储期只初始化一次程序退出时消亡作用域不变作用于全局变量会改变变量链接属性变成文件私有static作用于类的成员会使得和类绑定多个对象共享同一份作用于成员函数会使得不和对象绑定没有this指针只能访问类的static成员7.多态的种类和实现原理我复述一遍多态分成静态多态和动态多态静态多态发生在编译期通过函数重载、运算符重载、模板实现具体通过类型和模板实例化类型去决定调用哪个动态多态通过虚函数实现父类虚函数子类重写在使用基类的指针或者引用调用子类的方法时去决定具体执行。通过虚函数表和虚函数表指针实现虚函数表存储指向虚函数的指针虚函数表是含有虚函数的类有一个然后每个对象会有一个虚函数表指针通过虚函数表指针找到虚函数表找到虚函数执行