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.

66. Прибавить один

Задано неотрицательное число, представленное в виде массива цифр. Прибавьте к нему единицу.

Цифры в массиве расположены так, что наиболее значимая цифра находится в голове массива.

// C++

class Solution {

public:

vector<int> plusOne(vector<int>& digits) {

}

};

// Java

public class Solution {

public int[] plusOne(int[] digits) {

}

}

РЕШЕНИЕ

последовательности

Анализ алгоритма

Следует промоделировать прибавление единицы к цифрам числа.

Реализация алгоритма

class Solution

{

public:

vector<int> plusOne(vector<int>& digits)

{

int n = digits.size();

reverse(digits.begin(), digits.end());

int add = 1;

for (int i = 0; i < n; i++)

{

int v = digits[i] + add;

digits[i] = v % 10;

add = v / 10;

}

if (add == 1) digits.push_back(1);

reverse(digits.begin(), digits.end());

return digits;

}

};

Java реализация

public class Solution

{

public int[] plusOne(int[] digits)

{

int i = digits.length-1;

while(i >= 0)

{

if(digits[i] < 9)

{

digits[i] = digits[i] + 1;

return digits;

}

else

{

digits[i] = 0;

i--;

}

}

int Newdigits[] = new int[digits.length+1]; // all elements are 0

Newdigits[0] = 1;

return Newdigits;

}

}

Java реализация – второе решение

import java.util.*;

class Solution

{

public int[] plusOne(int[] digits)

{

int i = digits.length-1;

while(i >= 0 && digits[i] == 9)

{

digits[i] = 0; i--;

}

if (i >= 0)

{

digits[i] += 1;

return digits;

}

int Newdigits[] = new int[digits.length+1]; // all elements are 0

Newdigits[0] = 1;

return Newdigits;

}

}

public class Main

{

public static void main(String []args)

{

Solution s = new Solution();

int nums[] = {9,9,9,9};

int res[] = s.plusOne(nums);

for(int i = 0; i < res.length; i++)

System.out.print(res[i]);

System.out.println();

}

}