66. 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.

這題是用陣列來存數字,然後加1 ，如果用其它語言寫應該很容易，像C++有vector，不過C處理起來就比較麻煩，要判斷最後需不需要進位去malloc記憶體的大小。

1.這邊要知道 a%10 用mod取個位數，a/10去取十位數 2.MSB是放在陣列的開始位置digits[0].

我的想法是，從陣列中依先讀出個位數加1後，判斷如果要進位，再取十位數...依此類推 後來我google有看到一個想當不錯的想法。

/**
 *  * Return an array of size *returnSize.
 *   * Note: The returned array must be malloced, assume caller calls free().
 *    */
int* plusOne(int* digits, int digitsSize, int* returnSize) {
    int sum=1;
    int i;
    int *array=NULL;

    if(!digits || digitsSize < 1) return NULL;

    *returnSize=digitsSize;

    for(i=(digitsSize-1); i >= 0 ; i--){
        /* caculate the result */
        sum+=digits[i];

        /* get the digital in ones */
        digits[i]=sum%10;

        /*get the degital in tens*/
        sum=sum/10;

        if(sum == 0)
            break;
    }

    if(sum){  
        *returnSize=(*returnSize)+1;
        array=(int *)malloc(((*returnSize)*sizeof(int)));
        array[0]=1;
        memcpy( &array[1],digits,sizeof(int)*digitsSize);

    }else{
        array=(int *)malloc(((*returnSize)*sizeof(int)));
        memcpy( &array[0],digits,sizeof(int)*digitsSize);

    }

    return array;
}

google看到的，https://www.oschina.net/code/snippet_2289056_55609 因為題目是+1，所以要進位的情況只有某個位數是9，所以如果那個位數是9，就把它設成0， 然後繼續處理下一個位數，不是9就把它+1後，跳開迴圈。 這解法也蠻有意思的，相當針對題目的要求!

int* plusOne(int* digits, int digitsSize, int* returnSize) {
    int i = (digitsSize) - 1; // start from back
    int* newDigits = NULL;
    // if input is 0 don't bother
    if(!digits || digitsSize < 1) return NULL;

    while( i>=0 )
    {
        if(digits[i] == 9)
        {
            digits[i] = 0;
            --i;
        }
        else
        {
            ++digits[i];
            --i;
            break;
        }
    }

    if(digits[0] == 0)
    {
        *returnSize = digitsSize +1;
        newDigits =(int*) malloc( sizeof(int)*(*returnSize));
        memcpy( newDigits+1,digits,sizeof(int)*digitsSize);
        newDigits[0]=1;
    }
    else
    {
        *returnSize = digitsSize ;
        newDigits = (int*)malloc( sizeof(int)*(*returnSize));
        memcpy( newDigits,digits,sizeof(int)*digitsSize);

    }
    return newDigits;

}