Mündəricat
Problem bəyanat
Excel Cədvəli Sütun Başlığı LeetCode Həlli – Bizə sütun nömrəsi verilir (gəlin onu colNum adlandıraq) və onun müvafiq sütun başlığını Excel cədvəlində göründüyü kimi qaytarmalıyıq.
Məsələn
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
Nümunələr
Misal 1:
Input: columnNumber = 1 Output: "A"
Misal 2:
Input: columnNumber = 28 Output: "AB"
Misal 3:
Input: columnNumber = 701 Output: "ZY"
Yanaşma
'A' hərfinin 1 dəyəri olduğunu düşünün, 'B'->2 ….. 'Z'->26
qeyd edin ki, yuxarıdakı qeydlərdə qiymətlər 1 əsaslıdır
burada Radiksimiz (R) == 26
XYZ = X * R^2 + Y * R + Z ədədinin son qiyməti
bu, baza-10 onluq ədədinə bənzəyir, lakin ən böyük fərq ondadır ki, hər rəqəmdəki rəqəmlər 1 əvəzinə 0 ilə başlayır və hər bir rəqəmdəki maksimum R-1 əvəzinə R (Radix) ilə başlayır.
məsələn
Z== Radiks
onda növbəti ədəd AA = R + 1 = Z+1-dir
ZZ = R * R + R
növbəti nömrə AAA = 1*R^2 + 1 * R + 1 = ZZ +1-dir
beləliklə, AAA notasiyasından tutmuş ardıcıllıq nömrəsinə (ondalıq) qədər asandır, lakin digər yol % və / işləmə üsuluna görə bir qədər çətin olur.
Yuxarıda verilmiş misaldan da müşahidə etdiyimiz kimi, 26-cı sütundan sonra cavab (sütunNumber-1)%26-a uyğun gələn hərflərin təkrar əlavə edilməsi ilə alınır. Onun düzgünlüyünü induksiya prinsipi ilə mübahisə edə bilərik. Alqoritmin necə işlədiyini başa düşmək üçün bir nümunə götürək verilmiş nömrə 28-dir.
Fərz edək ki, “res” cavab sətri boş olsun. Char sistemində A 0, excel-də isə 1 olduğundan, biz sütunNumber dəyərini azaldıb colNum%26 alacağıq.
İterasiyadan əvvəl: colNum (verilmiş) = 28
First Iteration colNum = colNum - 1 = 28- 1 = 27 t = 'A' + (27)%26 = 'A' + 1 = 'B' res = t + res = 'B' colNum /= 26 = 27/26 = 1
Second Iteration colNum = colNum - 1 = 1 - 1 = 0 t = 'A' + 0%26 = 'A' res = ‘A’ + 'B' = ‘AB’ colNum = colNum/26 = 1/26 = 0
İkinci iterasiyadan sonra colNum 0 olur və buna görə də dövrə dayanır və biz “res” kimi cavab alırıq.
Kodu
Excel Cədvəli Sütun Başlığı LeetCode üçün C++ Kodu
class Solution {
public:
string convertToTitle(int colNum) {
string res = "";
char t;
while(colNum) {
t = 'A' + (--colNum)%26;
res = t + res;
colNum /= 26;
}
return res;
}
};
Excel Cədvəli Sütun Başlığı LeetCode üçün Java Kodu
class Solution {
public String convertToTitle(int colNum) {
StringBuilder res = new StringBuilder();
while(colNum > 0){
int t = (--colNum)%26;
colNum /= 26;
res.append((char)(t+'A'));
}
return res.reverse().toString();
}
}
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(colNum))
- hər dəfə colNum 26-ya bölünür, buna görə də O(log(colNum))
- Kosmik Mürəkkəblik: O (1)
- Yox əlavə yer res və t-dən başqa tələb olunur, buna görə də O(1)
