iT邦幫忙

DAY 23
1

連續30天,挑戰演算法系列 第 23

[Day23] 30 天挑戰演算法 - 加一

題目來源Plus One

問題:
給予一個 非負數 的數字,並且使用陣列方式呈現,請將該數字加一後回傳。

例子
例如: Number = [9, 9, 9, 9], 加1後請回傳 [1, 0, 0, 0, 0]
例如: Number = [1, 4], 加1後請回傳 [1, 5]

想法
關於這題,只要把握住一個原則,那就是 進位,其他就搞定了!如果最左邊的數字沒有進位,就不用在新增一個陣列回傳。如果最左邊的數字有進位,就必須要新增一個陣列 其大小為 原來陣列大小+1。

所以,整理一下重點:

  1. 最左邊的數字是否有進位。
  2. 其他數字是否有進位。

以數字來說,由小到大是由右到左,而使用 array 呈現是從 index N-1 到 index 0 (N是 array 的大小),所以我們的 for 迴圈就要從 N-1 到 0

for (int i = digits.length -1; i>=0; i-- )

接下來在嘗試去判斷 +1 後 是否有進位,若有進位,就把該 index 的值設成0,再使用 carrylast 當記號。

if (digits[i] + 1 > 9) {
    digits[i] = 0;
    carrylast = true;
} else {
    digits[i] += 1;
    carrylast = false;
    break;
}    

如果所有的陣列中的數字都有進位的話,最後的 carrylast 會等於 True,這時候就代表原來的陣列大小不敷使用,必須新建一個 +1 的新陣列。

if (carrylast) {
    int[] result = new int[digits.length+1];
    result[0] = 1; // 這裡是進位
    for (int i=1; i<digits.length; i++)
        result[i+1] = digits[i];
    return result;
}

最後,如果最左邊沒進位呢?那就直接回傳被 +1 陣列就可以了!

public int[] plusOne(int[] digits) {
    boolean carryLast = false;
    
    for(int i=digits.length-1; i>=0; i--) {
        if ( digits[i] + 1 > 9) {
            digits[i] = 0;
            carryLast = true;
        } else {
            digits[i] += 1;
            carryLast = false;
            break;  // 之後不會再有進位了,就直接脫離迴圈吧
        }
    }        
    
    if (carryLast) {
        int[] result = new int[digits.length+1];
        result[0] = 1;
        for(int i=0; i<digits.length; i++)
            result[i+1] = digits[i];
        return result;
    }
    

    return digits;
}

上一篇
[Day22] 30 天挑戰演算法 - 合併兩個已排序的陣列
下一篇
[Day24] 30 天挑戰演算法 - 反轉文字字串
系列文
連續30天,挑戰演算法30

尚未有邦友留言

立即登入留言