1
「算法刷题」数组之大数相加专项汇总（力扣版）
source link: https://magicdeveloperdrl.github.io/2022/06/13/%E7%AE%97%E6%B3%95%E5%88%B7%E9%A2%98-%E6%95%B0%E7%BB%84%E4%B9%8B%E5%A4%A7%E6%95%B0%E7%9B%B8%E5%8A%A0%E4%B8%93%E9%A1%B9%E6%B1%87%E6%80%BB-%E5%8A%9B%E6%89%A3%E7%89%88.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
「算法刷题」数组之大数相加专项汇总（力扣版）
Jun 13, 2022 • MRL Liu
本文记录作者刷题过程中与两数相加相关的题目。
1、数组中的两数相加
989. 数组形式的整数加法（简单难度）
class Solution {
public:
vector<int> addToArrayForm(vector<int>& num, int k) {
vector<int> res;
int i=num.size()-1;
int sum=0;
bool carry=false;
while(i>=0||k){
sum=0;
if(i>=0)sum+=num[i--];
if(k){
sum+=k%10;
k/=10;
}
if(carry) sum+=1;
res.push_back(sum%10);
carry=sum>=10?true:false;
}
if(carry) res.push_back(1);
reverse(res.begin(),res.end());
return res;
}
};
2、字符串中的两数相加
415. 字符串相加（简单难度）
class Solution {
public:
string addStrings(string num1, string num2) {
string res;
// 从右向左同时遍历2个可能不等长的字符串
int i=num1.length()-1;
int j=num2.length()-1;
bool carry=false;
int sum=0;
while(i>=0||j>=0){
sum=0;
if(i>=0) sum+=num1[i--]-'0';
if(j>=0) sum+=num2[j--]-'0';
if(carry) sum+=1;
res =to_string(sum%10)+res;
carry=sum>=10?true:false;
}
// 如果有多余的进位
if(carry) res =to_string(1)+res;
return res;
}
};
3、二进制中的两数相加
67. 二进制求和（简单难度）
剑指 Offer II 002. 二进制加法（简单难度）
class Solution {
public:
string addBinary(string a, string b) {
int i=a.length()-1;
int j=b.length()-1;
string res;
bool carry=false;
int sum=0;
// 从右向左同时遍历2个可能不等长的字符串
while(i>=0||j>=0){
sum=0;
if(i>=0) sum+=a[i--]-'0';
if(j>=0) sum+=b[j--]-'0';
if(carry) sum+=1;
res =to_string(sum%2)+res;
carry=sum>=2?true:false;
}
if(carry) res =to_string(1)+res;
return res;
}
};
4、链表中的两数相加
剑指 Offer II 025. 链表中的两数相加（中等难度）
445. 两数相加 II（中等难度）
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* slow=NULL;//慢指针
ListNode* fast=head;//快指针
while(fast!=NULL){
//保存
ListNode* temp = fast->next;
//反转
fast->next=slow;
//更新
slow=fast;
fast=temp;
}
//更新头结点
head=slow;
return head;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* head=new ListNode(-1);//结果链表的虚拟头结点
ListNode* cur=head;//遍历指针
l1=reverseList(l1);
l2=reverseList(l2);
// 同时遍历2个链表
int sum=0;
bool carry=false;//是否需要进位
while(l1||l2){
sum=0;
if(l1!=nullptr){
sum+=l1->val;
l1=l1->next;
}
if(l2!=nullptr){
sum+=l2->val;
l2=l2->next;
}
if(carry) sum++;
// 为结果链表添加一个新的结果
cur->next=new ListNode(sum%10);
cur=cur->next;
carry = sum >= 10 ? true: false;//发现需要进位
}
if(carry) cur->next=new ListNode(1);
head->next = reverseList(head->next);
return head->next;
}
};
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK