Сарлавҳаи варақаи Excel Ҳалли Leetcode


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Adobe Google
Матем Системаи рақамӣ

Изҳороти мушкилот

Дар ин масъала, адади бутуни мусбат дода мешавад, ки рақами сутуни варақи Excel-ро ифода мекунад, мо бояд унвони сутуни мувофиқи он дар варақи Excel баргардем.

Сарлавҳаи варақаи Excel Ҳалли Leetcode

мисол

#1

28
"AB"

#2

701
"ZY"

усул

Ин мушкил баръакси мушкилотест, ки мо бояд ба он маҷбур шавем рақами сутунро аз унвони сутун фаҳмед.
Ҳамин тавр, дар ин масъала мо рақами пойгоҳи 26-ро ба рақами base-10 табдил додем, ки он адади даҳӣ мебошад. Дар ин масъала мо бояд унвони сутунро аз рақами сутун ёбем. Пас, дар ин ҷо мо бояд танҳо баръакс амал кунем, яъне мо бояд рақами пойгоҳи 10 (даҳӣ) -ро ба як қатор системаи base-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 system '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 мусбат аст, давра иҷро кунед.
    • 1-ро аз n хориҷ кунед.
    • Бо иҷро кардани модули n то 26 аломати ҳозираро гиред.
    • N-ро ба 26 тақсим кунед.
  3. Акнун сатри натиҷаҳоро баргардонед, зеро мо аломатҳоро аз рост ба чап пайдо кардем.
  4. Сатрҳои баръаксро баргардонед.

татбиќи

Барномаи C ++ барои унвони сутуни варақаи Excel Ҳалли Leetcode

#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 Solutions Leetcode

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 Solution Leetcode

Мураккабии вақт

O (log (n)): Дар куҷо n рақами сутун дода шудааст. Мо дар ҳар як такрор шумораи онро ба 26 тақсим мекунем, аз ин рӯ мураккабии вақт O (log (n)) мешавад.

Мураккабии фазо 

О (1): Мо ягон фазои иловагиро ғайр аз нигоҳдории натиҷа истифода намебарем.