Excel Sheet ชื่อคอลัมน์ Leetcode โซลูชัน  


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อะโดบี Google
อัลกอริทึม การเข้ารหัส สัมภาษณ์ สัมภาษณ์เตรียม LeetCode LeetCodeSolutions คณิตศาสตร์ ระบบตัวเลข

คำชี้แจงปัญหา  

ในปัญหานี้จะมีการกำหนดจำนวนเต็มบวกซึ่งแสดงถึงหมายเลขคอลัมน์ของแผ่นงาน Excel เราต้องส่งคืนชื่อคอลัมน์ที่เกี่ยวข้องตามที่ปรากฏในแผ่นงาน Excel

Excel Sheet ชื่อคอลัมน์ Leetcode โซลูชัน

ตัวอย่าง

#1

28
"AB"

#2

701
"ZY"

เข้าใกล้  

ปัญหานี้เป็นการย้อนกลับของปัญหาที่เราต้องทำ ค้นหาหมายเลขคอลัมน์จากชื่อคอลัมน์
ดังนั้นในปัญหานั้นเราจึงแปลงเลขฐาน 26 เป็นเลขฐาน 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)? เนื่องจากในระบบถ่าน 'A' เป็น 0 แต่ในระบบ excel 'A' เป็นระบบเดียว ทุกถ่านจะได้รับหนึ่งพิเศษ

ดังนั้นเพื่อให้ได้ถ่านสุดท้ายคือ Z เราจะลบ 1 เช่น n - แล้วจึงได้ n% 26
(n-1)% 26 = Z
ตอนนี้หารด้วย 26 และทำซ้ำขั้นตอนเดียวกันสำหรับอักขระถัดไป
(n-1) / 26 = (A + 1) * 26 ^ 1 + (B + 1) * 26 ^ 0

ดูสิ่งนี้ด้วย
เกมหิน LeetCode

ขั้นตอนวิธี

  1. สร้างสตริงว่างสำหรับจัดเก็บอักขระ
  2. เรียกใช้ลูปในขณะที่ n เป็นค่าบวก
    • ลบ 1 จาก n
    • รับอักขระปัจจุบันโดยทำโมดูโลของ n คูณ 26
    • หาร n ด้วย 26
  3. ตอนนี้ย้อนกลับสตริงผลลัพธ์เนื่องจากเราพบอักขระจากขวาไปซ้าย
  4. ส่งคืนสตริงที่กลับด้าน

การดำเนินงาน  

โปรแกรม C ++ สำหรับ Excel Sheet Title 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 สำหรับ Excel Sheet Title 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 Sheet Title Leetcode Solution  

ความซับซ้อนของเวลา

O (บันทึก (n)): โดยที่ n คือหมายเลขคอลัมน์ที่กำหนด เรากำลังหารจำนวนด้วย 26 ในการวนซ้ำแต่ละครั้งดังนั้นความซับซ้อนของเวลาจะเป็น O (log (n))

ความซับซ้อนของอวกาศ 

O (1): เราไม่ได้ใช้พื้นที่เพิ่มเติมใด ๆ นอกเหนือจากการจัดเก็บผลลัพธ์