Excel хуудасны баганын гарчиг Leetcode шийдэл


Хэцүү байдлын түвшин Easy
Байнга асуудаг Adobe Google-ийн
Математик Тоон систем

Асуудлын мэдэгдэл

Энэ асуудалд Excel хуудасны баганын дугаарыг илэрхийлсэн эерэг бүхэл тоо өгөгдсөн тул харгалзах баганын гарчгийг Excel хуудсанд харуулсан шиг буцааж өгөх хэрэгтэй.

Excel хуудасны баганын гарчиг Leetcode шийдэл

Жишээ нь

#1

28
"AB"

#2

701
"ZY"

арга барил

Энэ асуудал бол бидний хийх ёстой асуудлын эсрэг тал юм баганын гарчгаас баганын дугаарыг олж мэдэх.
Тиймээс уг асуудалд бид base-26 тоог аравтын бутархай болох basic-10 болгож хөрвүүлэв. Энэ асуудалд бид баганын дугаараас баганын гарчгийг олох ёстой. Тиймээс энд зөвхөн эсрэгээр нь хийх хэрэгтэй, өөрөөр хэлбэл суурь-10 (аравтын бутархай) тоог хэд хэдэн суурь-26 систем болгон хөрвүүлэх хэрэгтэй.

Ерөнхий тооллын системд base-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, өөрөөр хэлбэл Z-г авахын тулд эхлээд хасах 1, өөрөөр хэлбэл n-, дараа нь n% 26-г авах болно
(n-1)% 26 = Z
Одоо 26-тай хуваагаад дараагийн дүрд ижил үйлдлийг давт.
(n-1) / 26 = (A + 1) * 26 ^ 1 + (B + 1) * 26 ^ 0

Алгоритм

  1. Тэмдэгтүүдийг хадгалах хоосон мөр үүсгэх.
  2. N эерэг байхад цикл ажиллуулна уу.
    • N-ээс 1-ийг хас.
    • N-ийн 26-ийн модулийг хийж одоогийн шинж чанарыг авна.
    • N-ийг 26-д хуваана.
  3. Одоо бид баруунаас зүүн тийш тэмдэгт олсон тул үр дүнгийн мөрийг буцаана уу.
  4. Урвуу мөрийг буцаана.

Хэрэгжүүлэх

Excel хуудасны баганын гарчгийн нэрийн Leetcode шийдлийн C ++ програм

#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 хуудасны баганын гарчгийн Leetcode шийдлийн Java програм

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 (бүртгэл (n)): N бол өгөгдсөн баганын дугаар. Бид давталт бүрт тоог 26-д хувааж байгаа тул цаг хугацааны нарийн төвөгтэй байдал O (log (n)) болно.

Сансрын нарийн төвөгтэй байдал 

O (1): Бид үр дүнг хадгалахаас өөр нэмэлт зай ашиглахгүй байна.