LeetCode 7 Reverse Integer: กลับหลักพร้อมหยุดก่อนล้น 32-bit

โจทย์ Reverse Integer ให้กลับลำดับหลักของจำนวนเต็ม signed 32-bit และคืนศูนย์เมื่อผลลัพธ์อยู่นอกช่วงที่กำหนด ศูนย์นำหน้าหลังกลับจะหายตามค่าจำนวนเต็มครับ

สรุปโจทย์ด้วยคำของเรา

เก็บเครื่องหมายไว้ กลับเฉพาะหลักของค่าสัมบูรณ์ แล้วนำเครื่องหมายกลับมา จุดที่โจทย์วัดจริงคือ overflow: ภาษาอย่าง Python เก็บ integer ใหญ่ได้ จึงต้องตรวจขอบ 32-bit เอง ไม่ใช่ปล่อยให้ runtime บอก

วิธีที่ 1: แปลงเป็นข้อความ

แปลงค่าสัมบูรณ์เป็น string, reverse ด้วย slicing, parse กลับ และตรวจช่วง

• เวลา O(d) เมื่อ d คือจำนวนหลัก
• หน่วยความจำ O(d)
• อ่านง่าย เหมาะกับ production utility หากโจทย์ไม่ห้าม string

วิธีที่ 2: pop หลักท้ายแล้ว push เข้าผลลัพธ์

ใช้ digit = value % 10, ลดค่าด้วย integer division และสร้าง reversed = reversed * 10 + digit วิธีนี้แสดงกลไกเลขฐานสิบตรง ๆ

• เวลา O(d)
• หน่วยความจำ O(1)
• ในภาษาที่ integer ล้นได้ ต้องตรวจ ก่อน คูณและบวก; ใน Python ตัวอย่างตรวจผลทุกก้าวเพื่อจำลอง boundary เดียวกัน

วิธีที่ 3: เก็บหลักใน stack แล้วประกอบใหม่

แยกหลักทั้งหมดใส่ list ก่อนแล้ววนประกอบ เป็นภาพชัดแต่ใช้ O(d) memory โดยไม่ได้อ่านง่ายกว่า string มากนัก เหมาะเฉพาะเมื่อต้อง transform หลักระหว่างทาง

import unittest


LOWER = -(2**31)
UPPER = 2**31 - 1


def reverse_string(value):
    sign = -1 if value < 0 else 1
    answer = sign * int(str(abs(value))[::-1])
    return answer if LOWER <= answer <= UPPER else 0


def reverse_arithmetic(value):
    sign = -1 if value < 0 else 1
    remaining = abs(value)
    answer = 0
    while remaining:
        remaining, digit = divmod(remaining, 10)
        answer = answer * 10 + digit
        signed = sign * answer
        if signed < LOWER or signed > UPPER:
            return 0
    return sign * answer


class ReverseTests(unittest.TestCase):
    def check(self, value, expected):
        self.assertEqual(reverse_string(value), expected)
        self.assertEqual(reverse_arithmetic(value), expected)

    def test_sign_zero_and_trailing_zero(self):
        self.check(123, 321)
        self.check(-120, -21)
        self.check(0, 0)

    def test_overflow(self):
        self.check(1534236469, 0)
        self.check(-2147483648, 0)


if __name__ == "__main__":
    unittest.main()

Decision table

สถานการณ์	String	Arithmetic	Stack
input ใหญ่ในกรอบโจทย์	O(d)	O(d)	O(d)
memory จำกัด	ใช้เพิ่มตามหลัก	ดีที่สุด	ใช้เพิ่มตามหลัก
readability	ดีที่สุด	ต้องระวัง sign/overflow	ปานกลาง
streaming digits	ต้องรวมข้อความ	ประกอบได้ทีละหลักตามทิศที่รับ	เหมาะเมื่อรับย้อนลำดับ
ห้ามแก้ input	ผ่าน	ผ่าน	ผ่าน
ภาษาที่ไม่มี big integer	ต้อง parse อย่างระวัง	guard ก่อนคูณ	guard ตอนประกอบ

Best default: arithmetic pop-push สำหรับโจทย์สัมภาษณ์ เพราะใช้พื้นที่คงที่และทำให้เห็น overflow contract; งานทั่วไปที่อนุญาต string เลือกวิธีที่ทีมอ่านง่ายกว่า

Edge cases

• ศูนย์และตัวเลขที่ลงท้ายด้วยศูนย์หลายตัว
• ค่าติดลบ โดยเฉพาะค่าต่ำสุดที่ค่าสัมบูรณ์อาจล้นในบางภาษา
• ผลกลับเท่ากับขอบพอดี เทียบด้วย <=
• Python ไม่ล้นเอง จึงต้องใส่ boundary ตามโจทย์

Recap

• แยกเครื่องหมายจากหลักก่อน
• ศูนย์นำหน้าหลังกลับหายตาม integer semantics
• ตรวจช่วง signed 32-bit ทุกคำตอบ
• เลือก arithmetic เมื่อ memory คงที่เป็นเงื่อนไขหลัก