【leetcode】字符串，链表的进位加法与乘法
【leetcode】字符串，链表的进位加法与乘法
📚️1.字符串的相加
1.1题目描述
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
如下所示：
看到这里大致就知道了，这里的意思了吧，那么小编也不再进行过多的解释了；
1.2题目解析
首先，这里是不可以使用我们java中的库函数的，并且我们如果使用Integer进行字符串转化为整数，那么会有越界的情况，会超出所表示的范围；那么我们的思路只能是：一个一个位进行相加，然后得出的每一位数字进行字符串的拼接；
1.我们的计算方式是从右到左 2.获取两个字符串对应的位置的值，与进位的值进行相加 3.得到一个一个数后，计算进位以及我们要拼接的字符
这道题比较简单小编大家可以去画图试试，小编就一笔进行带过了
1.3题目代码
代码如下所示：
class Solution {
public String addStrings(String num1, String num2) {
int i = num1.length() - 1;
int j = num2.length() - 1;
//进位
int carry = 0;
StringBuffer str = new StringBuffer();
while (i >= 0 || j >= 0 || carry > 0) {
int x = 0;
int y = 0;
if (i >= 0) {
x = num1.charAt(i) - '0';
i--;
}
if (j >= 0) {
y = num2.charAt(j) - '0';
j--;
}
int sum = x + y + carry;
carry = sum / 10;
str.append(sum % 10);
}
return str.reverse().toString();
}
}注意事项：这里要注意我们的循环的判断条件，以及我们在每次获取字符串对应位置的时候，指针的移动，以及进位的计算，和拼接的字符串；当然在最后我们要注意字符串拼接后的翻转
📚️2.链表相加
2.1题目描述
假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
数据范围：0≤n,m≤10000000≤n,m≤1000000，链表任意值 0≤val≤90≤val≤9 要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
2.2题目解析
同理这里的实现方式其实和上面一道题的解题思路一致，但是这里的链表不能从后往前进行遍历，所以这里我们要进行链表的翻转
1.翻转链表，从左往右进行遍历相加 2.计算我们的两个链表对应值，以及进位加法 3.通过sum之和计算我们的应该添加的节点的值，以及我们的进位是多少 4.循环结束后再次进行翻转链表
2.3题目代码
代码如下所示：
public ListNode addInList (ListNode head1, ListNode head2) {
//进行链表的翻转
head1 = reverse(head1);
head2 = reverse(head2);
//定义进位
int carry = 0;
ListNode newHead = new ListNode(0);
ListNode cur = newHead;
while(carry > 0 || head1 != null || head2 != null){
//进行操作
int x = 0;
int y = 0;
if(head1 != null){
x = head1.val;
head1 = head1.next;
}
if(head2 != null){
y = head2.val;
head2 = head2.next;
}
int sum = x + y + carry;
carry = sum / 10;
cur.next = new ListNode(sum % 10);
cur = cur.next;
}
//再次进行翻转
return reverse(newHead.next);
}
public ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next; // 保存下一个节点
head.next = prev; // 反转当前节点的指针
prev = head; // prev 移动到当前节点
head = next; // head 移动到下一个节点
}
return prev; // prev 就是反转后的头节点
}📚️3.字符串相乘
3.1题目描述
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
3.2题目解析
这里肯定是不可以进行转化之后进行相乘的，那么还是使用进位相乘，但是这里还是有技巧的，除了按照数学方式，还有一种办法，如下所示；
所以我们可以先用一个数组，来获取 4 13 28 27 18
3.3题目代码
代码如下所示：
class Solution {
public String multiply(String num1, String num2) {
if(num1.equals("0") || num2.equals("0") ){
return "0";
}
int cur1 = num1.length() - 1;
int cur2 = num2.length() - 1;
int[] count = new int[num1.length() + num2.length() - 1];
for(int i = 0; i < num2.length() ; i++ ){
for(int j = 0; j < num1.length(); j++){
int num = (num1.charAt(cur1) - '0') * (num2.charAt(cur2) - '0');
count[i + j] = count[i + j] + num;
cur1 --;
}
cur1 = num1.length() - 1;
cur2 --;
}
//此时已经将值存入到我们的数组中了，直接进行进位相加
int t = 0;
int cur3 = 0 ;
String str = "";
while(cur3 < count.length || t != 0){
if(cur3 < count.length){
t += count[cur3] ;
cur3 ++;
}
str = String.valueOf(t % 10) + str;
t /= 10;
}
return str;
}
}注意：这里进行存储的时候，我们可以根据i j 的不同数值来表示同一个数组中位置的值，最后进行进位相加的时候，和前面几道题逻辑基本一致小编就不再过多的进行赘述了；
📚️4.总结
📚 算法题解：字符串与链表数值运算
本期解析力扣经典算法题，重点讲解字符串和链表形式的数值运算问题：
1️⃣ 字符串相加（LeetCode 415）
- 模拟竖式加法，逐位相加处理进位
- 时间复杂度O(max(M,N))，空间复杂度O(1)
2️⃣ 链表相加（NC40）
- 先反转链表后相加，再反转结果
- 注意进位处理和节点创建
- 时间复杂度O(M+N)，空间复杂度O(1)
3️⃣ 字符串相乘（LeetCode 43）
- 使用数组存储中间结果，避免直接转换
- 双重循环计算乘积，最后处理进位
- 时间复杂度O(M*N)
所有解法均避免使用内置大数库，适合面试准备和算法提升。完整代码见原文，包含详细注释和复杂度分析。
更多数据结构与算法内容欢迎访问博客主页，持续更新中！
🌅🌅🌅~~~~最后希望与诸君共勉，共同进步！！！
腾讯云开发者
