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

目录

字符串相加

字符串相乘

二进制求和

千位分隔数


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

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

字符串相加

字符串相加

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

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

示例 1:

输入:num1 = “11”, num2 = “123”
输出:“134”

示例 2:

输入:num1 = “456”, num2 = “77”
输出:“533”

示例 3:

输入:num1 = “0”, num2 = “0”
输出:“0”

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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)直接将输入转换为整数来处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
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;
}



}

算法零基础——大数四则运算
http://example.com/2021/11/30/算法零基础——大数四则运算/
作者
Zevin
发布于
2021年11月30日
许可协议