网站建设评分细则,网站和app设计区别,app网站制作软件,学校网站建设汇报ppt模板小哆啦开始力扣每日一题的第十二天 https://leetcode.cn/problems/product-of-array-except-self/description/ 《小哆啦解题记#xff1a;如何计算除自身以外数组的乘积》
在一个清晨的阳光下#xff0c;小哆啦坐在书桌前#xff0c;思索着一道困扰已久的题目#xff1a;… 小哆啦开始力扣每日一题的第十二天 https://leetcode.cn/problems/product-of-array-except-self/description/ 《小哆啦解题记如何计算除自身以外数组的乘积》
在一个清晨的阳光下小哆啦坐在书桌前思索着一道困扰已久的题目 给定一个整数数组 nums返回一个新的数组 answer其中 answer[i] 等于 nums 中所有元素的乘积除了 nums[i] 本身。 “这看起来不复杂吧”小哆啦轻声自语脑海里已经开始快速构建解题思路。看似简单的题目背后却藏着优化的挑战。他决定从最基础的方法开始尽管他并不期待它能跑得很快。
第一步用双重循环解决问题
“最直接的方式是什么”小哆啦问自己随后他选择了使用两个嵌套的 for 循环来解决问题。对于每个元素他都会计算数组中除了它自己以外的所有元素的乘积。
function productExceptSelf(nums: number[]): number[] {const n nums.length;const answer: number[] new Array(n);for (let i 0; i n; i) {let product 1;for (let j 0; j n; j) {if (i ! j) {product * nums[j];}}answer[i] product;}return answer;
}然而当他输入一组较大的数字时程序的速度开始变得异常缓慢。每次都要做两层循环计算每个元素的乘积这样的时间复杂度是 O(n2)) 。这显然不是一个高效的解法。
“嗯看起来我得换个思路了。”小哆啦皱了皱眉头开始思考如何避免重复计算。
第二步寻找高效解法
小哆啦坐在书桌前突然灵光一闪“如果我计算出数组中每个元素左边的乘积再计算出右边的乘积然后结合起来不就能避免重复计算吗”这一瞬间他感觉找到了答案。
他决定实现一个新思路分别计算出每个元素左边和右边的乘积然后将它们相乘。这样每个位置的答案就能得到且时间复杂度将降到 O(n) 。
第三步前缀积和后缀积的巧妙结合
小哆啦迅速动手实现这个新思路。首先他计算出每个元素左边的所有元素的乘积前缀积然后计算每个元素右边的乘积后缀积。最后将两者相乘即可得到最终的答案。
function productExceptSelf(nums: number[]): number[] {const n nums.length;const answer: number[] new Array(n).fill(1);// 计算前缀积let prefix 1;for (let i 0; i n; i) {answer[i] prefix;prefix * nums[i];}// 计算后缀积并更新结果let suffix 1;for (let i n - 1; i 0; i--) {answer[i] * suffix;suffix * nums[i];}return answer;
}第四步高效的实现快速的运行
小哆啦再次运行代码。这一次进度条飞速前进几乎在眨眼之间就得到了正确的结果
“太棒了终于解决了。”小哆啦松了口气心里充满了成就感。这种方法的时间复杂度是 O(n) 比之前的暴力方法快得多而且它只使用了常数空间存储前缀积和后缀积空间复杂度为 O(1) 除了结果数组。
第五步胜利的微笑
回想这一路的艰难与突破小哆啦感到十分满足。每一个程序员的成长都是在一次次挑战中找到突破口的过程。从最初的双重循环到最后的前缀积和后缀积的优化这不仅仅是一个简单的算法问题而是一次智慧的提升。
他站起身来望着窗外的蓝天嘴角微微上扬“未来的道路还很长我会继续走下去发现更多的优化和突破。” 结语优化的思维突破的力量
小哆啦的解题历程给我们带来了深刻的启示对于一个看似简单的问题背后往往隐藏着对效率和优化的深刻理解。通过巧妙地运用前缀积和后缀积的方式我们能够在 O(n) 的时间复杂度内高效地解决问题避免了重复计算。
每次的挑战背后都是对思维和能力的一次锤炼。当我们能够突破常规的思维方式才能真正在算法的世界中找到属于自己的道路。
