当前位置: 首页 > article >正文

高精度加法,高精度乘法,高精度除法,高精度减法,链表相加

文章目录

  • 高精度加法
  • 大数相加
    • 题解
    • 代码
  • 高精度乘法
  • 大数乘法
    • 题解
    • 代码
  • 高精度除法
    • 题解
    • 代码
  • 高精度减法
    • 题解
    • 代码
  • 链表相加(二)
    • 题解
    • 代码
  • 总结

高精度加法

大数相加

题目链接
在这里插入图片描述

题解

1. 可以将字符串转换为一个一个的字符相加,注意进位,从后向前加,就是你小学的计算
2. 只要存在进位,就继续加,字符串长度不同,加到长的字符串结束为止

代码

// 解法一:
class Solution 
{
public:
    string solve(string s, string t) 
    {
        int a[100000] = {0},b[100000] = {0},c[100000] = {0};
        int mn = 0;
        int m = s.size();
        int n = t.size();
        mn = max(m,n);
        
        for(int i = m-1;i >= 0;i--) a[m-1-i] = s[i] - '0';
        for(int i = n-1;i >= 0;i--) b[n-1-i] = t[i] - '0';
        
        for(int i = 0;i < mn;i++)
        {
            c[i] += a[i] + b[i];
            c[i+1] = c[i] / 10;// 进位
            c[i] %= 10;// 比如 9 + 9 = 18 % 10 = 8  
        }	
        if(c[mn]) mn++;
        string p = "";
        for(int i = mn-1;i >= 0;i--)
        { 
            p += (c[i] + '0');
        }

        return p;
    }
};

// 解法二:
class Solution 
{
public:
    string solve(string s, string t) 
    {
        string ret;
        int i = s.size() - 1;
        int j = t.size() - 1;
        int tmp = 0;// 进位
        while(i >= 0 || j >= 0 || tmp)
        {
            if(i >= 0) tmp += s[i--] - '0';
            if(j >= 0) tmp += t[j--] - '0';
            ret += tmp % 10 + '0';
            tmp /= 10;// 进位
        }
        reverse(ret.begin(),ret.end());

        return ret;
    }
};

高精度乘法

大数乘法

题目链接
在这里插入图片描述

题解

1. 无进位相乘再相加,下标在相加的位置可以得到这样的结论:下标相加相等的数,等于最后结果相加在一起,比如4和7,下标相加为1,5和6,下标相加为1,28和30都在1下标下
2. 处理进位:把个位都加入到string ret后面,进位往前加,如果最后还剩下一个进位没处理,使用while循环处理
3. 处理前导0:逆置后才是答案,所以保证数字长度大于1的前提下,如果末尾存在0就删除,比如12300->123

在这里插入图片描述

代码

class Solution 
{
public:
    string solve(string s, string t) 
    {
       // 1.无进位相乘再相加
       reverse(s.begin(),s.end());
       reverse(t.begin(),t.end());
       int m = s.size();
       int n = t.size();
       vector<int> tmp(m+n);

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

       // 2.处理进位
       int c = 0;
       string ret;
       for(auto x : tmp)
       {
           c += x;
           ret += c % 10 + '0';
           c /= 10;
       }

       while(c)
       {
          ret += c % 10 + '0';
          c /= 10;
       }
     
       // 3. 处理前导0
       while(ret.size() > 1 && ret.back() == '0') ret.pop_back();
       
       reverse(ret.begin(),ret.end());

       return ret;
    }
};

高精度除法

题解

1. 高精度数除以普通整数
2. 用被除数的每一位除以除数,除完之后的余数乘10加上后面的数,除完就打印每一位数
3. 注意1234/5000和0/1的条件判断

在这里插入图片描述

代码

#include<iostream>
#include<string>
#include<vector>

using namespace std;


int main()
{
	string s;
	int b;
	vector<int> ret;
	cin >> s >> b;

	int n = s.size();
	for (int i = 0; i < n; i++) ret.push_back(s[i] - '0');

	int x = 0;
	bool flag = true;
	for (int i = 0; i < n; i++)
	{
		x = x * 10 + ret[i];
        
		// 第一个数,1234 / 5000 = 0, 0 / 1 = 0
		// 只限制了第一次出现全部0的前导0,把第一次
		// 出现的全部都删除了
		if (flag && x / b == 0 && i < n - 1) continue;
		flag = false;

		cout << x / b;
		x %= b;
	}
	cout << " ";
	cout << x << '\n';

	return 0;
}

高精度减法

题目链接
在这里插入图片描述

题解

1. 始终保证第一个数比第二个数大,如果第一个数比第二个数小,记得标记负号,交换两个数的长度和字符串保证第一个始终比第二个数大
2. 逆序存入数组a,b中,因为从低位开始减
3. 借位和存差值到c数组中
4. 记得消除前导零,消除一个零长度减一,如果都是0全消除了,记得判断长度为0时输出0并返回
5. 如果是负数记得加上负号,并且逆序输出

代码

#include<iostream>
#include<string>

using namespace std;
const int N = 1e5 + 10;
int a[N], b[N], c[N];


int main()
{
	string s, t;
	cin >> s >> t;
    
	int m = s.size();
	int n = t.size();
	int p = m > n ? m : n;

	// 判断是否有负号
	int tt = 0;
	if (n > m || (m == n && s.compare(t) < 0))
	{
		tt = 1;
		swap(s, t);
		swap(m, n);
	}

	// 倒序存储数字
	for (int i = 0; i < m; i++) a[i] = s[m - i - 1] - '0';
	for (int i = 0; i < n; i++) b[i] = t[n - i - 1] - '0';


	// 借位 存差
	for (int i = 0; i < p; i++)
	{
		if (a[i] < b[i])
		{
			a[i + 1]--;
			a[i] += 10;
		}
		c[i] = a[i] - b[i];
	}

	// 处理前导0
	while (p && c[p - 1] == 0) p--;
	if (p == 0)
	{
		cout << 0 << '\n';
		return 0;
	}

	// 加负号
	if (tt)
	{
		cout << '-';
	}

	for (int i = p - 1; i >= 0; i--) cout << c[i];
	cout << '\n';

	return 0;
}

链表相加(二)

题目链接
在这里插入图片描述

题解

1. 先头插把链表进行逆序,逆序完后可以进行高精度加法,得到最终的答案
2. 注意创建一个虚拟节点更好做

在这里插入图片描述

代码

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution 
{
public:
    ListNode* Listreverse(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;
        newhead = nullptr;
        delete newhead;
        return cur;
    }
    ListNode* addInList(ListNode* head1, ListNode* head2) 
    {
        // 1.逆置,头插
        ListNode* cur1 = Listreverse(head1);  
        ListNode* cur2 = Listreverse(head2);
        
        // 2.高精度加法
        ListNode* ret = new ListNode(0);
        int t = 0;// 进位
        ListNode* pre = ret;
        while(cur1 || cur2 || t)
        {
            if(cur1)
            {
                t += cur1->val;
                cur1 = cur1->next;
            }
            if(cur2)
            {
                t += cur2->val;
                cur2 = cur2->next;
            }
            pre->next = new ListNode(t % 10);
            pre = pre->next;
            t /= 10;
        }
        ListNode* cur = ret->next;
        ret = nullptr;
        delete ret;
        return Listreverse(cur);
    }
};

总结

1. 高精度加减乘都是从后往前处理的,唯独高精度除法是从前往后处理的
2. 高精度减乘除法需要处理前导0,高精度加法不需要从处理前导0,比如823 + 242 -> 328 + 242 = 5601 -> 1065
3. 高精度加法逆序数组,处理进位,逆序打印,高精度减法,处理负号,逆序存储,处理借位,处理前导零,是否加负号,逆序打印数组,高精度乘法,无进位相乘再相加,处理进位,处理前导零,逆序打印,高精度除法,每次处理商,处理余数,处理前导零
4. 基本的做题步骤:
1、将数组逆置
2、处理进位/借位
3、处理前导零
4、逆序打印数组


http://www.kler.cn/a/589638.html

相关文章:

  • 如何仅在conda中更新gcc版本
  • 什么是数学建模?数学建模是将实际问题转化为数学问题
  • Linux服务器跑python脚本定时任务
  • AIP-181 稳定级别
  • fastapi+angular实现个人博客
  • 什么是死锁?如何避免死锁?
  • 【spring boot 实现图片验证码 前后端】
  • ESP32学习 -从STM32工程架构进阶到ESP32架构
  • MySQL 性能优化:索引优化 + 读写分离 + Redis 缓存,TPS 提升 175% 实战解析
  • 《Classifier-Free Diffusion Guidance》的核心观点与方法
  • 三层架构与MVC架构的本质:从设计思想到实战选择
  • 贝叶斯网络的基本概念并构建一个贝叶斯网络(实例)
  • QT 磁盘文件 教程04-创建目录、删除目录、遍历目录
  • IntelliJ IDEA 中 Maven 的 `pom.xml` 变灰带横线?一文详解解决方法
  • 微服务即时通信系统---(八)用户管理子服务
  • 2025交易所开发突围:AI增强型撮合引擎与零知识证明跨链架构
  • 有趣的算法实践:整数反转与回文检测(Java实现)
  • java学习总结(六)Spring IOC
  • 基于k3s部署Nginx、MySQL、Golang和Redis的详细教程
  • 一键爬取b站视频