算法问题——大数相加的方法

415. 字符串相加（大数相加问题）

/**
 * Copyright (C), 2018-2020
 * FileName: addStrings415
 * Author:   xjl
 * Date:     2020/8/3 9:30
 * Description: 给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。
 */
package String;

import java.util.Scanner;

public class addStrings415 {
    public static String addStrings(String num1, String num2) {
        //从尾部开始计算
        int i = num1.length() - 1, j = num2.length() - 1, add = 0;
        //存储结果
        StringBuffer ans = new StringBuffer();
        //遍历
        while (i >= 0 || j >= 0 || add != 0) {
            int x = i >= 0 ? num1.charAt(i) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j) - '0' : 0;
            int result = x + y + add;
            ans.append(result % 10);
            add = result / 10;
            i--;
            j--;
        }
        // 计算完以后的答案需要翻转过来
        ans.reverse();
        return ans.toString();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.nextLine();
        String s2 = sc.nextLine();
        String result = addStrings(s1, s2);
        System.out.println(result);
    }
}

其他的解法：利用的数组的方法

/**
 * Copyright (C), 2018-2020
 * FileName: MaxStringsum
 * Author:   xjl
 * Date:     2020/7/27 12:57
 * Description: 大数相加的和
 */
package Math;

import java.util.ArrayList;
import java.util.Scanner;

/**
 * 18798458748987589654887584
 * 875898748587968489578456984587
 */
public class MaxStringsum {
    public static void main(String[] args) {
        //数据的输入
        Scanner sc = new Scanner(System.in);
        String nums1 = sc.nextLine();
        String nums2 = sc.nextLine();

        //函数的调用
        String result = testmax(nums1, nums2);
        //结果的打印
        System.out.println(result);
    }

    private static String testmax(String nums1, String nums2) {
        nums1 = new StringBuffer(nums1).reverse().toString();
        nums2 = new StringBuffer(nums2).reverse().toString();
        //设置两个相同的数组存放数字
        int[] array1 = new int[nums1.length()];
        int[] array2 = new int[nums2.length()];
        for (int i = 0; i < array1.length; i++) {
            array1[i] = nums1.charAt(i) - '0';
        }
        for (int i = 0; i < array2.length; i++) {
            array2[i] = nums2.charAt(i) - '0';
        }
        //存放结果
        ArrayList list = new ArrayList();
        int i = 0;
        int j = 0;
        //进位
        int current = 0;
        int a = 0, b = 0;
        while (i < array1.length || j < array2.length) {
            if (i == array1.length) {
                a = 0;
            } else {
                a = array1[i++];
            }
            if (j == array2.length) {
                b = 0;
            } else {
                b = array2[j++];
            }
            int sum = a + b + current;
            current = sum / 10;
            list.add(sum % 10);
        }
        if (current == 1) {
            list.add(current);
        }
        String res = "";
        for (int V : list) {
            res += String.valueOf(V);
        }
        return new StringBuffer(res).reverse().toString();
    }
}

利用的BigInter函数来处理大数问题

/**
 * Copyright (C), 2018-2020
 * FileName: Bignumber
 * Author:   xjl
 * Date:     2020/7/28 16:25
 * Description: 大整数
 */
package Math;

import java.math.BigInteger;
import java.util.Scanner;

/**
 * 相加：add(BigInteger val);
 *    相减：subtract(BigInteger val);
 *    相乘：multiply(BigInteger val);
 *    相除：divide(BigInteger val);
 *    最大公约数：gcd(BigInteger val);
 *    取模：mod(BigInteger val);
 *    N次方：pow(int exponent);
 *
 */
public class Bignumber {
    public static void main(String[] args) {
        //相加
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
        BigInteger x1 = new BigInteger(str1);
        BigInteger x2 = new BigInteger(str2);
        //相加
        BigInteger sum = x1.add(x2);
        System.out.println(x1.add(x2));
        //相乘
        BigInteger and=x1.multiply(x2);
        System.out.println(and);
    }
}

面试题 02.05. 链表求和

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //初始进位为0
        int pre = 0;
        //操作数
        ListNode mid = new ListNode(0);
        //返回头节点
        ListNode anws = mid ;
        //当l1和l2都不为null时进入while循环
        while(l1!=null&&l2!=null){
            //操作数赋值
            mid.val = (l1.val+l2.val+pre)%10;
            //更新进位
            pre = (l1.val+l2.val+pre)/10;
            //更新头节点
            l1 = l1.next;
            l2=l2.next;
            //头节点更新后判断是否为空
            if(l1==null){
                //如果l1头节点为空且进位为0，则操作数的next直接为l2剩下的
                if(pre==0) {
                    mid.next = l2;
                    return anws;
                }else {
                    //如果有进位，则递归调用addTwoNumbers方法
                    mid.next = addTwoNumbers(l2,new ListNode(pre));
                    return anws;
                }
            }
            //同上
            if(l2 == null){
                if(pre==0) {
                    mid.next = l1;
                    return anws;
                }else {
                    mid.next = addTwoNumbers(l1,new ListNode(pre));
                    return anws;
                }
            }
            //l1 l2更新后都不为null，则设置操作数为0 进入下一次while循环
            mid.next =new ListNode(0);
            mid = mid.next;
        }
        //l1为null，直接不能进入上面while循环的情况下，直接返回l2
        if(l1==null){
            return l2;
        }//同上
        else if(l2 ==null){
            return l1;
        }
        return anws;
    }
}

2. 两数相加

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        //进位符
        int carry = 0;
        while (l1 != null || l2 != null) {
            //如果是等于空的时候要选择为0数进行加减
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            int sum=x + y + carry;
            carry=sum/10;
            int n =sum%10;
            //添加新的节点
            cur.next = new ListNode(n);
            //并将向下移动
            cur = cur.next;
            //分别在两个中进行下一个的操作
            if (l1 != null)
                l1 = l1.next;
            if (l2 != null)
                l2 = l2.next;
        }
        if (carry == 1) {
            cur.next = new ListNode(carry);
        }
        return pre.next;
    }
}