[LintCode] Big Integer Addition

i_garfileo 发布于2019-08-16 10:59 / 2847人阅读

Problem

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Notice

The length of both num1 and num2 is < 5100.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

Example

Given num1 = "123", num2 = "45"
return "168"

Solution

public class Solution {
    /*
     * @param num1: a non-negative integers
     * @param num2: a non-negative integers
     * @return: return sum of num1 and num2
     */
    public String addStrings(String num1, String num2) {
        //start from adding the last digits of num1, num2:
        //if the current sum > 10, save 1 in `carry`,
        //add to the front of StringBuilder sb
        //... doing this till both indice less than 0
        
        int i = num1.length()-1, j = num2.length()-1, carry = 0, curSum = 0;
        StringBuilder sb = new StringBuilder();
        while (i >= 0 || j >= 0 || carry == 1) {
            //Integer.valueOf(String.valueOf(char)) is to remind me that the value of char is mapped to the decimal value in ascii 
            int curNum1 = i >= 0 ? Integer.valueOf(String.valueOf(num1.charAt(i))) : 0;
            int curNum2 = j >= 0 ? Integer.valueOf(String.valueOf(num2.charAt(j))) : 0;
            int sum = carry + curNum1 + curNum2;
            curSum = sum % 10; carry = sum/10;
            sb.insert(0, curSum);
            i--; j--;
        }
        return sb.toString();
    }
}

云服务器 GPU云服务器 Addition LintCode big integer

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/70857.html

[LintCode/LeetCode] Range Addition

Problem Assume you have an array of length n initialized with all 0s and are given k update operations. Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each el...

endless_road 2019-08-16 12:46 评论0 收藏0
[LintCode] Hash Function

摘要：又用到了取余公式，推导出。用循环对数组各位进行转换和相乘和累加。因为第二个取余公式证明乘积取余与乘数相加后再取余等价于乘积取余，所以在每个循环内都进行一次取余，以免乘积太大溢出。 Problem In data structure Hash, hash function is used to convert a string(or any other type) into an int...

Dogee 2019-08-14 15:26 评论0 收藏0
[LintCode] Buy Fruits

Problem Xiao Ming is going to help companies buy fruit. Give a codeList, which is loaded with the fruit he bought. Give a shoppingCart, which is loaded with target fruit. We need to check if the order...

邱勇 2019-08-15 17:47 评论0 收藏0
[LintCode] Integer to Roman & Roman to Integer

摘要：建立映射整数数组字符串数组，这两个数组都要从大到小，为了方便之后对整数进行从大到小的分解，以便用从前向后建立数字。建立，存入的数值对应关系。 Problem Integer to RomanGiven an integer, convert it to a roman numeral.The number is guaranteed to be within the range fro...

pkwenda 2019-08-14 15:15 评论0 收藏0
[LintCode] Reverse Integer

摘要：这道题有一些细节需要留意。新数会不会溢出符号位如何处理用惯用的做法，除以取余，得到最低位，放进。每次循环乘以累加当前最低位，同时除以不断减小。要点在于考虑乘累加运算的情况，用分支语句判断发生溢出的条件。最后的结果要加上之前排除的符号位。 Problem Reverse digits of an integer. Returns 0 when the reversed integer o...

The question 2019-08-14 15:17 评论0 收藏0