Основно решење Леетцоде


Ниво тешкоће Лако
Често питани у Блоомберг гарена
Математика

Проблем Басе 7 Леетцоде Солутион тражи да конвертујемо број у басе 7 број. Дати број може бити негативан или позитиван до 10 милиона, у оба смера на бројевној линији. Чини се да је проблем једноставан и састоји се у једноставној конверзији децималног броја у другу базу. Баш као и конверзија броја у бинарни формат. Уместо основе 2, основа је 7. Повратна вредност треба да буде низ. Погледајмо неколико примера.

Пример

100
"202"

Објашњење: Број 202 у бази 7 након конверзије даје 100 у децималном формату. 202 у основи 7 = 2 * (7 ^ 2) + 0 * (7 ^ 1) + 2 * (7 ^ 0) = 100 у бази 7.

Основно решење Леетцоде

-7
"-10"

Објашњење: Дати број -7 након претварања у базу 7 даће -10.

Приступ за решење 7 Леетцоде решења

Проблем Басе 7 Леетцоде Солутион, пружа нам број или цео број и тражи од нас да га претворимо у базу 7. Конверзија у не само базу 7 је једноставна операција. Настављамо да делимо дати број са потребном базом. Након поделе броја, остатак се чува. Тада се резултат пронађен после поделе броја поново шаље на понављање. Настављамо да складиштимо остатак који је одговор на питање. Понављајући поступак се зауставља када број постане мањи од дате основе.

Дакле, узмимо у обзир 100 као улаз. Прво делимо број са 7, количник је 14, а остатак 2. Затим се остатак чува и количник се поново шаље на дељење. Сада количник постаје 2, а остатак се чува. До сада претворени број постаје 20. Тада се количник поново шаље на дељење, али се враћа јер је мањи од дате основе (7). Тако коначни резултат износи 202.

код

Ц ++ код за Басе 7 Леетцоде Солутион

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

string convertToBase7(int num) {
    if(num < 0)return "-" + convertToBase7(-num);
    else if(num < 7) return to_string(num);
    else
        return convertToBase7(num/7) + convertToBase7(num%7);
}

int main(){
    cout<<convertToBase7(100);
}
202

Јава код за решење 7 Леетцоде решења

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

class Solution {
    public static String convertToBase7(int num) {
        if(num < 0)return "-" + convertToBase7(-num);
        else if(num < 7) return Integer.toString(num);
        else
            return convertToBase7(num/7) + convertToBase7(num%7);
    }
    
    public static void main(String[] args){
    	System.out.print(convertToBase7(100));
    }
}
202

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

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

О (М (н) лог н), где је н дужина датог улаза, М (н) је време потребно за поделу два 2-битна броја. Дакле, временска сложеност је логаритамска.

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

О (лог н), простор који користи стек компајлера. Овде н представља дужину броја. Дакле, сложеност свемира је такође логаритамска.