葫芦岛建设工程信息网站,安徽省建设厅网站资料下载,asp模版网站如何做优化,免费申请网站永久系列综述#xff1a; #x1f49e;目的#xff1a;本系列是个人整理为了秋招面试的#xff0c;整理期间苛求每个知识点#xff0c;平衡理解简易度与深入程度。 #x1f970;来源#xff1a;材料主要源于左程云算法课程进行的#xff0c;每个知识点的修正和深入主要参考… 系列综述 目的本系列是个人整理为了秋招面试的整理期间苛求每个知识点平衡理解简易度与深入程度。 来源材料主要源于左程云算法课程进行的每个知识点的修正和深入主要参考各平台大佬的文章其中也可能含有少量的个人实验自证。 结语如果有帮到你的地方就点个赞和关注一下呗谢谢 【C】秋招实习面经汇总篇 文章目录 堆比较器 参考博客 点此到文末惊喜↩︎
堆
完全二叉树的数组表示当前结点下标为i第0位不用从而可以使用移位操作进行快速处理 左孩子 2 ∗ i ⟺ ( i 1 ) 2 * i \iff (i 1) 2∗i⟺(i1)右孩子 2 ∗ i 1 ⟺ ( i 1 ∣ 1 ) 2 * i 1 \iff (i 1 | 1) 2∗i1⟺(i1∣1)父结点 ( i ) / 2 ⟺ ( i 1 ) (i) / 2 \iff (i 1) (i)/2⟺(i1) 堆 通过下沉和上浮操作进行处理
// 插入底部插入结点自底向上上浮
void HeapUp(vectorint vec, int index) {// 若当前结点大于父亲结点则交换while (vec[index] vec[(index - 1) / 2]) {swap(vec[index], vec[(index - 1) / 2]);index (index-1) / 2;}
}// 弹出根节点插入结点自顶向下下沉
void HeapDown(vectorint vec, int index, int heap_size) {int left index * 2 1;while (left heap_size) { // 表示孩子即至少有一个左孩子// 有右孩子 右孩子值大于左孩子 则最大下标为右孩子否则是左孩子int largest left 1 heap_size vec[left1] vec[left] ? left1 : left;// largest中存储自己和左右孩子中最大的largest vec[largest] vec[index] ? largest : index;if (largest index) break; // 如果是根结点则停止swap(vec[largest], vec[index]);// 迭代条件index largest;left index * 2 1;}
}
// 堆排序
void HeapSort(vectorint vec) {if (vec.empty() || vec.size() 2) return ;// 依次将每个数插入建立大根堆for (int i 0; i vec.size(); i) {HeapUp(vec, i);}// 每次将大根堆的堆顶元素与数组尾元素交换int heap_size vec.size();swap(vec[0], vec[--heap_size]);while (heap_size 0) {HeapDown(vec[0], vec[head_size]);swap(vec[0], vec[--heap_size]);}
}已知一个几乎有序的数组 若把数组排好序每个元素移动的距离一定不超过k并且k相对与数组长度比较小 将前k个数放入小根堆中每次弹出一个堆顶元素并将下一个数加入堆中
在这里插入代码片比较器
比较器 原理通过重载比较运算符然后进行两个元素的按某种条件的大小比较优点可用于泛型编程 自定义cmp函数传入堆中从而实现自定义的比较 少年我观你骨骼清奇颖悟绝伦必成人中龙凤。 不如点赞·收藏·关注一波 点此跳转到首行↩︎
参考博客 对数器 单调队列 快速链表quicklist《深入理解计算机系统》侯捷C全系列视频 待定引用 待定引用 待定引用
