Re: [閒聊] 每日leetcode
看板Marginalman作者JerryChungYC (JerryChung)時間1年前 (2024/09/18 12:51)推噓1(1推 0噓 2→)留言3則, 2人參與討論串874/1548 (看更多)
https://leetcode.com/problems/largest-number
179. Largest Number
給一個非負整數列表 nums
將它排成最大的數字並回傳它
因為數字可能很大 所以是回傳字串而不是整數
Example 1:
Input: nums = [10,2]
Output: "210"
Example 2:
Input: nums = [3,30,34,5,9]
Output: "9534330"
Constraints:
* 1 <= nums.length <= 100
* 0 <= nums[i] <= 10^9
思路：
因為要數字開頭越大越前面
原本想法很簡單 根據每個數反轉後排序
nums.sort(reverse=True, key=lambda x: str(x)[::-1])
結果馬上就錯了(
後來想說改為靠左對齊並在右邊補0
nums.sort(reverse=True, key=lambda x: str(x).ljust(len_max, '0')
過了一些但還是錯了
再研究發現並不是補0 而是要補兩數間長度差的前n位數 才會知道大小
如 8308 跟 830 差1 會比較肯定是至少1個數相同
只補1個數的話兩邊都是 8308 看不出來 要補2個數變成
8308_8 跟 830_83 所以知道 8308 放前面
最後想說乾脆逐個比對 超越不了再insert
Python Code:
class Solution:
def largestNumber(self, nums: List[int]) -> str:
if len(nums) == 1: return str(nums[0])
ans = [str(nums[0])]
for num in nums[1:]:
n = len(ans)
while n:
if f'{num}{ans[n-1]}' <= f'{ans[n-1]}{num}':
ans.insert(n, str(num))
break
n -= 1
else: # 檢查到第0個都是比較大的話 就插到最前面
ans.insert(0, str(num))
return str(int(''.join(ans))) # 有 [0,0] 這種東西 ((
想了一個早上 比預期中難 不早早早了
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.251.52.67 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1726635110.A.297.html
※ 編輯: JerryChungYC (60.251.52.67 臺灣), 09/18/2024 12:54:53
推
09/18 12:54,
1年前
, 1F
09/18 12:54, 1F
→
09/18 12:55,
1年前
, 2F
09/18 12:55, 2F
→
09/18 12:55,
1年前
, 3F
09/18 12:55, 3F
討論串 (同標題文章)
完整討論串 (本文為第 874 之 1548 篇)：