Преобразуване на цяло число в сумата от две нулеви целочислени решения с Leetcode


Ниво на трудност Лесно
Често задавани в ХЗТ
Математически

Проблемът Convert Integer to Sum of Two No-Zero Integers Leetcode Solution помоли ни да разделим даденото цяло число. Трябва да разделим даденото цяло число на две числа. Има ограничение, наложено на тези две цели числа. Тези две цели числа не трябва да съдържат цифрата 0. За по-добро разбиране ще разгледаме няколко примера.

Преобразуване на цяло число в сумата от две нулеви целочислени решения с Leetcode

n = 2
[1,1]

Обяснение: Двете цели числа в изхода са 1 и 1. Целите числа могат да бъдат еднакви, но не трябва да имат цифра 0. Ограничението е изпълнено в изхода. Сумата от двете цели числа също е равна на входа. По този начин изходът е правилен.

n = 1010
[11, 999]

Обяснение: Изходът е правилен, защото сумата от двете цели числа е равна на 1010. И те също нямат цифра, равна на 0.

Подход за преобразуване на цяло число в сумата от две без нулеви числа Leetcode решение

Проблемът ни помоли да разделим дадения вход на две цели числа. Условието, което трябва да бъде изпълнено, вече е посочено в описанието по-горе. Първото условие е сумата от целите числа да бъде равна на даденото цяло число. Двете цели числа, които ще бъдат върнати като изход, не трябва да съдържат 0 цифри. За да разрешим проблема, изпълняваме цикъл върху първото цяло число, което варира от 1 до n. Второто цяло число може да се изведе от първото отношение. След това проверяваме дали и двете цели числа отговарят на второто условие.

За проверка на второто условие създаваме персонализирана функция, която приема цяло число като вход. Той връща true или false в зависимост от това дали даденото цяло число съдържа 0 или не. За да проверим дали просто продължаваме да премахваме цифри една по една от края.

код

C ++ код за преобразуване на цяло число в сумата от две без нулеви числа Leetcode решение

#include <bits/stdc++.h>
using namespace std;

bool check(int n){
    while(n>0){
        if(n%10 == 0)
            return false;
        n/=10;
    }
    return true;
}

vector<int> getNoZeroIntegers(int n) {
    for(int i=1;i<n;i++){
        if(check(i) && check(n-i))
            return {i, n-i};
    }
    return {-1,-1};
}

int main(){
    int input = 1010;
    vector<int> output = getNoZeroIntegers(input);
    cout<<output[0]<<" "<<output[1];
}
11 999

Java код за преобразуване на Integer в сумата от две без нулеви Integers Leetcode разтвор

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  private static boolean check(int n){
        while(n>0){
            if(n%10 == 0)return false;
            n/=10;
        }
        return true;
    }
    
    public static int[] getNoZeroIntegers(int n) {
        for(int i=1;i<n;i++){
            if(check(i) && check(n-i))
                return new int[]{i, n-i};
        }
        return new int[]{-1,-1};
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    int input = 1010;
      int[] output = getNoZeroIntegers(input);
      System.out.print(output[0]+" "+output[1]);
  }
}
11 999

Анализ на сложността

Сложност във времето

O (NlogN), където N е цялото число, дадено като вход. Дневникът има база 10, защото нашата функция, която проверява дали цялото число съдържа 0 или не, работи в logN време.

Сложност на пространството

O (1), ние не съхраняваме никаква информация. И целият алгоритъм използва постоянен брой променливи. По този начин сложността на пространството е постоянна.