Last Updated on 2023-08-22 by Clay
題目
Given an integer columnNumber, return its corresponding column title as it appears in an Excel sheet.
For example:A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ...
Example 1:
Input: columnNumber = 1 Output: "A"
Example 2:
Input: columnNumber = 28 Output: "AB"
Example 3:
Input: columnNumber = 701 Output: "ZY"
Constraints:
1 <= columnNumber <= 231 - 1
解題思路
由於我們要對應 Index 並在換號時新增新的字母，所以本質上可以將其理解成使用除以 26 之後的餘數來轉換成對應的英文字母。
但這題雖然是 Easy，我卻一直卡在一個盲點 —— 那就是除以 26 之後的最小值為 0，但是在題目給定的設定中，A 這個最初的字母 Index 卻是 1。
當然我們可以直接設定一個 mapping 的字典，但是我卻不願意多花記憶體做這件事。一直到後來恬不知恥地和 ChatGPT 討論時，它才提醒我說可以對於給定的 columnNumber 在每次計算餘數前減一，實現平移的對齊。
C++ 程式碼
class Solution {
public:
string convertToTitle(int columnNumber) {
// Init
string result;
int remainder = 0;
// Combine
while (columnNumber > 0) {
--columnNumber;
remainder = columnNumber % 26;
columnNumber = columnNumber / 26;
char currChar = 'A' + remainder;
result = currChar + result;
}
return result;
}
};Python 程式碼
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
mid = 0
while left <= right:
mid = left + ((right - left) >> 1);
if nums[mid] == target:
return mid
# If the left side is ordered
if nums[mid] >= nums[left]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
# If the right side is ordered
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1