做网站建设工资多少大型门户网站制作流程

做网站建设工资多少,大型门户网站制作流程,上海做网站,网站建设报价网站建设报价单一、堆排序 1.1、堆的基本概念 堆结构是用数组实现的完全二叉树完全二叉树中如果每棵子树的最大值都在顶部就是大根堆—升序完全二叉树中如果每棵子树的最小值都在顶部就是小根堆—降序优先级队列的实现就是堆结构 1.2、完全二叉树的数组表示 每层都是满的或者每层都是从左到右…一、堆排序1.1、堆的基本概念堆结构是用数组实现的完全二叉树完全二叉树中如果每棵子树的最大值都在顶部就是大根堆—升序完全二叉树中如果每棵子树的最小值都在顶部就是小根堆—降序优先级队列的实现就是堆结构1.2、完全二叉树的数组表示每层都是满的或者每层都是从左到右填充的以数组来进行存储从0开始存储那么对于任意一个节点i左孩子为2i1右孩子为2i2如果从1开始存储那么对于任意一个节点i左孩子为2i右孩子为2i11.3、核心操作向上调整建堆// 某个数处在index位置往上继续移动voidheapInsert(vectorintarr,intindex){// 往上移动直到找到合适的位置或者到达顶部----两个条件while(arr[index]arr[(index-1)/2]){swap(arr[index],arr[(index-1)/2]);index(index-1)/2;// 往上移动}}向下调整调整堆// 节点index上的值变小需要向下移动// heapSize: 堆的大小有效范围voidheapify(vectorintarr,intindex,intheapSize){intleftindex*21;// 左孩子索引// 当还有左孩子时没有左孩子就一定没有右孩子while(leftheapSize){// 找出左右孩子中较大的那个intlargestleft1heapSizearr[left1]arr[left]?left1// 右孩子存在且更大:left;// 左孩子更大或没有右孩子// 父节点和较大的孩子比较largestarr[largest]arr[index]?largest:index;if(largestindex){break;// 父节点已经是最大不需要调整}// 交换父节点和较大的孩子swap(arr[largest],arr[index]);// 继续向下调整indexlargest;leftindex*21;}}交换函数void swap(vectorint arr, int a, int b) { using std::swap; swap(arr[a], arr[b]); }1.4、堆排序voidheapSort(vectorintarr){intnarr.size();// 数组长度if(n0||n2)return;// 数组为空或者只有一个元素不需要排序for(inti0;in;i)// O(n)heapInsert(arr,i);// 建堆 O(logn)swap(arr,0,--n);// 把堆顶和最后一个元素交换让最大的元素来到最后while(n0){// 还有元素需要排序 O(n)heapify(arr,0,n);// 把剩下的元素重新堆化 O(logn)swap(arr,0,--n);// 把堆顶和最后一个元素交换让最大的元素来到最后 O(1)}}最终时间复杂度为O(nlogn)空间复杂度为O(1)。建立堆过程还可以再次优化只需要从最后一个非叶子节点开始往上建堆即可;因为最后一个非叶子节点以下的元素已经是堆结构了。for(intin/2-1;i0;--i)// 从最后一个非叶子节点开始往上建堆heapify(arr,i,n);1.5、堆排序过程以数组[410351]构建大根堆构建堆后:[10, 5, 3, 4, 1]排序过程交换堆顶元素和最后一个元素然后重新调整堆结构交换 10 和 1: [1, 5, 3, 4, 10]调整堆: [5, 4, 3, 1, 10]交换 5 和 1: [1, 4, 3, 5, 10]调整堆: [4, 1, 3, 5, 10]交换 4 和 3: [3, 1, 4, 5, 10]调整堆: [3, 1, 4, 5, 10]交换 3 和 1: [1, 3, 4, 5, 10]最终结果: [1, 3, 4, 5, 10]1.6、C中STL中的堆操作#includequeue#includevector#includealgorithm#includefunctionalvoidstlHeapOperations(){// 1. 容器适配器 - priority_queuepriority_queueintmaxHeap;// 默认大根堆priority_queueint,vectorint,greaterintminHeap;// 小根堆// 2. 算法函数在 algorithm 中vectorintarr{3,1,4,1,5,9};// 构建最大堆make_heap(arr.begin(),arr.end());// 堆操作后: [9, 5, 4, 1, 1, 3]// 向堆中添加元素arr.push_back(6);push_heap(arr.begin(),arr.end());// 从堆中移除最大元素pop_heap(arr.begin(),arr.end());arr.pop_back();// 堆排序sort_heap(arr.begin(),arr.end());// 排序后: [1, 1, 3, 4, 5, 9]// 检查是否为堆boolisHeapis_heap(arr.begin(),arr.end());}1.7、扩展题目已知一个几乎有序的数组几乎有序是指如果把数组排好序的话每个元素移动的距离一定不超过k并且k相对于数组长度来说比较小。请问这个几乎有序的数组的最快排序方法是堆排序可以解决这个问题因为堆排序的时间复杂度是O(nlogk)远远小于O(n^2)。原因假设k6那么堆的大小就是7先从前7个元素建立小根堆/大根堆然后依次把后面的元素插入到堆中每次插入之后再重新调整堆结构每次调整会将堆顶元素弹出然后再把后面的元素插入到堆中。时间复杂度为O(nlogk)空间复杂度为O(k)。#includeiostream#includequeue#includevector#includefunctionalvoidsortedArrDistanceLessK(vectorintarr,intk){priority_queueint,std::vectorint,std::greaterintminHeap;// 小根堆intindex0;for(;indexstd::min((int)arr.size(),k);index){// 先将前k个元素放入小根堆中minHeap.push(arr[index]);}inti0;for(;iarr.size();i,index){// 遍历数组minHeap.push(arr[index]);// 把当前元素放入小根堆中arr[i]minHeap.top();// 把堆顶元素放到当前位置minHeap.pop();// 弹出堆顶元素}while(!minHeap.empty()){arr[i]minHeap.top();// 把堆顶元素放到当前位置minHeap.pop();// 弹出堆顶元素}}1.8、为什么要手写堆结构系统提供的堆的局限性无法修改中间元素priority_queue不支持修改堆中任意元素无法指定比较器有时需要自定义复杂的比较逻辑无法批量建堆系统堆通常是逐个插入无法控制内存某些嵌入式环境需要手动管理内存二、实操演练2.1、Leetcode 506 相对名次题目描述:给你一个长度为 n 的整数数组 score 其中 score[i] 是第 i 位运动员在比赛中的得分。所有得分都 互不相同 。运动员将根据得分 决定名次 其中名次第 1 的运动员得分最高名次第 2 的运动员得分第 2 高依此类推。运动员的名次决定了他们的获奖情况名次第 1 的运动员获金牌 “Gold Medal” 。名次第 2 的运动员获银牌 “Silver Medal” 。名次第 3 的运动员获铜牌 “Bronze Medal” 。从名次第 4 到第 n 的运动员只能获得他们的名次编号即名次第 x 的运动员获得编号 “x”。使用长度为 n 的数组 answer 返回获奖其中 answer[i] 是第 i 位运动员的获奖情况。示例 1输入score [5,4,3,2,1]输出[“Gold Medal”,“Silver Medal”,“Bronze Medal”,“4”,“5”]解释名次为 [1st, 2nd, 3rd, 4th, 5th] 。示例 2输入score [10,3,8,9,4]输出[“Gold Medal”,“5”,“Bronze Medal”,“Silver Medal”,“4”]解释名次为 [1st, 5th, 3rd, 2nd, 4th] 。解题思路使用大根堆来存储得分和索引从堆中逐个弹出元素根据弹出的顺序确定名次将名次信息存入结果数组classSolution{public:vectorstringfindRelativeRanks(vectorintscore){// 使用堆排序建立最大堆intlengthscore.size();vectorstringret(length);// 得分索引priority_queuepairint,intmaxHeap;for(inti0;ilength;i){maxHeap.push({score[i],i});}intrank1;while(!maxHeap.empty()){auto[scoreVal,index]maxHeap.top();maxHeap.pop();if(rank1){ret[index]Gold Medal;}elseif(rank2){ret[index]Silver Medal;}elseif(rank3){ret[index]Bronze Medal;}else{ret[index]to_string(rank);}rank;}returnret;}};2.2、LeetCode 703 数据流中的第K大元素题目描述设计一个找到数据流中第 k 大元素的类class。注意是排序后的第 k 个最大元素不是第 k 个不同的元素。实现 KthLargest 类KthLargest(int k, int[] nums) 初始化对象其中 nums 是传递给构造函数的整数数组k 表示每次查找的第 k 大元素。int add(int val) 将 val 插入数据流 nums 后得到的新数据流中并返回当前数据流中第 k 大的元素。示例输入[“KthLargest”,“add”,“add”,“add”,“add”,“add”], [[3,[4,5,8,2]],[3],[5],[10],[9],[4]]输出[null,4,5,5,8,8]解释KthLargest kthLargest new KthLargest(3, [4, 5, 8, 2]);kthLargest.add(3); // 返回 4kthLargest.add(5); // 返回 5kthLargest.add(10); // 返回 5kthLargest.add(9); // 返回 8kthLargest.add(4); // 返回 8解题思路使用最小堆维护大小为k的元素集合最小堆的堆顶就是第k大的元素classKthLargest{public:KthLargest(intk,vectorintnums){this-m_countk;// 先加入所有元素建立小根堆for(constautoval:nums){minHeap.push(val);}// 堆大小超过k弹出多余元素while(minHeap.size()k){minHeap.pop();}}intadd(intval){minHeap.push(val);if(minHeap.size()m_count){minHeap.pop();}returnminHeap.top();}private:intm_count;priority_queueint,vectorint,greaterintminHeap;};