企业官网建设流程全解析

深圳建网站哪个公司,备案网站建设承诺书,网络营销是什么岗位,撰写超越时空网上书城网站策划书哈喽各位#xff0c;我是前端小L。 欢迎来到贪心算法专题第十一篇#xff01; 想象一下#xff0c;墙上贴着一排气球#xff0c;每个气球都有一个水平覆盖范围 [start, end]。 你是神射手#xff0c;可以垂直射出一支箭。只要箭的 X 坐标在气球的覆盖范围内#xff0c…哈喽各位我是前端小L。欢迎来到贪心算法专题第十一篇想象一下墙上贴着一排气球每个气球都有一个水平覆盖范围 [start, end]。你是神射手可以垂直射出一支箭。只要箭的 X 坐标在气球的覆盖范围内气球就会爆炸。贪心目标 找准所有气球重叠最密集的地方射箭争取用最少的箭引爆所有气球。力扣 452. 用最少数量的箭引爆气球https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/题目分析输入points数组元素为[xstart, xend]。输出最少箭数。例子[[10,16], [2,8], [1,6], [7,12]]气球 A:1~6气球 B:2~8气球 C:7~12气球 D:10~16如果我们乱射可能需要 4 支箭。但如果我们精打细算在x6射一箭引爆 A(1~6) 和 B(2~8)。在x11射一箭引爆 C(7~12) 和 D(10~16)。共需 2 支箭。核心思维寻找“重叠区间”我们要想一箭穿透多个气球这几个气球必须在垂直方向上有重叠。问题转化为如何找到这组气球的公共重叠区域第一步排序既然是区间肯定要让它们有序排列才能方便判断。我们通常按起始位置 (Start) 从小到大排序。排序前[[10,16], [2,8], [1,6], [7,12]]排序后[1,6], [2,8], [7,12], [10,16]第二步遍历与更新边界我们拿第一支箭去瞄准第一个气球 [1, 6]。理论上这支箭可以射在 1 到 6 之间的任何位置。为了让这支箭能射中后面更多的气球我们应该尽可能往右边射延迟射出但不能超过 6。看第二个气球[2, 8]它的起始位置2小于第一个气球的结束位置6。说明有重叠这支箭可以同时射中这两个。关键点但这支箭的射击范围被压缩了。它必须在[1, 6]里也必须在[2, 8]里。所以这支箭最远只能射到min(6, 8) 6。更新当前重叠组的右边界right 6。看第三个气球[7, 12]它的起始位置7大于当前重叠组的右边界6。说明断档了前面那支箭最远只能射到 6根本够不着 7。决策前面的气球结算必须射出一支箭了arrows。然后我们拿出一支新箭瞄准这个新气球[7, 12]。算法流程 (JavaScript)特判如果数组为空返回 0。排序按start(下标0) 升序排列。初始化arrows 1(只要有气球至少要一箭)。遍历从第 2 个气球 (i1) 开始遍历。如果当前气球.start 上一个气球.end无重叠需要一支新箭。arrows。如果当前气球.start 上一个气球.end有重叠省下一支箭。核心操作更新当前气球的右边界模拟求交集。当前气球.end Math.min(当前气球.end, 上一个气球.end)。注这里我们直接修改数组元素的 end 值让它作为“当前重叠组的最小右边界”传递给下一次比较。代码实现JavaScript/** * param {number[][]} points * return {number} */ var findMinArrowShots function(points) { if (points.length 0) return 0; // 1. 按起始位置升序排列 // 注意a[0] - b[0] 可能会溢出(在C中)但在JS中 number 是浮点数一般没事 // 稳妥写法是 (a, b) a[0] - b[0] points.sort((a, b) a[0] - b[0]); let arrows 1; // 至少需要一支箭 // 2. 从第二个气球开始遍历 for (let i 1; i points.length; i) { // 如果当前气球的左边界 上一个气球(修正后)的右边界 // 说明完全不沾边必须新加一支箭 if (points[i][0] points[i - 1][1]) { arrows; } else { // 说明有重叠这支箭可以继续穿透 // 但是为了能穿透这两个气球箭必须射在两者较小的那个右边界之内 // 我们更新当前气球的右边界作为这一组重叠气球的“最远射击位置” points[i][1] Math.min(points[i][1], points[i - 1][1]); } } return arrows; };深度辨析为什么要Math.min假设气球是A: [1, 10](很大),B: [2, 3](很小且在A内部)。排序后A 在前B 在后。遍历到 B 时B.start(2) A.end(10)有重叠。如果我们不更新边界继续用A.end(10)跟后面的气球比。假设后面有个气球C: [4, 5]。C.start(4) A.end(10)看起来好像能一箭穿 A、B、C错你的箭如果要穿过 B就必须在[2, 3]之间射。如果你在4射箭虽然能中 A 和 C但 B 就漏了。所以一旦发现重叠这支箭的有效射击范围就瞬间缩小到了重叠区域即右边界取最小值3。这样对比 C 的时候4 3我们就知道 C 必须用新箭了。复杂度分析时间复杂度$O(N \log N)$。因为有排序。遍历只需要 $O(N)$。空间复杂度$O(1)$。除了排序可能需要的栈空间我们没有使用额外数组。总结区间问题的通解这道题展示了区间问题的标准模板排序通常按 Start 排序。判断重叠Start vs PrevEnd。更新边界取 Min 还是 Max 看具体需求。下一题预告无重叠区间如果你理解了这一题那么下一题 LC 435. 无重叠区间 你只需要改两行代码就能通过。题目问给定一堆区间最少移除几个区间才能让剩下的区间都不重叠思考一下“最少移除几个”是不是等价于“最多保留几个不重叠的”而“最多保留几个不重叠的区间”是不是和“最少用几支箭引爆所有气球”有着某种神秘的数学联系提示其实就是一模一样的题下期见