scala网站开发宝安公司网站制作哪家公司好

scala网站开发,宝安公司网站制作哪家公司好,wordpress大前端d8,网站免费云主机下面我按 “为什么这么做 两种常见写法 易错点”#xff0c;把 283. 移动零 讲清楚。这题是双指针的入门必会题。一、题目本质#xff08;先定型#xff09; 你要做三件事#xff1a; 把所有非 0 元素往前挪保持原有相对顺序#xff08;稳定#xff09;原地修改数组 两种常见写法 易错点”把283. 移动零讲清楚。这题是双指针的入门必会题。一、题目本质先定型你要做三件事把所有非 0 元素往前挪保持原有相对顺序稳定原地修改数组不能新建数组二、最优思路双指针快慢指针一句话版本慢指针指向“下一个该放非零的位置”快指针负责扫描整个数组。三、标准解法推荐面试首选写法一覆盖 补零最清晰defmoveZeroes(nums):slow0forfastinrange(len(nums)):ifnums[fast]!0:nums[slow]nums[fast]slow1foriinrange(slow,len(nums)):nums[i]0人脑解释非常重要第一轮循环把所有非 0按顺序写到数组前面例如[0,1,0,3,12] ↓ [1,3,12,?,?]第二轮循环把后面的空位补 0四、另一种常见写法原地交换更“原地”defmoveZeroes(nums):slow0forfastinrange(len(nums)):ifnums[fast]!0:nums[slow],nums[fast]nums[fast],nums[slow]slow1何时交换fast指向非 0slow指向 0五、两种写法对比面试加分点写法特点覆盖 补零思路直观写操作较多交换真正原地操作更优面试推荐覆盖 补零更容易解释六、为什么这题一定要双指针如果你用nums.remove(0)nums.append(0)❌ 错误原因remove是 O(n)多次调用退化成 O(n²)且不是“原地算法思想”七、复杂度分析指标复杂度时间复杂度O(n)空间复杂度O(1)八、常见错误非常容易踩❌ 错误 1边遍历边删forxinnums:ifx0:nums.remove(0)❌ 错误 2破坏相对顺序nums.sort(keylambdax:x0)九、你现在应该形成的“条件反射”看到题目包含“保持相对顺序”“原地操作”“移动 / 删除 / 重排”第一反应双指针十一、一个检验理解的问题建议你自己想为什么交换法里当slow fast时交换是“无害的”如果你能答出“交换自己不影响结果”那说明你对指针不变量已经理解了。我为什么要这么设计指针每一步是在维护什么不变量交换到底在干什么我按**“问题 → 思想 → 不变量 → 每一行代码的意义”**来彻底拆解283 移动零。看完你应该能自己推导出来而不是背。一、先把目标说清楚不谈代码题目要你同时满足三件事非 0 的相对顺序不能变所有 0 去后面原地这三点合在一起直接排除了很多做法。二、你真正需要做的其实只有一件事把所有非 0 元素按原来的顺序放到数组的最前面。一旦你做到这点后面剩下的位置自然只能是 0所以问题被“降维”为如何在一次遍历中稳定地收集非 0三、为什么一定要“快指针遍历”你问为什么要用快指针答案是因为你必须检查数组里的“每一个元素”这就意味着必然有一个指针是扫描者不管你叫它fast、i还是别的名字所以forfastinrange(len(nums)):不是“技巧”而是最低成本的全量检查方式。四、那慢指针在干什么核心慢指针slow的语义非常重要slow永远指向下一个“非 0 应该放的位置”这是这道题的不变量Invariant。换句话说在任意时刻nums[0 : slow] → 已经是按顺序排好的非 0 nums[slow : fast] → 已扫描但全是 0 nums[fast : ] → 还没看五、条件判断是怎么“推导出来”的你问“为啥判断nums[fast] ! 0”因为只有两种情况情况 1nums[fast] 0这个元素最终要去后面现在什么都不用做继续扫描即可情况 2nums[fast] ! 0这个元素必须出现在前面位置应该是slow这一步必须处理六、那为什么要“交换”你最困惑的点我们来看这行代码nums[slow],nums[fast]nums[fast],nums[slow]这一步到底在干什么把当前发现的非 0放到它应该去的位置slow而nums[slow]里原本是什么要么是 0要么是它自己当slow fast举个完整例子一步不跳初始nums [0,1,0,3,12] slow 0fast 0nums[0] 0 → 什么都不做 slow 0fast 1nums[1] 1 → 非 0交换swap nums[0] 和 nums[1] → [1,0,0,3,12] slow 1fast 2nums[2] 0 → 跳过fast 3nums[3] 3 → 非 0交换swap nums[1] 和 nums[3] → [1,3,0,0,12] slow 2fast 4nums[4] 12 → 非 0交换swap nums[2] 和 nums[4] → [1,3,12,0,0]七、那当 slow fast 时交换有意义吗你可能会担心nums[slow],nums[fast]nums[fast],nums[slow]当slow fast是不是多余答案是是多余的但无害交换自己不影响结果。而好处是不需要额外判断逻辑保持统一八、为什么不直接“删 0 再补 0”你可能本能会想到nums.remove(0)nums.append(0)但问题是remove是 O(n)多次 remove 变成 O(n²)且破坏“原地 指针模型”九、用一句“思想级总结”帮你定型快指针负责“看世界”慢指针负责“安排位置”遇到该留下的就放到该去的位置。十、你现在已经站在“双指针真正入门”的门口你现在问的这些问题正是LeetCode 27移除元素26删除重复项80重复元素 II的统一思想根源。十一、最后给你一个自检问题非常重要你现在可以自己想一下如果题目改成“把所有奇数移到前面偶数移到后面保持相对顺序”你还会不会用这套快慢指针如果你能回答“是的只需要把! 0换成是奇数”那说明你已经真正理解了这道题的思想。这道题你不理解思想是非常正常的因为它是双指针里最“反直觉”的一道。我不直接给代码先把为什么能这么做讲清楚。一、先把“水量”这件事数学化任意选两根线i和ji j水量 min(height[i], height[j]) × (j - i)注意只有两个因素宽度j - i高度由较短的那根决定木桶效应二、为什么一开始选「最左 最右」你可能会问为什么不是枚举所有组合因为那是 O(n²)题目明显在逼你优化。关键事实宽度的最大值一定发生在最外侧所以如果最外侧都不能形成最大水量那内侧更窄的组合必须靠“更高的短板”来弥补于是自然得到一个策略从最大宽度开始逐步缩小宽度三、双指针的“角色分工”设left 0 right n - 1在任意时刻left和right定义了当前容器我们计算一次水量然后只移动其中一个指针核心问题来了 为什么只动一边动哪一边四、最关键的结论必须理解假设height[left] height[right]也就是说左边是短板问题我如果移动右指针长板有没有可能变好答案不可能原因这是整道题的灵魂宽度变小了高度仍然 ≤height[left]面积一定不增反减所以当左边是短板时右边动是“纯亏操作”五、因此指针移动规则是“被逼出来的”结论不是拍脑袋是逻辑推导短板不变宽度减小 → 面积一定更小想变大只能放弃当前短板试图找到一根“更高的短板”于是得到唯一合理策略谁短谁移动六、为什么这个策略“不会漏解”你可能会担心万一我跳过了某个最优组合呢这是关键保证每一次你舍弃短板都是在说“以这根短板为边界的所有更窄组合都不可能超过当前结果”所以你不是在“随便跳”而是在一次性排除一整类不可能最优的解这是贪心 双指针的典型结构。七、用一个直觉比喻非常重要想象你拿着两个挡板接水水位永远由较低的一侧决定你拉近挡板只会让水更少你只能尝试换一块“更高的短挡板”所以你永远不会去动高的一侧。八、完整思想流程不是代码左右指针从最宽开始计算当前水量比较左右高度移动较低的一边重复直到相遇九、你现在应该具备的“判断能力”如果我现在问你为什么不能两个指针一起往里走你应该能回答因为那会无差别缩小宽度却没有保证短板提升属于“无信息损失的盲减”一定可能错过最优解。十、把这道题放在你整个刷题体系里这题的本质不是“装水”而是在「单调收缩的搜索空间」中用物理约束强制剪枝它和你前面学的283 移动零维护区间不变量128 最长连续序列用集合消除无效搜索在思维层级上是同一类问题。最后一个关键自检问题非常重要如果我把题目改成允许容器倾斜你觉得这个双指针策略还成立吗如果你能说出“不成立因为高度不再由 min 决定短板原则被破坏”那你已经真正吃透了这道题。下面给出LeetCode 11盛最多水的容器的标准、可直接背诵的面试代码以及每一行在干什么。你可以对照我刚才讲的思想逐行看。一、标准双指针代码推荐写法defmaxArea(height):left0rightlen(height)-1max_water0whileleftright:# 当前容器的高度由短板决定hmin(height[left],height[right])# 当前容器的宽度wright-left# 计算水量max_watermax(max_water,h*w)# 谁短谁移动ifheight[left]height[right]:left1else:right-1returnmax_water二、逐行解释按你当前阶段必须理解的粒度left0rightlen(height)-1从最宽的容器开始搜索空间最大whileleftright:两根线至少要是两根指针相遇就没有宽度了hmin(height[left],height[right])wright-left高度短板宽度两指针距离max_watermax(max_water,h*w)记录历史最大值不是 return因为后面可能更大ifheight[left]height[right]:left1else:right-1这是整道题唯一的“策略”短板不变宽度缩小 → 一定更差只能试图换一根更高的短板所以谁短谁走三、为什么这段代码是 O(n)left最多走 n 步right最多走 n 步总步数 ≤ 2n四、你现在应该能回答的 3 个问题1️⃣ 为什么不用双重循环因为双循环是 O(n²)而这里每根线只被访问一次。2️⃣ 为什么不能动长板因为宽度变小高度上限不变面积一定不会更大3️⃣ 为什么不会漏掉最优解因为每次移动短板都一次性排除了以该短板为边界的所有更差情况五、和你之前题目的“统一理解”题目不变量移动零[0, slow)永远是非零盛水当前区间外的组合已被证明不可能更优下面给你LeetCode 15三数之和3Sum的标准代码以及从 0 到 1 的完整思想拆解。这题本质是排序 固定一个数 双指针二数之和变体。一、最终标准代码面试可直接写defthreeSum(nums):nums.sort()res[]nlen(nums)foriinrange(n):# 剪枝 1第一个数大于 0不可能再凑出 0ifnums[i]0:break# 去重 1第一个数去重ifi0andnums[i]nums[i-1]:continuelefti1rightn-1whileleftright:snums[i]nums[left]nums[right]ifs0:res.append([nums[i],nums[left],nums[right]])# 去重 2第二、第三个数去重whileleftrightandnums[left]nums[left1]:left1whileleftrightandnums[right]nums[right-1]:right-1left1right-1elifs0:left1else:right-1returnres二、先说结论整体思路一句话把三数之和降维成固定一个数 在剩余区间做“有序数组的两数之和”。三、为什么第一步一定要排序排序后你得到三个关键能力双指针可用可以剪枝提前结束可以去重这是最难的部分没有排序这题基本做不出来。四、三层结构的真实含义不是“套模板”① 第一层for 循环固定第一个数foriinrange(n):你在说“我先假设 nums[i] 是三元组里的第一个数。”剪枝 1为什么nums[i] 0可以 breakifnums[i]0:break因为数组已排序后面只会更大三个正数不可能加出 0这是数学剪枝不是经验。去重 1为什么要跳过相同的 nums[i]ifi0andnums[i]nums[i-1]:continue否则会出现[-1, 0, 1] [-1, 0, 1] ← 重复五、第二层双指针 两数之和你已经学过lefti1rightn-1现在问题变成在有序数组中找nums[left] nums[right] -nums[i]六、三种情况判断核心决策snums[i]nums[left]nums[right]情况 1s 0找到一个解但不能马上结束因为可能还有别的组合情况 2s 0left1原因总和太小想变大只能让left右移变大情况 3s 0right-1原因总和太大只能让right左移变小七、为什么去重要写成 while这是 3Sum 最容易写错的地方。whileleftrightandnums[left]nums[left1]:left1因为相同的值会产生相同的三元组排序后相同值是连续的要一次性跳过否则你会得到重复答案。八、这题真正的“思想层级”不是“三重循环优化”而是用排序 单调性把指数级组合空间压缩成线性扫描九、复杂度分析面试必说项目复杂度排序O(n log n)双指针扫描O(n²)总体O(n²)额外空间O(1)不算结果十、和你之前题目的统一视角题目本质Two Sum哈希查找盛水双指针 剪枝三数之和固定一维 双指针四数之和再套一层3Sum 是整个双指针体系的“天花板入门题”。十一、你现在应该能回答的关键问题如果我问你为什么不能用 set 直接存三元组你应该能说可以但会多用空间且无法提前剪枝时间不稳定排序 双指针是结构性解法。