数据结构与算法 常见面试题

数据结构与算法 常见面试题

二分查找

搜索区间的概念：

如果是左闭右闭空间，那么跳出循环的条件为搜索区间为空，那么Left>Right时才返回

下面是基本二分查找、左边界二分查找、右边界二分查找

如何从所有很多的ip地址中快速找个某个ip地址

如何求一个数的平方根

​​开根号​​

​​162. 寻找峰值​​

递归

非递归

排序算法

各自的性质，甚至优化，手撕快排，归并等

​

快排：

​

冒泡：

​

归并：

​

​​数组中的逆序对​​

桶排序

void BucketSort(vector& vec){ int max = vec[0]; int min = vec[0]; // 确定元素的最值 for (auto it : vec) { if (it > max) max = it; if (it < min) min = it; } // 桶数: (max - min) / array.length的结果为数组大小的倍数（最大倍数），以倍数作为桶数 // 【注意1】当序列大小vec.size()比较小，而元素值很大且分散(max - min比较大)，会造成很多“空桶”, 增加系统开销 // 比如(0, 13, 19892)——> 很多“空桶” // 【注意2】：当待排序序列元素个数很多(vec.size()很大), 但是每个元素却又很小时, 只有一个桶, 这种情况比较耗时 int bucketNum = (max - min) / vec.size() + 1; // 初始化桶, 可以用数组实现, 也可以用vector实现, 这里选取vector实现, 原因下述 // int** buckets = new int*[bucketNum]; // 数组实现桶，需要二维数组 vector > vecBucket; // vector容器实现桶，类似二维数组 // 桶初始化 for (size_t i = 0; i < bucketNum; i++) { vector vecTmp; vecBucket.push_back(vecTmp); } // 用数组实现桶初始化 // for (size_t i = 0; i < bucketNum; i++) // { // buckets[i] = new int[vec.size()]; // 每个桶最多存放vec.size()个元素 // } // 将待排序元素挨个放入对应桶中 for (size_t i = 0; i < vec.size(); i++) { // 和上面【注意】结合看，如果只有1个桶, 要分开处理 if (bucketNum == 1) { vecBucket[0].push_back(vec[i]); } else { int bucketIndex = (vec[i] - min) / bucketNum; // 确定存放在哪个桶 bucketIndex = bucketIndex >= bucketNum ? bucketNum - 1 : bucketIndex; vecBucket[bucketIndex].push_back(vec[i]); // 这是用vector实现桶的好处, 直接“接”在后面自动扩容即可, 数组实现还需代码处理 } } vec.clear(); // 遍历“桶组合”, 给每个桶中元素排序 // 每个桶元素有序了, 则整个“桶组合”从“编号小”的桶遍历到“编号大”的桶，则为整体有序序列 for (vector >::iterator iter = vecBucket.begin(); iter != vecBucket.end(); iter++) { vector vecTmp = *iter; // *iter也是一个vector, 内部存放了该桶内元素 if (vecTmp.size() <= 0) { continue; } // 对每个桶进行排序, 这里借用选择排序 // 当n较小时，对稳定性不作要求时宜用选择排序 //SelectSort(vecTmp); sort(vecTmp.begin(),vecTmp.end()); for (auto it : vecTmp) { // 每个桶内元素有序后, 重新给vec赋值, 此时vec有序。 vec.push_back(it); } }}

链表

链表的查找、定位、反转、连接

两个链表如何判断有环

快慢指针：

首先创建两个指针1和2（在java里就是两个对象引用），同时指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针1每次向下移动一个节点，让指针2每次向下移动两个节点，然后比较两个指针指向的节点是否相同。如果相同，则判断出链表有环，如果不同，则继续下一次循环。

例如链表A->B->C->D->B->C->D，两个指针最初都指向节点A，进入第一轮循环，指针1移动到了节点B，指针2移动到了C。第二轮循环，指针1移动到了节点C，指针2移动到了节点B。第三轮循环，指针1移动到了节点D，指针2移动到了节点D，此时两指针指向同一节点，判断出链表有环

队列与栈

让面试者利用队列写一个多线程下的生产者和消费者程序，全面考察的多线程的资源同步与竞态问题

函数调用实现来问。即函数如何实现的，包括函数的调用的几种常见调用方式、参数的入栈顺序、内存栈在地址从高向低扩展、栈帧指针和栈顶指针的位置、函数内局部变量在栈中的内存分布、函数调用结束后，调用者和被调用者谁和如何清理栈等等。

树

二分搜索树

avl树

红黑树

红黑树的概念、左旋右旋的方式、分析出查找和插入的平均算法复杂度和最好最坏时的算法复杂度

哈希表、哈希函数、哈希冲突、

B类树

MySQL 索引实现原理

图

深度优先和广度优先问题

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。