Бүтін санды нөлдік бүтін сандардың қосындысына айналдыру Leetcode шешімі  


Күрделілік дәрежесі оңай
Жиі кіреді HRT
алгоритмдер кодтау сұхбат сұхбат дайындау LeetCode LeetCodeSolutions математика

Бүтін санды нөлге тең бүтін сандардың қосындысына айналдыру мәселесі Leetcode Solution бізден берілгенді бөлуді сұрады бүтін сан. Біз берілген бүтін санды екі санға бөлуіміз керек. Осы екі бүтін санға шектеу қойылған. Бұл екі бүтін сандарда 0 цифры болмауы керек. Жақсырақ түсіну үшін бірнеше мысал қарастырамыз.

Бүтін санды нөлдік бүтін сандардың қосындысына айналдыру Leetcode шешімітүйреуіш

n = 2
[1,1]

Түсініктеме: Шығармадағы екі бүтін сан 1 және 1. Бүтін сандар бірдей болуы мүмкін, бірақ оларда 0 цифры болмауы керек. Шығарылымда шектеулер орындалады. Екі бүтін санның қосындысы да кіріске тең. Осылайша шығыс дұрыс.

n = 1010
[11, 999]

Түсініктеме: Шығарылым дұрыс, өйткені екі бүтін санның қосындысы 1010-ға тең. Сонымен қатар оларда 0-ге тең цифрлар жоқ.

Бүтін санды нөлдік бүтін сандардың қосындысына айналдыру әдісі, Leetcode шешімі  

Мәселе берілген кірісті екі бүтін санға бөлуді сұрады. Орындалуы керек шарт жоғарыда сипатталған. Бірінші шарт - бүтін сандардың қосындысы берілген бүтін санға тең болуы керек. Шығарылым ретінде қайтарылатын екі бүтін санда 0 сан болмауы керек. Есепті шешу үшін біз 1-ден n-ге дейінгі бірінші бүтін санға цикл жүргіземіз. Екінші қатынасты бірінші қатынастан шығаруға болады. Содан кейін екі бүтін сан екінші шартты қанағаттандыратындығын тексереміз.

Сондай-ақ, қараңыз
Жолдарды тең парақ кодының шешіміне теңестіру үшін минималды своптар

Екінші шартты тексеру үшін біз бүтін санды кіріс ретінде қабылдайтын тапсырыс функциясын құрамыз. Ол берілген бүтін санның 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 коды, 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), біз ешқандай ақпарат сақтамаймыз. Ал бүкіл алгоритмде айнымалылардың тұрақты саны қолданылады. Осылайша кеңістіктің күрделілігі тұрақты болады.

2