废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是【字符串相加】，使用【字符串】这个基本的数据结构来实现，这个高频题的站点是：CodeTop，筛选条件为：目标公司+最近一年+出现频率排序，由高到低的去牛客TOP101去找，只有两个地方都出现过才做这道题（CodeTop本身汇聚了LeetCode的来源），确保刷的题都是高频要面试考的题。
名曲目标题后，附上题目链接，后期可以依据解题思路反复快速练习，题目按照题干的基本数据结构分类，且每个分类的第一篇必定是对基础数据结构的介绍。
字符串相加【EASY】
感觉很多数据结构都有要相加或合并的计算逻辑
题干
解题思路
算法流程： 设定 i，j 两指针分别指向 num1，num2 尾部，模拟人工加法；
- 计算进位： 计算 carry = tmp / 10，代表当前位相加是否产生进位；
- 添加当前位： 计算 tmp = n1 + n2 + carry，并将当前位 tmp % 10 添加至 res 头部；
- 索引溢出处理： 当指针 i或j 走过数字首部后，给 n1，n2 赋值为 0，相当于给 num1，num2 中长度较短的数字前面填0，以便后续计算。
- 当遍历完 num1，num2 后跳出循环，并根据 carry 值决定是否在头部添加进位 1，最终返回 res 即可。
复杂度分析：
- 时间复杂度 O(max(M,N))：其中 M，N 为 数字长度，按位遍历一遍数字（以较长的数字为准）；
- 空间复杂度 O(1)：指针与变量使用常数大小空间。
代码实现
给出代码实现基本档案
基本数据结构：字符串
辅助数据结构：无
算法：迭代
技巧：无
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 计算两个数之和 * @param s string字符串 表示第一个整数 * @param t string字符串 表示第二个整数 * @return string字符串 */ public String solve (String s, String t) { int i = s.length() - 1; int j = t.length() - 1; int cnt = 0; StringBuilder res = new StringBuilder(""); while (i >= 0 || j >= 0) { // 1 计算当前总和,如果其中一个字符串用完了则补0 int n = i >= 0 ? s.charAt(i) - '0' : 0; int m = j >= 0 ? t.charAt(j) - '0' : 0; int curSum = n + m + cnt; // 2 计算进位值 cnt = (curSum) / 10; // 3 设置当前位值 res.append(curSum % 10); // 4 移动指针 i--; j--; } // 字符串都用完后，发现还有进位值，则再补充1 if (cnt > 0) { res.append(1); } return res.reverse().toString(); } }
复杂度分析
时间复杂度 O(N)：遍历了两个字符串，O（N）阶
空间复杂度 O(1)：只用到常量
字符串相乘【MID】
字符串相加的升级版，但其实乘法也是转换为加法来使用的
题干
解题思路
我们可以把乘法转为加法来做，原题解出处
每次得到乘积后都需要与上一个乘积的高位计算总和，然后再更新res中自身的位置的值
代码实现
给出代码实现基本档案
基本数据结构：字符串
辅助数据结构：无
算法：迭代
技巧：无
代码加了注释和进行了优化
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @param n int整型 * @return string字符串 */ public String multiply(String num1, String num2) { // 1 入参判断，如果字符串都为空，返回空，如果有一个为0，则直接返回0 if (num1.length() == 0 || num2.length() == 0) { return ""; } if (num1.equals("0") || num2.equals("0")) { return "0"; } // 2 设置结果字符数组，结果最大不会超过两个字符长度和 int[] res = new int[num1.length() + num2.length()]; // 3 双指针遍历开始做加法 for (int i = num1.length() - 1; i >= 0; i--) { int n1 = num1.charAt(i) - '0'; // 与被乘数逐个相乘 for (int j = num2.length() - 1; j >= 0; j--) { int n2 = num2.charAt(j) - '0'; // 3-1 获取当前乘积 int curNum = n1 * n2; // 3-2 当前乘积对应结果集位置 int high = i + j; int low = i + j + 1; // 3-3 当前乘积与上个乘积的高位相加 int sum = curNum + res[low]; // 3-4 更新结果集的数字，高位为进位值，低微为累加取模值 res[high] = sum / 10 + res[high]; res[low] = sum % 10; } } // 4 将结果转为字符串返回 StringBuilder strBuilder = new StringBuilder(); for (int i = 0; i < res.length; i++) { if (i == 0 && res[i] == 0) { continue; } strBuilder.append(res[i]); } return strBuilder.toString(); } }
复杂度分析
时间复杂度 O(N)：遍历了两个字符串，**O（N*N）**阶
空间复杂度 O(1)：只用到常量
