ຫົວຂໍ້ Excel ແຖວຖັນແຖວ Leetcode Solution


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Adobe ກູໂກ
ຄະນິດສາດ ລະບົບຈໍານວນ

ຖະແຫຼງການບັນຫາ

ໃນປັນຫານີ້, ມັນໄດ້ຖືກມອບໃຫ້ບວກກັບເຊິ່ງ ໝາຍ ເຖິງເລກຖັນຂອງເອກະສານ Excel, ພວກເຮົາຕ້ອງເອົາຫົວຂໍ້ຖັນທີ່ສອດຄ້ອງກັນດັ່ງທີ່ປາກົດຢູ່ໃນເອກະສານ Excel.

ຫົວຂໍ້ Excel ແຖວຖັນແຖວ Leetcode Solution

ຍົກຕົວຢ່າງ

#1

28
"AB"

#2

701
"ZY"

ວິທີການ

ບັນຫານີ້ແມ່ນການຖອຍຫລັງຂອງບັນຫາທີ່ພວກເຮົາຕ້ອງເຮັດ ຊອກຫາເລກຖັນຈາກຫົວຂໍ້ຖັນ.
ສະນັ້ນໃນປັນຫາດັ່ງກ່າວພວກເຮົາປ່ຽນເລກທີ 26-base ເປັນ base-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, ແຕ່ວ່າໃນລະບົບ ex 'A' ແມ່ນ ໜຶ່ງ ດຽວ. ທຸກໆ char ໄດ້ຮັບຂອງພິເສດ.

ສະນັ້ນເພື່ອໃຫ້ໄດ້ຮັບ char ຄັ້ງສຸດທ້າຍເຊັ່ນ: Z ພວກເຮົາຈະລົບ 1 ຕົວຢ່າງຄື n– ແລະຈາກນັ້ນໄດ້ຮັບ n% 26
(n-1)% 26 = Z
ຕອນນີ້ແບ່ງກັບ 26 ແລະເຮັດຊ້ ຳ ຂະບວນການດຽວກັນ ສຳ ລັບຕົວລະຄອນຕໍ່ໄປ.
(n-1) / 26 = (A + 1) * 26 ^ 1 + (B + 1) * 26 ^ 0

ລະບົບວິເຄາະ

  1. ສ້າງສະຕິງເປົ່າ ສຳ ລັບເກັບຮັກສາຕົວອັກສອນ.
  2. ດໍາເນີນການ loop ໃນຂະນະທີ່ n ແມ່ນບວກ.
    • ລົບ 1 ຈາກນ.
    • ຮັບຕົວລະຄອນປະຈຸບັນໂດຍການເຮັດ modulo ຂອງ n ໂດຍ 26.
    • ແບ່ງ n ໂດຍ 26.
  3. ດຽວນີ້ປ່ຽນສາຍເຊືອກຜົນໄດ້ຮັບເພາະວ່າພວກເຮົາໄດ້ພົບຕົວອັກສອນຈາກຂວາຫາຊ້າຍ.
  4. ສົ່ງຄືນເຊືອກທີ່ປີ້ນກັບກັນ.

ການປະຕິບັດ

C ++ Program ສຳ ລັບຫົວຂໍ້ Excel ຂອງຄໍ ລຳ ຫົວຂໍ້ 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 Program ສຳ ລັບຫົວຂໍ້ Excel ຂອງຄໍ ລຳ ຫົວຂໍ້ 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 Solution

ຄວາມສັບສົນເວລາ

O (log (n)): ບ່ອນທີ່ n ແມ່ນ ໝາຍ ເລກຖັນທີ່ໃຫ້. ພວກເຮົາ ກຳ ລັງແບ່ງ ຈຳ ນວນໂດຍ 26 ໃນແຕ່ລະ iteration, ເພາະສະນັ້ນຄວາມສັບສົນເວລາຈະເປັນ O (log (n)).

ຄວາມສັບສົນໃນອະວະກາດ 

O (1): ພວກເຮົາບໍ່ໄດ້ໃຊ້ພື້ນທີ່ພິເສດອື່ນນອກ ເໜືອ ຈາກການເກັບຮັກສາຜົນໄດ້ຮັບ.