ภาพรวม
โจทย์บวก 1 ให้ตัวเลขที่แทนด้วยลิสต์ของหลัก (digits) เช่น [2,4,9] = 249 → [2,5,0]
ตัวอย่าง
อินพุต: [9, 9] (แทน 99)
99 + 1 = 100 → [1, 0, 0]
อัลกอริทึม (Grade School Addition)
- เพิ่ม 0 นำหน้า (guard digit) → [0, 9, 9]
- บวก 1 ให้หลักสุดท้าย → [0, 9, 10]
- Propagate carry จากหลังมาหน้า:
- i=2: 10 → carry=1, digit=0 → [0, 10, 0]
- i=1: 10 → carry=1, digit=0 → [1, 0, 0]
- ถ้าหลักแรกเป็น 0 ตัดทิ้ง
โค้ด Python
class Solution:
def solve(self, n):
n = [0] + n
n[-1] += 1
for i in range(len(n) - 1, 0, -1):
n[i-1] += n[i] // 10
n[i] = n[i] % 10
return n if n[0] > 0 else n[1:]
ob = Solution()
print(ob.solve([9, 9]))
วิธี Pythonic (แปลง int)
def plus_one(digits):
num = int("".join(map(str, digits))) + 1
return [int(d) for d in str(num)]
แต่ไม่เหมาะกับตัวเลขใหญ่มาก (เกิน precision)
ผลลัพธ์
[1, 0, 0]
