0%

leetcode——两数相加

发表于 分类于

题目描述

请设计一个算法完成两个超长正整数的加法。

接口说明

/*
请设计一个算法完成两个超长正整数的加法。
输入参数：
String addend：加数
String augend：被加数
返回值：加法结果
*/

public String AddLongInteger(String addend, String augend)
{
/在这里实现功能/

return null;
}

本题有多组输入数据，请使用while(cin>>)等方式读取

输入描述:

  • 输入两个字符串数字

输出描述：

  • 输出相加后的结果，string型

示例1

输入

1
2
99999999999999999999999999999999999999999999999999
1

输出

1
100000000000000000000000000000000000000000000000000

讲解

这个题目第一次做的时候是在去年做网易的笔试题目的时候，当时用的语言还是c++，但是无从下手，不知道该怎么解决这个问题，昨天刷leetcode每日一题的时候，又重新看到了这个题目，所以很系统的了解一下应该如何去处理这样的题目，因为leetcode只需要写算法，不需要整个写输入输出，所以特地去牛客网上找到相同的题目又重新写了一遍。

算法其实不难，但是我们整体用到的知识点就是如何从尾部相加，我们用两个指针i，j分别指向加数和被加数的尾部，然后一个个相加，并用StringBuilder存储结果，最后将StringBuilder逆序并且转化为String类型。下面提供一个我自己写的代码：

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
import java.util.*;


public class Main{
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String  add1 = sc.nextLine();
            String add2 = sc.nextLine();
            String res = AddLongInteger(add1, add2);
            System.out.println(res);
        }
        
    }
    
    private static String AddLongInteger(String add1, String add2){
        int m = add1.length();
        int n = add2.length();
        int c = 0;
        StringBuilder sb = new StringBuilder();
        int i=m-1;
        int j = n-1;
        while(i>=0 || j>=0 || c ==1){
            int a1 = i>=0?add1.charAt(i)-'0':0;
            int a2 = j>=0?add2.charAt(j)-'0':0;
            int sum = a1+ a2+ c;
            sb.append(sum %10);
            c = sum/10;
            i--;
            j--;
        }
        return sb.reverse().toString();
    }
}