48days强训——day6
第一题：大数加法
描述 以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。 数据范围：s.length,t.length≤100000s.length,t.length≤100000，字符串仅由'0'~‘9’构成 要求：时间复杂度 O(n)O(n) 示例1 输入： "1","99" 返回值： "100" 说明： 1+99=100 示例2 输入： "114514","" 返回值： "114514"
题解：只要进行模拟即可。
代码：
class Solution {
public:
string solve(string s, string t)
{
string ret;
int tmp = 0;
int i = s.size() - 1, j = t.size() - 1;
while (i >= 0 || j >= 0 || tmp)
{
if (i >= 0) tmp += s[i--] - '0';
if (j >= 0) tmp += t[j--] - '0';
ret += '0' + tmp % 10;
tmp /= 10;
}
reverse(ret.begin(), ret.end());
return ret;
}
};第二题：链表相加
描述 假设链表中每一个节点的值都在 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。
示例1 输入： [9,3,7],[6,3] 返回值： {1,0,0,0} 说明： 如题面解释 示例2 输入： [0],[6,3] 返回值： {6,3} 备注： 1≤n,m≤1061≤n,m≤106 0≤ai,bi≤90≤ai,bi≤9
题解：模拟高精度加法的过程，只不过是在链表中进行而已。
代码：
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution
{
public:
ListNode* reverse(ListNode* head)
{
ListNode* newHead = new ListNode(0);
ListNode* cur = head;
while(cur)
{
ListNode* next = cur->next;
cur->next = newHead->next;
newHead->next = cur;
cur = next;
}
cur = newHead->next;
delete newHead;
return cur;
}
ListNode* addInList(ListNode* head1, ListNode* head2)
{
// 1.逆序
head1 = reverse(head1);
head2 = reverse(head2);
// 2. ⾼精度加法
int t = 0;
ListNode* cur1 = head1, *cur2 = head2;
ListNode* ret = new ListNode(0);
ListNode* prev = ret;
while(cur1 || cur2 || t)
{
if(cur1)
{
t += cur1->val;
cur1 = cur1->next;
}
if(cur2)
{
t += cur2->val;
cur2 = cur2->next;
}
prev = prev->next = new ListNode(t % 10);
t /= 10;
}
cur1 = ret->next;
ret->next = nullptr;
delete ret;
return reverse(cur1);
}
};第三题：大数乘法
描述 以字符串的形式读入两个数字，编写一个函数计算它们的乘积，以字符串形式返回。 数据范围： 读入的数字大小满足 0≤n≤1010000≤n≤101000 要求：空间复杂度 O(m)O(m)，时间复杂度 O(m2)O(m2)（假设m是n的长度） 示例1 输入： "11","99" 返回值： "1089" 说明： 11*99=1089 示例2 输入： "1","0" 返回值： "0"
题解：根据列竖式运算的过程模拟，1)反转字符串从个位算起；2)关键步骤tmp[i+j]记录各位乘积；3)处理进位；4)去零反转得结果。
代码：
class Solution {
public:
string solve(string num1, string num2)
{
//1.逆序
reverse(num1.begin(),num1.end());
reverse(num2.begin(),num2.end());
int m = num1.size(),n = num2.size();
vector<int>tmp(n+m-1);
//2.先无进位相乘后相加
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
tmp[i+j] += (num1[i]-'0') * (num2[j]-'0');
}
}
//3.处理进位
int cur = 0,t = 0;
、
string ret;
while(cur < m+n-1 || t != 0)
{
if(cur < m+n-1) t += tmp[cur++];
ret += t % 10 +'0';
t /= 10;
}
cout << ret;
//4.处理前导0
while(ret.size() > 1 && ret.back() == '0') ret.pop_back();
reverse(ret.begin(),ret.end());
return ret;
}
};腾讯云开发者
