网站制作公司 番禺微信公众平台运营

网站制作公司 番禺,微信公众平台运营,网站建设风险怎样规避,夫唯seo培训“大数加法”是面试和算法练习中非常经典的一道题#xff08;如 LeetCode 415#xff09;。它的核心矛盾在于#xff1a;计算机的标准整数类型#xff08;如 64 位整型#xff09;有最大值限制#xff0c;当数字超过几十位甚至上百位时#xff0c;直接相加会溢出。 处理…“大数加法”是面试和算法练习中非常经典的一道题如 LeetCode 415。它的核心矛盾在于计算机的标准整数类型如 64 位整型有最大值限制当数字超过几十位甚至上百位时直接相加会溢出。处理这个问题的通用方案是模拟人类列竖式计算的过程。1. 核心逻辑从低位到高位就像我们在纸上做加法一样对齐从两个字符串的末尾个位开始加。进位 (carry)如果相加结果≥10\ge 10≥10记下进位留到下一位使用。补齐如果一个数字比另一个短短的部分补0。最后进位如果所有位都加完了进位还剩1别忘了在最高位补个1。2. 代码实现 (Python)classSolution:defaddStrings(self,num1:str,num2:str)-str:# 指针分别指向两个字符串的末端i,jlen(num1)-1,len(num2)-1carry0# 进位res[]# 存储每一位的结果# 只要还有位没加完或者还有进位没处理whilei0orj0orcarry:# 取出当前位的值如果指针已经越界则补 0xint(num1[i])ifi0else0yint(num2[j])ifj0else0# 计算当前位的总和totalxycarry# 更新进位和当前位carrytotal//10res.append(str(total%10))# 指针左移i-1j-1# 因为是从个位开始存的最后需要翻转回来并拼接成字符串return.join(res[::-1])3. 关键点拆解A. 为什么用res[::-1]我们在循环里是先算出“个位”再算“十位”存入列表的结果是[个, 十, 百]。这和我们阅读数字的顺序是相反的所以最后需要[::-1]反转一下。B.while i 0 or j 0 or carry:这个条件非常精妙i 0 or j 0保证了即使两个数字长度不等也能把长的那个加完。or carry处理最特殊的情况比如99 1。当i和j都走完了carry还是1循环会多跑一次把最高位的1加上去。C.total // 10和total % 10total // 10取商。如果是 13商就是 1作为进位。total % 10取余。如果是 13余数就是 3作为当前位的结果。4. 复杂度分析时间复杂度O(max(N,M))O(max(N, M))O(max(N,M))。N,MN, MN,M分别为两个数字的长度。我们需要遍历较长的那个数字。空间复杂度O(max(N,M))O(max(N, M))O(max(N,M))。我们需要一个列表来存放结果。# 只要还有位没加完或者还有进位没处理whilei0orj0orcarry:# 取出当前位的值如果指针已经越界则补 0xint(num1[i])ifi0else0yint(num2[j])ifj0else0在 Python 中x A if condition else B叫做条件表达式也叫三元运算符。如果你觉得它看起来太挤完全可以用标准的if-else结构来替换。写开后的代码更易读版我们将这两个赋值动作拆解到循环内部whilei0orj0orcarry:# --- 处理 num1 的当前位 ---ifi0:xint(num1[i])else:x0# 如果 num1 已经遍历完了就当它是 0# --- 处理 num2 的当前位 ---ifj0:yint(num2[j])else:y0# 如果 num2 已经遍历完了就当它是 0# --- 后面的逻辑不变 ---totalxycarry carrytotal//10res.append(str(total%10))i-1j-1为什么我们要这么写补零逻辑这种写法是为了解决**“两个数字长度不一样”**的问题。比如计算123 45第一轮i指向3j指向5。x3, y5。第二轮i指向2j指向4。x2, y4。第三轮i指向1但j已经变成-1了越界。此时如果没有else: y 0这段代码程序就会报错。有了这段代码y就会自动补0。这就相当于你在纸上算1 2 3 0 4 5 -- 这里的0就是靠 else 分支补上的 ---------这种写法的好处调试方便如果你想看x或者y到底取到了什么值你可以在if分支里打断点或加print。逻辑安全它显式地处理了索引越界的情况不会出现IndexError。intnum1[i]代码中将字符转换为整数的关键步骤。我们可以把它拆成三部分来理解1. 拆解分析num1[i]num1是一个字符串比如123。i是当前的索引下标。所以num1[i]是从字符串中取出第i个位置的字符。比如num1[0]取出的是1注意此时它还是带引号的字符串不能直接做加法。int(...)这是一个内置函数负责强制类型转换。它把括号里的东西转成整数。比如把字符串1转成数字1。x ...把转换后的数字赋值给变量x这样x就可以参与数学运算了。2. 为什么要加int()在 Python 中字符串和数字是两种完全不同的“物种”。如果你直接把两个字符串相加Python 会把它们拼接起来1 2 12这显然不是我们要的加法结果如果你把字符串和数字相加Python 会报错1 2 TypeError因为系统不知道你是想拼接还是想求和所以我们需要用int()把字符变成数字才能进行真正的数学运算int(1) int(2) 33. 放到大数加法背景下假设我们要算98 7当i指向num1的末尾字符8时x int(num1[i])得到x 8。当j指向num2的末尾字符7时y int(num2[j])得到y 7。这时我们就可以算8 7 15然后处理进位。4. 这种写法的一个“坑”在实际运行这行代码之前必须确保num1[i]确实是一个代表数字的字符比如0-9。如果是int(a)代码会报错ValueError。在大数加法里因为我们已经用if i 0保证了索引有效且题目保证输入是数字字符串所以这么写是安全的。你会发现在很多涉及数字字符串处理的题目中比如求和、乘法、有效数字判断int(s[i])都是出镜率最高的一行代码。