算法零基础——大数四则运算

原 作者 许泽文 | 发表于 | 分类于 2021级

目录

字符串相加

字符串相乘

二进制求和

千位分隔数

我们知道无论任何类型都有数字的最大范围，所以我们如果想要对于任何两个数都能够进行

四则运算，那么我们就可以运用一个字符串进行运算

字符串相加

字符串相加

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

示例 1：

输入：num1 = "11", num2 = "123"
输出："134"

示例 2：

输入：num1 = "456", num2 = "77"
输出："533"

示例 3：

输入：num1 = "0", num2 = "0"
输出："0"

我们想要对字符串进行运算，所以我们要对字符串进行反转

char *reverse(char * s)
{
    int len=strlen(s);
    int i=0;
    for(i=0;i<len/2;i++)
    {
        char c=s[i];
        s[i]=s[len-1-i];
        s[len-1-i]=c;
    }
    return s;
}
char * addStrings(char * num1, char * num2)
{
int i,n1,n2,now,cap;
cap=0;//cap用来计算进位的，逢10进1，所以cap只有0或1
int len1=strlen(num1);//计算num1的长度
int len2=strlen(num2);//计算num2的长度
reverse(num1);
reverse(num2);
int max=len1>len2?len1:len2;//两个数相加，最大的可能长度就是，两者最大长度+1，要不然就是两者的最大值
char *c=(char *)malloc(sizeof(char)*(max+2));//我们把加后的数字存储到c里面，由于字符串的结束标志是‘\0’，所以我们开辟的时候多开辟一点
for(i=0;i<max;i++)
{
    n1=i<len1?num1[i]-'0':0;//i<len1的话，数字都是可以的，到len的话num1后就没有数字了，
    n2=i<len2?num2[i]-'0':0;//同理
    int now=n1+n2+cap;//now就是还没进位的数，每个位置数有可能是个两位数
    cap=now/10;//cap处理进位
    c[i]=(now%10)+'0';//%10就是现在的数+‘0’就是个字符了

}
if(cap)
{
    c[i]='1';//如果cap处理进位后变成了1，那么最高位进1
    max++;//同时长度增长
}
c[max]='\0';//最后要把最后一位变成‘\0’作为字符串的结束标志，与他反转无关，字符串结束就要加个‘\0’
reverse(c);//最后再把c给转过来
return c;
}

字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

说明：

  1. num1 和 num2 的长度小于110。
  2. num1 和 num2 只包含数字 0-9。
  3. num1 和 num2 均不以零开头，除非是数字 0 本身。
  4. 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
char *reverse(char *s)
{
    int len=strlen(s);
    for(int i=0;i<len/2;i++)
    {
        char tmp=s[i];
        s[i]=s[len-1-i];
        s[len-1-i]=tmp;
    }
    return s;
}

char * multiply(char * num1, char * num2){
int i,j;
int len1=strlen(num1);
int len2=strlen(num2);
int len=len1+len2;//字符串相乘的长度，最大是两个长度相加
int *mul=(int *)malloc(sizeof(int)*(len+5));//我们开辟一个相乘后的字符串数组，长度要多开辟一点，避免最后数组越界,多出来的部分我们可以在后面进行处理
char*ret=(char*)malloc(sizeof(char)*(len+5));
memset(mul,0,sizeof(int)*(len+5));//再memset里面，我们最好用sizeof(int)*计算数组的长度，而不用sizeof(mul),
reverse(num1);
reverse(num2);
for(i=0;i<len1;i++)
{
    for(j=0;j<len2;j++)
    {
        mul[i+j]+=(num1[i]-'0')*(num2[j]-'0');//根据竖式计算，第i位和第j位的数相乘会再第i+j位上，同时i+j位会有多个数字运算
    }
}
for(i=0;i<len;i++)//因为mul我们多开辟了空间，所以他的长度可以到len而不越界
{
    mul[i+1]+=mul[i]/10;//第i+1位需要进位，是前一位/10出来的
    mul[i]%=10;//每一位需要%10，才得出了真实的每一位
}
//由于我们不知道相乘后的长度，所以我们要处理反转后的前导0
while(len>1&&mul[len-1]==0)//当len-1位是0是长度减减1
{
    len--;
}
//最后把数字转化成一个字符串
for(i=0;i<len;i++)
{
    ret[i]=mul[i]+'0';//数字+‘0’就变成了一个字符
}
ret[len]='\0';//把最后一位赋值为‘\0’，作为字符串的结束标志
reverse(ret);//把ret反转后就是运算后的结果
return ret;
}

二进制求和

二进制求和

给你两个二进制字符串，返回它们的和（用二进制表示）。

输入为 非空 字符串且只包含数字 1 和 0。

示例 1:

输入: a = "11", b = "1"
输出: "100"

示例 2:

输入: a = "1010", b = "1011"
输出: "10101"
char *reverse(char *s)
{
    int len=strlen(s);
    for(int i=0;i<len/2;i++)
    {
        char tmp=s[i];
        s[i]=s[len-1-i];
        s[len-1-i]=tmp;
    }
    return s;
}
char * addBinary(char * a, char * b)
{
int lena=strlen(a);
int lenb=strlen(b);
int maxlen=lena>lenb?lena:lenb;
reverse(a);
reverse(b);
char *ret=(char*)malloc(sizeof(char)*(maxlen+2));
int av,bv,now,cap=0;
int i=0;
for(i=0;i<maxlen;i++)
{
av=(i<lena)?(a[i]-'0'):0;
bv=(i<lenb)?(b[i]-'0'):0;
now=av+bv+cap;
cap=now/2;
ret[i]=now%2+'0';
}
if(cap)
{
    ret[i]='1';
maxlen++;
}
ret[maxlen]='\0';
reverse(ret);
return ret;



}

千位分隔数

千位分隔数

给你一个整数 n，请你每隔三位添加点（即 "." 符号）作为千位分隔符，并将结果以字符串格式返回。

示例 1：

输入：n = 987
输出："987"

示例 2：

输入：n = 1234
输出："1.234"

示例 3：

输入：n = 123456789
输出："123.456.789"

示例 4：

输入：n = 0
输出："0"

char * reverse(char*n)//逆序
{

int len=strlen(n);
for(int i=0;i<len/2;i++)
{
    char tmp=n[i];
    n[i]=n[len-1-i];
    n[len-1-i]=tmp;
}

return n;

}
char * thousandSeparator(int n){
    //首先先求出n是几位数
    //将n转化为一个字符串
    //记录字符串的长度
    //把n逆序
    //每三位就加个点，同时后面的位数往后挪，len++，要注意的是，加点之后，数组i对应的就变化了
，要对这个点进行处理
    //最后再逆序
    int x=n;
    if(n==0)//当他为0的情况下，在计算长度时候不会进入计算，所以要单独拿出来写
    {
        return "0";
    }
    else
    {
    int len=0;
    while(n)
    {
        n/=10;
        len++;//记录他的长度
    }
    int i=0;
    char*num=(char*)malloc(sizeof(char)*(len+(len-1)/3+4));//(len-1)是为了避免假如最后也是3位而多大的点，同时+4是为了让他不越界
    for(i=0;i<len;i++)
    {
        if(x)
        {
        num[i]=x%10+'0';
        x/=10;
        }
    }
 num[i]='\0';//'\0'作为字符串结束的标志，必须要写，不然是不合法的
    
int k=0;//因为每次加一个点，则num对应的下标所对应的元素就会发生变化
for(i=0;i<len-k;i++)//-k是为了保证每次移动他的下标对应的值不发生变换
{
    if(i>1&&i%3==0)//
    {
        
        int end=len;
        while(end>=i+k)//每次加点后i包含了点，所以也要往后挪
        {
            num[end+1]=num[end];//遇到了就往后挪，空出位置给‘.’
            end--;
        }
        len++;
       num[i+k]='.';
       k++;//要先给i+k赋值才能++，否则i+k的值就变了
    }
}
reverse(num);
return num;
    }
    


}