快手/字节 LeetCode 415.字符串相加

思路模拟人工加法。一、算法流程设定i,j两指针分别指向num1、num2尾部模拟人工加法。1.计算进位计算carry tmp / 10代表当前位相加是否产生进位2.添加当前位计算tmp n1 n2 carry并将当前位tmp % 10添加至res头部3.索引溢出处理当指针i或j走过数字首部后给n1、n2赋值为0相当于给num1、num2中长度较短的数字前面填0以便后续计算4.当遍历完num1、num2后跳出循环并根据carry值决定是否在头部添加进位1最终返回res即可。二、复杂度分析1.时间复杂度O(max(M,N))其中M和N为两个数字的长度按位遍历一遍数字以较长的数字为准。2.空间复杂度O(1)指针与变量需要使用常数大小的空间。注意1字符串相加是对应位相加因此i和j是从字符串最后一位做完运算后i--,j--。2字符串相乘是每位都要和对方的所有位相乘因此是forint i num1.length() - 1;i 0;i--{int val1 for(int j num2.length() - 1;j 0;j--){int val2 int sum 处理当前位和进位}}附代码class Solution { public String addStrings(String num1, String num2) { StringBuilder res new StringBuilder(); int i num1.length() - 1,j num2.length() - 1,carry 0; while(i 0 || j 0){ int val1 i 0 ? num1.charAt(i) - 0 : 0; int val2 j 0 ? num2.charAt(j) - 0 : 0; int tmp val1 val2 carry; carry tmp / 10; res.append(tmp % 10); i--;j--; } // 处理最高位相加后可能产生的进位 // 在加法运算中当两个数字的最高位相加加上之前的进位后如果结果大于等于10就会产生一个进位 // 这个进位要在循环结束后单独处理 if(carry 1){ res.append(1); } return res.reverse().toString(); } }ACM模式import java.util.Scanner; class Solution { public String addStrings(String num1, String num2) { StringBuilder res new StringBuilder(); int i num1.length() - 1, j num2.length() - 1, carry 0; while (i 0 || j 0) { int val1 i 0 ? num1.charAt(i) - 0 : 0; int val2 j 0 ? num2.charAt(j) - 0 : 0; int tmp val1 val2 carry; carry tmp / 10; res.append(tmp % 10); i--; j--; } if (carry 1) { res.append(1); } return res.reverse().toString(); } } public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); // 读取两个数字字符串 String num1 scanner.next(); String num2 scanner.next(); // 计算字符串相加结果 Solution solution new Solution(); String result solution.addStrings(num1, num2); System.out.println(result); scanner.close(); } }