算法笔记day03

目录

1. 大数加法

2.链表相加(二)

3.大数乘法

---

1. 大数加法

大数加法_牛客题霸_牛客网

算法思路：

这就是一道模拟题，模拟加法列竖式运算的过程。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算两个数之和
     * @param s string字符串 表示第一个整数
     * @param t string字符串 表示第二个整数
     * @return string字符串
     */
    string solve(string s, string t) 
    {
        int m = s.size() -1, n = t.size() -1;

        int tmp = 0;//保存进位
        string ret; 
        while (m >= 0 || n >= 0 || tmp) 
        {
            if(m >= 0)
            {
                tmp += s[m--] - '0';
            }

            if(n >= 0)
            {
                tmp += t[n--] - '0';
            }

            ret += tmp % 10 + '0';
            tmp /= 10;
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

2.链表相加(二)

链表相加(二)_牛客题霸_牛客网

算法思路：

这道题与上一道题类似，只不过换成了链表，只需要注意第一步一定要先将链表逆置，其他的步骤与上一题相同。

/**
 * 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) 
    {
        head1 = reverse(head1);
        head2 = reverse(head2);
        int tmp = 0;
        ListNode * cur1 = head1;
        ListNode * cur2 = head2;
        ListNode * ret = new ListNode(0);
        ListNode * prev = ret;    
        while (cur1 || cur2 || tmp) 
        {
            if(cur1)
            {
                tmp += cur1->val;
                cur1 = cur1->next;
            }

            if(cur2)
            {
                tmp += cur2->val;
                cur2 = cur2->next;
            }

            prev->next = new ListNode(tmp % 10);
            prev = prev->next;
            tmp /= 10;
        }

        prev = ret;
        ret = ret->next;
        delete prev;
        ret = reverse(ret);
        return ret;
    }
};

3.大数乘法

大数乘法_牛客题霸_牛客网

算法思路：

同样也是一道模拟题，使用无进位相乘相加进行优化。

使用数组将每一位都存储起来，最后统一处理进位

#include <iterator>
class Solution {
public:
    string solve(string s, string t) 
    {
        reverse(s.begin(), s.end());
        reverse(t.begin(), t.end());

        string ret;
        int n = s.size(), m = t.size();
        vector<int> v(m + n);

        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                v[i + j] += (s[i] - '0') * (t[j] - '0');
            }
        }

        //处理进位
        int c = 0;
        for(int x : v)
        {
            c += x;
            ret += c % 10 + '0';
            c /= 10;
        }

        while(c)
        {
            ret += c % 10 + '0';
            c /= 10;
        }

        while(ret.size() > 1 && ret.back() == '0')
        {
            ret.pop_back();
        }

        reverse(ret.begin(), ret.end());
        return ret;
    }
};

原文地址：https://blog.csdn.net/W2155/article/details/142847808

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！