Excel Cədvəl Sütun Başlığı Leetcode Həlli

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic google
alqoritmlər kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions Riyaziyyat Sayı SistemiBaxılıb 37

Problem bəyanat

Bu problemdə bir Excel vərəqinin sütun nömrəsini əks etdirən bir müsbət tam ədədi verilir, uyğun bir sütun başlığını bir Excel vərəqində göründüyü kimi qaytarmalıyıq.

Excel Cədvəl Sütun Başlığı Leetcode Həlli

misal

#1

28
"AB"

#2

701
"ZY"

Yanaşma

Bu problem, etməli olduğumuz problemin tərsidir bir sütun başlığından sütun nömrəsini tapın.
Beləliklə, bu problemdə bir baza-26 rəqəmini onlu bir ədədi olan baza-10 sayına çevirdik. Bu problemdə sütun nömrəsindən sütun başlığını tapmaq məcburiyyətindəyik. Beləliklə, burada yalnız əksini etməliyik, yəni baza-10 (onluq) ədədi bir sıra baza-26 sisteminə çevirməliyik.

Ümumi say sistemində baza-26-nın 26-dan 0-ə qədər dəyərləri təmsil edən 25 simvoldan ibarət olduğunu düşünürük. Ancaq Excel vərəqəsi sütun başlığında bu bir qədər fərqlidir. 1-dən 26-dək dəyərləri təmsil edir. Beləliklə, AZ simvollarını 0-25 kimi istifadə etsək, aşağıdakı tənlik kimi görünür:

Sətir ABZ olsun, bu n rəqəminə uyğundur:
n = (A + 1) * 26 ^ 2 + (B + 1) * 26 ^ 1 + (Z + 1) * 26 ^ 0

Niyə (A + 1)? Çünki char sistemində 'A' 0, excel sistemində 'A' birdir. Hər char əlavə edir.

Beləliklə, son char yəni Z-i əldə etmək üçün əvvəlcə mənfi 1 yəni n - və sonra n% 26 əldə edəcəyik
(n-1)% 26 = Z
İndi 26 ilə bölün və növbəti simvol üçün eyni prosesi təkrarlayın.
(n-1) / 26 = (A + 1) * 26 ^ 1 + (B + 1) * 26 ^ 0

Alqoritm

  1. Simvolların saxlanması üçün boş bir simli yaradın.
  2. N müsbət olarkən bir döngə işlədin.
    • N-dən 1-i çıxarın.
    • N-dən 26-ya qədər modul edərək cari xarakter əldə edin.
    • N-i 26-ya bölün.
  3. İndi sağdan sola simvol tapdığımız üçün nəticə sətrini tərs çevirin.
  4. Tərs sətri qaytarın.

Həyata keçirilməsi

Excel Cədvəl Sütun Başlığı Leetcode Həlli üçün C ++ Proqramı

#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

Excel Vərəq Sütun Başlığı Leetcode Həlli üçün Java Proqramı

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 Vərəq Sütun Başlığı Leetcode Həlli üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (log (n)): Harada n verilən sütun nömrəsidir. Hər təkrarlamada ədədi 26-ya bölürük, bu səbəbdən zaman mürəkkəbliyi O (log (n)) olacaqdır.

Kosmik Mürəkkəblik 

O (1): Nəticəni saxlamaq üçün başqa yerdən istifadə etmirik.

Şərh yaz

Translate »
1