描述#
非負整数を表す整数の非空配列が与えられた場合、その数に 1 を加えます。
最上位の数字は配列の先頭に格納され、配列の各要素は単一の数字のみを格納します。
整数 0 以外の場合、この整数は 0 で始まらないと仮定できます。
例 1:
入力: [1,2,3]
出力: [1,2,4]
説明: 入力配列は数字123を表します。
例 2:
入力: [4,3,2,1]
出力: [4,3,2,2]
説明: 入力配列は数字4321を表します。
思路#
- 配列の操作は、最後の要素が 9 である場合と 9 でない場合に分けられます。最後の要素が 9 でない場合、最後の要素に 1 を加えて出力するだけです。
- 最後の要素が 9 の場合、すべての要素が 9 であるかどうかと、すべての要素が 9 でないかどうかに分けられます。すべての要素が 9 の場合、配列のサイズを 1 つ増やし、最初の要素を 1 にし、他の要素をすべて 0 にします。
- すべての要素が 9 でない場合、配列を後ろから前に走査し、9 の場合は 0 に設定し、9 でない場合は 1 を加えて直接返します。
/**
* 注意：返される配列はmallocされたものでなければなりません。呼び出し元がfree()を呼び出すと仮定しています。
*/
int* plusOne(int* digits, int digitsSize, int* returnSize){
int* result;
// 最後の要素が9でない場合
if(digits[digitsSize - 1] != 9) {
result = (int*)malloc(sizeof(int)*digitsSize);
memcpy((void*)result,(void*)digits,sizeof(int)*digitsSize);
*returnSize = digitsSize;
result[digitsSize - 1] = digits[digitsSize - 1] + 1;
return result;
}
/* 最後の要素が9の場合 */
for(int i=digitsSize - 1;;i--) {
if(digits[i] != 9)
break;
if(i == 0) {
// すべての要素が9の場合
*returnSize = digitsSize + 1;
result = (int*)malloc(sizeof(int)*(*returnSize));
result[0] = 1;
for(int j=1;j<*returnSize;j++)
result[j] = 0;
return result;
}
}
// すべての要素が9でない場合
*returnSize = digitsSize;
result = (int*)malloc(sizeof(int)*(digitsSize));
int not_9_num = digitsSize - 1;
for(;not_9_num >= 0;not_9_num--) {
if(digits[not_9_num] != 9)
break;
result[not_9_num] = 0;
}
memcpy(result,digits,sizeof(int) * (not_9_num + 1));
result[not_9_num] = digits[not_9_num] + 1;
return result;
}