企业官网建设流程全解析

多用户建站系统源码,wordpress前台视频上传,百度推广关键词技巧定价,外国媒体网站哈喽各位#xff0c;我是前端小L。 欢迎来到贪心算法专题第十篇#xff01; 想象一下#xff0c;一群人排队#xff0c;每个人都知道自己的身高 h#xff0c;也知道排在自己前面且身高大于或等于自己的人数 k。 现在队伍被打乱了#xff0c;只给你这两个数字#xff…哈喽各位我是前端小L。欢迎来到贪心算法专题第十篇想象一下一群人排队每个人都知道自己的身高 h也知道排在自己前面且身高大于或等于自己的人数 k。现在队伍被打乱了只给你这两个数字请你把队伍恢复原状。示例[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]][7,0]身高7前面有0个比我高的说明我站在最前面或者前面都比我矮。[5,2]身高5前面有2个比我高的。力扣 406. 根据身高重建队列https://leetcode.cn/problems/queue-reconstruction-by-height/题目分析输入people数组元素为[h, k]。输出重排后的数组。核心思维高个子看不见矮个子如果我们先按k排序或者乱序插入会发现极其痛苦因为插入一个人可能会影响后面所有人的k值因为你不知道插入的人是不是比后面的人高。贪心策略优先处理“高个子”为什么因为矮个子对高个子没有影响。只要高个子先站好了后面无论怎么插入矮个子高个子前面的“大于等于自己身高的人数”都不会变因为新插进来的比他矮他不care。反之如果先排矮个子后面来了个高个子往前面一插矮个子的k就废了前面多了一个比他高的k就要变。确定主导维度先按身高h从大到小排序。如果身高相同则按k从小到大排序因为身高一样时k小的肯定在前面。插入操作排序后我们拿到的人是[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]我们按照这个顺序把每个人插入到队列中索引为k的位置。神奇之处因为你是最矮的相对于已经排好的人你插入到位置k意味着你前面正好有k个人。而这k个人都比你高因为他们是先排进去的。你的k属性天然满足同时你插进去也不会破坏已经在队伍里那些高个子的k属性。算法流程 (JavaScript)排序h降序 (b[0] - a[0])。h相同时k升序 (a[1] - b[1])。排序结果[[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]插入创建一个空数组queue。拿出[7,0]- 插到 index 0 -[[7,0]]拿出[7,1]- 插到 index 1 -[[7,0], [7,1]]拿出[6,1]- 插到 index 1 -[[7,0], [6,1], [7,1]](站在7,0后面7,1前面)拿出[5,0]- 插到 index 0 -[[5,0], [7,0], [6,1], [7,1]]...以此类推。代码实现在 JS 中数组的splice方法非常适合做“在特定位置插入元素”的操作。JavaScript/** * param {number[][]} people * return {number[][]} */ var reconstructQueue function(people) { // 1. 排序 // 优先按身高 h (p[0]) 降序排列 // 如果身高相同按 k (p[1]) 升序排列 people.sort((a, b) { if (a[0] ! b[0]) { return b[0] - a[0]; // h 降序 } else { return a[1] - b[1]; // k 升序 } }); let queue []; // 2. 遍历排序后的数组按 k 值插入 for (let i 0; i people.length; i) { // splice(插入位置, 删除数量, 插入元素) // 核心贪心逻辑因为比我高的人都已经排好了 // 我现在的 k 是多少我就应该站在第 k 个位置上。 // 我插进去之后不会影响后面比我高的人的 k 值因为我比他们矮。 queue.splice(people[i][1], 0, people[i]); } return queue; };深度复杂度分析时间复杂度$O(N^2)$。排序是 $O(N \log N)$。但是splice插入操作本质上是数组元素的移动最坏情况是 $O(N)$。在循环中做 $N$ 次插入总共是 $O(N^2)$。虽然是 $O(N^2)$但因为数据量不大且 JS 引擎对数组操作优化较好可以通过。空间复杂度$O(N)$。用于存储结果队列如果算上输出空间。总结维度的优先级这道题是解决多维度冲突问题的教科书级案例。当我们在两个维度身高、k值之间摇摆不定时试着先固定一个维度身高看看是否能消除另一个维度的不确定性。确定了由高到低排k就变成了纯粹的“绝对索引”。下一题预告用最少数量的箭引爆气球接下来我们将进入贪心算法中最实用、最成体系的**“区间问题”**板块共 4 题。给你一堆气球每个气球覆盖一个水平区间[start, end]。你可以垂直射箭。问最少射几箭能把所有气球都打破这道题将教会我们如何处理重叠区间。一旦掌握了这道题后面的“无重叠区间”、“合并区间”全都是秒杀。准备好你的弓箭了吗下期见