數(shù)組實現(xiàn)整數(shù)加法

問題描述

給定一個由 整數(shù) 組成的 非空 數(shù)組所表示的非負整數(shù)，在該數(shù)的基礎(chǔ)上加一。最高位數(shù)字存放在數(shù)組的首位， 數(shù)組中每個元素只存儲單個數(shù)字。你可以假設除了整數(shù) 0 之外，這個整數(shù)不會以零開頭。詳見leetcode66

問題分析

可以從數(shù)組的末尾，即length-1下標處開始向前遍歷，末尾元素?1，如果沒有進位，直接返回該數(shù)組（例如 123+1->124），如果有進位，前一位繼續(xù)加一，直至沒有進位(例如 19+1->20)，如果循環(huán)結(jié)束，仍有進位，則需要創(chuàng)建一個比原數(shù)組長度增加1的數(shù)組，將首元素置為1，進行返回(例如 99+1->100)。

代碼實現(xiàn)

public int[] plusOne(int[] digits) {
    for(int i=digits.length-1;i>=0;i--){
        digits[i]++;
        digits[i]%=10;
        if(digits[i]!=0){
            return digits;
        }
    }
    digits = new int[digits.length+1];
    digits[0] = 1;
    return digits;
}

字符串加法

問題描述

給定兩個字符串形式的非負整數(shù)，計算他們的和并仍然以字符串的形式返回。

問題分析

從兩個字符串末尾字符依次向前遍歷，取對應位的字符進行加法，設置進位標識，結(jié)果可通過StringBuilder進行存儲。最后反轉(zhuǎn)即可。

代碼實現(xiàn)

public static String plusString(String str1, String str2) {
    int i = str1.length() - 1;
    int j = str2.length() - 1;
    int add = 0;
    int x;
    int y;
    StringBuilder sb = new StringBuilder();
    while (i >= 0 || j >= 0 || add != 0) {
        if (i >= 0) {
            x = str1.charAt(i) - '0';
        } else {
            x = 0;
        }
        if (j >= 0) {
            y = str2.charAt(j) - '0';
        }else {
            y = 0;
        }
        int result = x + y + add;
        sb.append(result%10);
        if(result/10 == 1){
            add = 1;
        }else{
            add = 0;
        }
        i--;
        j--;
    }
    return sb.reverse().toString();
}

二進制加法

問題描述

給你兩個二進制字符串 a 和 b ，以二進制字符串的形式返回它們的和。詳見leetcode67

問題分析

仍然是兩個字符串末尾字符依次向前遍歷，取對應位的字符進行加法，設置進位標識，結(jié)果可通過StringBuilder進行存儲。最后反轉(zhuǎn)即可。只是結(jié)果取模和判斷進位與十進制有所不同，詳見代碼實現(xiàn)

代碼實現(xiàn)

public String addBinary(String a, String b) {
   int i = a.length() - 1;
    int j = b.length() - 1;
    int add = 0;
    int x;
    int y;
    StringBuilder sb = new StringBuilder();
    while(i>=0 || j>=0 || add!=0){
        if(i>=0){
            x = a.charAt(i)-'0';
        }else{
            x = 0;
        }
        if(j>=0){
            y = b.charAt(j)-'0';
        }else{
            y = 0;
        }
        int sum = x + y + add;
        sb.append(sum%2);
        add = sum / 2;
        i--;
        j--;
    }
    if(add == 1){
        sb.append(1);
    }
    return sb.reverse().toString();
}

總結(jié)與拓展

數(shù)組和字符串(本質(zhì)上是字符數(shù)組)的加法其實只需要盡心遍歷相加即可，但是數(shù)字是從低位到高位相加，而字符串是從高位到低位存儲。所以需要反響遍歷，并且注意進位，通過十進制與二進制的加法，可以拓展到任意進制的加法，只是在結(jié)果取模和判斷進位時有所不同。

文章來源地址http://www.zghlxwxcb.cn/news/detail-695891.html

到了這里，關(guān)于算法通關(guān)村-----數(shù)組實現(xiàn)加法專題問題解析的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！