[Leetcode] Plus One 加一

shmily 發(fā)布于2019-08-14 12:36 / 3382人閱讀

摘要：不過這里有個小技巧，因為我們只要加，所以不用完全模擬加法的所有規(guī)則一個數(shù)如果不是，那加以后不會對其他位產(chǎn)生影響。

Plus One

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

遇九置零法 復(fù)雜度

時間 O(N) 空間 O(1)

思路

簡單的加法運算。這里需要注意的是，數(shù)字的最高位的下標(biāo)是0，最低位下標(biāo)是length-1，所以我們要從后向前模擬加法。不過這里有個小技巧，因為我們只要加1，所以不用完全模擬加法的所有規(guī)則：一個數(shù)如果不是9，那加1以后不會對其他位產(chǎn)生影響。根據(jù)這個思路，我們先把末尾所有連續(xù)的9置0，然后對從后往前第一個不是9的數(shù)加1就行了。如果越界的話，說明原數(shù)全是9，那就要建個新數(shù)組存放結(jié)果。

注意

System.arraycopy(src, 0, dst, 0, length) 可以用來高效拷貝數(shù)組

代碼

public class Solution {
    public int[] plusOne(int[] digits) {
        int i = digits.length - 1;
        // 從后向前把所有連續(xù)9置0，直到不是9
        while(i >= 0 && digits[i] == 9){
            digits[i] = 0;
            i--;
        }
        // 如果越界，則拷貝一個新數(shù)組并在最前面置1
        if(i < 0){
            int[] res = new int[digits.length + 1];
            System.arraycopy(digits, 0, res, 1, digits.length);
            res[0] = 1;
            return res;
        } else {
        // 否則，將第一個不是9的數(shù)字加1就行了
            digits[i] += 1;
            return digits;
        }
    }
}

GPU云服務(wù)器云服務(wù)器 LeetCode LeetCode_String leetcode_35_SearchIn one()

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64583.html

相關(guān)文章

Leetcode加一（java、python3）

摘要：加一給定一個由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)，在該數(shù)的基礎(chǔ)上加一。示例輸入輸出解釋輸入數(shù)組表示數(shù)字。思路指針從最后往前移動，若值為逐個加一，并賦值。不等于則退出循環(huán)。首位如果為是則證明需要進一。只需首位賦值即可。加一給定一個由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)，在該數(shù)的基礎(chǔ)上加一。最高位數(shù)字存放在數(shù)組的首位，數(shù)組中每個元素只存儲一個數(shù)字。你可以假設(shè)除了整數(shù) 0 之外，這個...

沈建明 2019-07-31 10:30 評論0 收藏0
Leetcode加一（java、python3）

摘要：加一給定一個由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)，在該數(shù)的基礎(chǔ)上加一。示例輸入輸出解釋輸入數(shù)組表示數(shù)字。思路指針從最后往前移動，若值為逐個加一，并賦值。不等于則退出循環(huán)。首位如果為是則證明需要進一。只需首位賦值即可。加一給定一個由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)，在該數(shù)的基礎(chǔ)上加一。最高位數(shù)字存放在數(shù)組的首位，數(shù)組中每個元素只存儲一個數(shù)字。你可以假設(shè)除了整數(shù) 0 之外，這個...

Apollo 2019-08-16 17:51 評論0 收藏0
leetcode66 將數(shù)組表示的非負(fù)整數(shù)加一

摘要：題目要求一個非負(fù)整數(shù)被表示為一個數(shù)組，數(shù)組中每一個元素代表該整數(shù)的一個位。數(shù)組的下標(biāo)越小，代表的位數(shù)越高。現(xiàn)在對該數(shù)組做加一運算，請返回結(jié)果數(shù)組。題目要求：一個非負(fù)整數(shù)被表示為一個數(shù)組，數(shù)組中每一個元素代表該整數(shù)的一個位。數(shù)組的下標(biāo)越小，代表的位數(shù)越高?，F(xiàn)在對該數(shù)組做加一運算，請返回結(jié)果數(shù)組。 /** * @author rale * * Given a non-negativ...

QLQ 2019-08-14 17:50 評論0 收藏0
leetcode 66 Plus One

摘要：題目詳情題目的意思是，給你一個用數(shù)組表示的一個非負(fù)整數(shù)。你需要返回這個整數(shù)加后，所對應(yīng)的數(shù)組。解法一主要需要關(guān)注的點就在于，當(dāng)末尾數(shù)字為的時候的進位情況。如果不需要進位了，則代表循環(huán)可以結(jié)束了。題目詳情 Given a non-negative integer represented as a non-empty array of digits, plus one to the in...

ytwman 2019-08-14 18:35 評論0 收藏0
[LeetCode/LintCode] Plus One

Problem Given a non-negative number represented as an array of digits, plus one to the number. The digits are stored such that the most significant digit is at the head of the list. Example Given [1,2...

sunsmell 2019-08-14 15:17 評論0 收藏0