【C++笔试强训】如何成为算法糕手Day6
第一题：大数加法
牛客网做题链接：大数加法_牛客题霸_牛客网 (nowcoder.com)
思路：
对于这种问题，有特定解题模板---高精度算法。
要实现这个功能，我们可以使用两个指针分别指向两个字符串的末尾，然后从后往前遍历这两个字符串，同时处理加法运算和进位。这里我假设两个字符串都是用字符数组表示的，并且它们的长度可能不同。如果某个字符串比另一个短，我们可以在其末尾添加0来补齐，以便两个字符串可以从后往前同时遍历。
class Solution {
public:
string solve (string s, string t) {
int cur1 = s.size() - 1, cur2 = t.size() - 1, n = 0;
string ret;
while (cur1 >= 0 || cur2 >= 0 || n)
{
int sum = 0;
if (cur1 >= 0) sum += (s[cur1--] - '0');
if (cur2 >= 0) sum += (t[cur2--] - '0');
sum += n;
ret += to_string(sum % 10);
n = sum / 10;
}
reverse(ret.begin(), ret.end());
return ret;
}
};第二题：链表相加
牛客网做题链接：链表相加(二)_牛客题霸_牛客网 (nowcoder.com)
思路：
对于链表的逆序，我们可以创建一个链表结点，如何将我们需要的逆序的链表，不断头插到我们新建的链表中，当全部头插完成后，也就实现了链表的逆序了。 之后的写法就与第一题一模一样的， 使用两个指针从头一次枚举然后相加即可，再将计算出来的结果添加到最终的结果链表中，循环完成之后再将结果链表进行逆置就可以
class Solution {
public:
ListNode * Reverse(ListNode *&list)
{
ListNode * p = nullptr, * c = list, * n = list->next;
while (c)
{
c->next = p;
p = c;
c = n;
if (n)
n = n->next;
}
return p;
}
// 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)
{
ListNode * cur1 = Reverse(head1);
ListNode * cur2 = Reverse(head2);
ListNode* ret = nullptr;
ListNode* list = nullptr;
int n = 0;
while (cur1 || cur2 || n)
{
int num = 0;
if (cur1)
{
num += cur1->val;
cur1 = cur1->next;
}
if (cur2)
{
num += cur2->val;
cur2 = cur2->next;
}
num += n;
ListNode *node = new ListNode(num % 10);
if(list != nullptr)
{
list -> next = node;
list = list->next;
}
else
{
list = node;
ret = node;
}
cout << list->val << " ";
n = num / 10;
}
ret = Reverse(ret);
return ret;
}
};第三题：大数乘法
牛客网做题链接：大数乘法_牛客题霸_牛客网 (nowcoder.com)
思路：
在大数乘法中，我们采用了一种累积相加的方法，即先不立即处理进位，而是将所有乘法结果累积到它们对应的位置上。这个过程通常是在将参与乘法的两个大数以字符串形式逆序（即最低位在前）之后进行的，以便从个位开始相乘。
具体来说，我们维护一个数组（或类似的数据结构）来存储乘法结果的累积和。对于字符串中的每一个字符（代表数字），我们将其与另一个字符串中的每一个字符相乘，并将乘积放置在一个新数组中的特定位置，这个位置由两个字符在原字符串中的下标之和决定。例如，如果第一个字符串中的数字7（下标为0）与第二个字符串中的数字9（下标也为0）相乘，那么乘积就累积到新数组的下标0位置。同样地，如果第一个字符串中的数字6（下标为1）与第二个字符串中的数字9（下标为0）相乘，乘积则累积到新数组的下标1位置。如果还有其他组合（如第一个字符串的7与第二个字符串的8）也产生结果在下标1，则这些结果会相加。
重要的是，在累积过程中，我们使用加法赋值操作符（+=）来确保相同位置上的多个乘积能够正确相加。这是因为，在乘法运算中，同一个位置可能会由多个不同的数字对相乘得到的结果所贡献。
最终，这个累积了所有乘法结果的数组（或数据结构）将包含处理进位之前的所有信息，接下来我们可以对这个数组进行进位处理，以得到最终的大数乘法结果。
class Solution {
public:
string solve(string s, string t)
{
string ret;
reverse(s.begin(), s.end());
reverse(t.begin(),t.end());
int m = s.size(), n = t.size();
vector<int> nums(m + n);
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
{
nums[i+j] += (s[i] - '0') * (t[j] - '0');
}
n = 0;
for(int i = 0; i < nums.size(); i++)
{
nums[i] += n;
ret += nums[i] % 10 + '0';
n = nums[i] / 10;
}
while(n)
{
ret += n + '0';
n /= 10;
}
while(ret.size() > 1 && ret.back() == '0') ret.pop_back();
reverse(ret.begin(), ret.end());
return ret;
}
};学习编程就得循环渐进，扎实基础，勿在浮沙筑高台
腾讯云开发者
