Λύση Leetcode Τίτλος στήλης φύλλου Excel


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

Δήλωση προβλήματος

Σε αυτό το πρόβλημα δίνεται ένας θετικός ακέραιος που αντιπροσωπεύει έναν αριθμό στήλης ενός φύλλου Excel, πρέπει να επιστρέψουμε τον αντίστοιχο τίτλο στήλης όπως εμφανίζεται σε ένα φύλλο Excel.

Λύση Leetcode Τίτλος στήλης φύλλου Excel

Παράδειγμα

#1

28
"AB"

#2

701
"ZY"

Προσέγγιση

Αυτό το πρόβλημα είναι το αντίστροφο του προβλήματος στο οποίο πρέπει να αντιμετωπίσουμε μάθετε τον αριθμό στήλης από έναν τίτλο στήλης.
Έτσι, σε αυτό το πρόβλημα μετατρέψαμε έναν αριθμό βάσης-26 σε αριθμό βάσης-10 που είναι δεκαδικός αριθμός. Σε αυτό το πρόβλημα πρέπει να μάθουμε τον τίτλο της στήλης από τον αριθμό της στήλης. Εδώ λοιπόν απλώς πρέπει να κάνουμε το αντίθετο, δηλαδή πρέπει να μετατρέψουμε έναν βασικό-10 (δεκαδικό) αριθμό σε έναν αριθμό βασικού-26 συστήματος.

Γνωρίζουμε γενικά ότι το σύστημα αριθμών υποθέτω ότι η βάση-26 πρέπει να έχει 26 χαρακτήρες που αντιπροσωπεύουν τις τιμές 0 έως 25. Αλλά στον τίτλο της στήλης φύλλου του Excel αυτό είναι λίγο διαφορετικό. Αντιπροσωπεύει τιμές από το 1 έως το 26. Επομένως, αν χρησιμοποιήσουμε τους χαρακτήρες AZ ως 0-25, τότε θα μοιάζει με την παρακάτω εξίσωση:

Αφήστε τη συμβολοσειρά να είναι ABZ, αυτό αντιστοιχεί στον αριθμό n:
n = (A + 1) * 26 ^ 2 + (B + 1) * 26 ^ 1 + (Z + 1) * 26 ^ 0

Γιατί (A + 1); Επειδή στο σύστημα char το "A" είναι 0, αλλά στο σύστημα excel το "A" είναι ένα. Κάθε char παίρνει ένα επιπλέον.

Έτσι, για να πάρουμε τον τελευταίο char, δηλαδή Z, πρώτα θα μείον 1, δηλαδή n– και μετά θα πάρουμε n% 26
(n-1)% 26 = Ζ
Τώρα διαιρέστε με 26 και επαναλάβετε την ίδια διαδικασία για τον επόμενο χαρακτήρα.
(n-1) / 26 = (A + 1) * 26 ^ 1 + (B + 1) * 26 ^ 0

Αλγόριθμος

  1. Δημιουργήστε μια κενή συμβολοσειρά για την αποθήκευση των χαρακτήρων.
  2. Εκτελέστε έναν βρόχο ενώ το n είναι θετικό.
    • Αφαιρέστε το 1 από το n.
    • Αποκτήστε τον τρέχοντα χαρακτήρα κάνοντας modulo του n έως 26.
    • Διαίρεση n με 26.
  3. Τώρα αντιστρέψτε τη συμβολοσειρά αποτελεσμάτων επειδή έχουμε βρει χαρακτήρες από δεξιά προς τα αριστερά.
  4. Επιστρέψτε την αντίστροφη συμβολοσειρά.

Εκτέλεση

Πρόγραμμα C ++ for Excel Sheet Column Title Leetcode Solution

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

string convertToTitle(int n) 
{        
    string ans;
    while(n>0)
    {
        --n;
        int d= n%26;
        n/=26;
        ans+= 'A'+d;            
    }
   reverse(ans.begin(),ans.end());
   return ans; 
}

int main() 
{
   cout<<convertToTitle(28) <<endl;
   return 0; 
}
AB

Πρόγραμμα Java για το Excel Sheet Column Title Leetcode Solution

class Rextester{
    
    public static String convertToTitle(int n) 
    {
        StringBuilder ans= new StringBuilder();
        while(n>0)
        {
            --n;
            int d= n%26;
            n/=26;
            ans.append((char)('A'+d));            
        }
        ans.reverse();
        return ans.toString(); 
    }
    
    public static void main(String args[])
    {    	
       System.out.println( convertToTitle(28)  ) ;
    }
}
AB

Ανάλυση πολυπλοκότητας για τίτλο στήλης φύλλου Excel Λύση κωδικού Leetcode

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

O (log (n)): Όπου n είναι ο δεδομένος αριθμός στήλης. Διαιρούμε τον αριθμό με 26 σε κάθε επανάληψη, επομένως η πολυπλοκότητα του χρόνου θα είναι O (log (n)).

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

O (1): Δεν χρησιμοποιούμε επιπλέον χώρο εκτός από την αποθήκευση του αποτελέσματος.