Βάση 7 Λύση κώδικα Leetcode


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις Bloomberg Γκάρενα
μαθηματικά

Το πρόβλημα Base 7 Leetcode Solution, μας ζητά να μετατρέψουμε έναν αριθμό σε έναν βασικό αριθμό 7. Ο δεδομένος αριθμός μπορεί να είναι αρνητικός ή θετικός έως και 10 εκατομμύρια, και στις δύο κατευθύνσεις στη γραμμή αριθμών. Το πρόβλημα φαίνεται απλό και είναι μια απλή μετατροπή ενός δεκαδικού αριθμού σε διαφορετική βάση. Ακριβώς όπως η μετατροπή ενός αριθμού σε δυαδική μορφή. Αντί η βάση να είναι 2, η βάση είναι 7. Η τιμή επιστροφής θα πρέπει να είναι συμβολοσειρά. Ας ρίξουμε μια ματιά σε μερικά παραδείγματα.

Παράδειγμα

100
"202"

Επεξήγηση: Ο αριθμός 202 στη βάση 7 μετά τη μετατροπή αποδίδει 100 σε δεκαδική μορφή. 202 στη βάση 7 = 2 * (7 ^ 2) + 0 * (7 ^ 1) + 2 * (7 ^ 0) = 100 στη βάση 7.

Βάση 7 Λύση κώδικα Leetcode

-7
"-10"

Επεξήγηση: Ο δεδομένος αριθμός -7 μετά τη μετατροπή σε βάση 7 θα δώσει -10.

Προσέγγιση για τη Λύση Leetcode Base 7

Το πρόβλημα Base 7 Leetcode Solution, μας παρέχει έναν αριθμό ή ακέραιος αριθμός και μας ζητά να το μετατρέψουμε σε βάση 7. Η μετατροπή σε όχι μόνο βάση 7, είναι μια απλή λειτουργία. Συνεχίζουμε να διαιρούμε τον δεδομένο αριθμό με την απαιτούμενη βάση μας. Αφού διαιρέσετε τον αριθμό, το υπόλοιπο αποθηκεύεται. Στη συνέχεια, το αποτέλεσμα που βρέθηκε μετά τη διαίρεση του αριθμού αποστέλλεται ξανά για την επαναλαμβανόμενη διαίρεση. Συνεχίζουμε να αποθηκεύουμε το υπόλοιπο που είναι η απάντηση στην ερώτηση. Η επαναλαμβανόμενη διαδικασία διακόπτεται μόλις ο αριθμός γίνει μικρότερος από τη δεδομένη βάση.

Ας θεωρήσουμε λοιπόν το 100 ως την είσοδο. Πρώτον, διαιρούμε τον αριθμό με 7, το πηλίκο είναι 14 και το υπόλοιπο είναι 2. Στη συνέχεια, το υπόλοιπο αποθηκεύεται και το πηλίκο αποστέλλεται και πάλι για τη διαίρεση. Τώρα, το πηλίκο γίνεται 2 και το υπόλοιπο αποθηκεύεται. Μέχρι τώρα, ο αριθμός που μετατράπηκε γίνεται 20. Στη συνέχεια, το πηλίκο αποστέλλεται ξανά για διαίρεση αλλά επιστρέφεται επειδή είναι μικρότερο από τη δεδομένη βάση (7). Έτσι, το τελικό αποτέλεσμα είναι 202.

Κώδικας

Κωδικός C ++ για το Base 7 Leetcode Solution

#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

Κωδικός Java για Λύση Leetcode Base 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

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

O (M (n) log n), όπου n είναι το μήκος της δεδομένης εισόδου, M (n) είναι ο χρόνος που χρειάζεται για να διαιρέσετε δύο αριθμούς 2-bit. Έτσι, η χρονική πολυπλοκότητα είναι λογαριθμική.

Διαστημική πολυπλοκότητα

O (log n), ο χώρος που χρησιμοποιείται από τη στοίβα μεταγλωττιστή. Εδώ το n αντιπροσωπεύει το μήκος του αριθμού. Έτσι, η διαστημική πολυπλοκότητα είναι επίσης λογαριθμική.