Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the force button algorithm continued to punch the card 19 days 🎈!
🚀 Algorithm 🚀

🌲 Example of original problem

Given a non-negative integer represented by a non-empty array of integers, add one to that number.

The highest digit is stored at the beginning of an array, where each element stores only a single digit.

You can assume that this integer does not start with zero, except for the integer 0.

The sample1: input: digits = [1.2.3] output: [1.2.4An input array represents a number123.Copy the code
The sample2: input: digits = [4.3.2.1] output: [4.3.2.2An input array represents a number4321.Copy the code
The sample3: input: digits = [0] output: [1]
Copy the code

Tip:

  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9

🌻C# method 1: traverse

Thinking analytical

The last digit of the array is +1

This plus one goes into two cases

  • The last digit is +1 except for 9
  • The last digit is the number 9

If the last digit is 9, then carry!

When 9 is incremented by one, it becomes zero, and then the preceding digit is incremented by one, and the loop is checked until no carry is performed, and the loop returns the result

There is a special case is 99, 999, 9999, etc., this time to the highest cycle is still need to carry, it is necessary to add a judgment, manual to it into a

Go straight to the code!

Code:

public class Solution {
    public int[] PlusOne(int[] digits) {

        int len = digits.Length;
        for(int i = len - 1; i >= 0; i--) {
            digits[i]++;
            digits[i] %= 10;
            if(digits[i]! =0)
                return digits;
        }
        digits = new int[len + 1];
        digits[0] = 1;
        returndigits; }}Copy the code

The execution result

By execution time:216Ms, in all CDefeated 94.37% of users in # submitMemory consumption:30MB, in all CBeat 61.16% of users in # commit
Copy the code

Complexity analysis

Time: O(n) Space: O(1)
Copy the code

🌻Java Method 1: Traversal

Thinking analytical

The last digit of the array is +1

This plus one goes into two cases

  • The last digit is +1 except for 9
  • The last digit is the number 9

If the last digit is 9, then carry!

When 9 is incremented by one, it becomes zero, and then the preceding digit is incremented by one, and the loop is checked until no carry is performed, and the loop returns the result

There is a special case is 99, 999, 9999, etc., this time to the highest cycle is still need to carry, it is necessary to add a judgment, manual to it into a

The following two kinds of code slightly different, the same idea, can refer to

A code:

class Solution {
// Traverses from back to front, if not 9: add one directly, if 9 resets the current element to 0
public int[] plusOne(int[] digits) {
    for (int i = digits.length - 1; i >= 0; i--) {
        // If equal to 9, reset to 0
        if (digits[i] == 9){
            digits[i] = 0;
        } else {
        // Instead of 9, add one to return
            digits[i] ++;
            returndigits; }}If there is no return, all the bits have been reset to 0
    // If all bits are carried, the length is +1
    digits = new int[digits.length + 1];
    digits[0] = 1;
    returndigits; }}Copy the code

Code 2:

class Solution {
    public int[] plusOne(int[] digits) {
        int len = digits.length;
        for(int i = len - 1; i >= 0; i--) {
            digits[i]++;
            digits[i] %= 10;
            if(digits[i]! =0)
                return digits;
        }
        digits = new int[len + 1];
        digits[0] = 1;
        returndigits; }}Copy the code

The execution result

By execution time:0Ms, beat out all Java commits100% user memory consumption:36.8MB, beat out all Java commits63.66% of the userCopy the code

Complexity analysis

Time: O(n) Space: O(1)
Copy the code

💬 summary

  • Today is the nineteenth day of the buckle algorithm clocking!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!