ที่นี่เราจะดูวิธีตรวจสอบว่าตัวเลข n เป็น Happy Number หรือไม่ Happy Number คือตัวเลขที่เริ่มจากจำนวนเต็มบวกใดๆ แล้วแทนที่ตัวเลขด้วยผลรวมของกำลังสองของหลักตัวเลข กระบวนการนี้จะทำซ้ำจนกลายเป็น 1 มิฉะนั้นจะวนรอบไม่สิ้นสุดในวงจร ตัวเลขที่เจอ 1 จะเป็น Happy Number
สมมติตัวเลขคือ 19 ผลลัพธ์จะเป็น true เนื่องจากเป็น Happy Number เราสามารถเห็นได้จาก 19 ว่าจะได้:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
วิธีการแก้ปัญหา
- เราจะใช้แนวคิด Dynamic Programming และแก้ปัญหาแบบเรียกซ้ำ (recursion)
- Base case คือ เมื่อ n = 1 ให้คืนค่า true
- เมื่อ n ถูกเยี่ยมชมแล้ว ให้คืนค่า false
- ทำเครื่องหมาย n ว่าเยี่ยมชมแล้ว
- n := n เป็นสตริง, l := รายการหลักตัวเลขทั้งหมดใน n
- temp := ผลรวมกำลังสองของหลักตัวเลขทั้งหมด
- คืนค่าฟังก์ชันแบบเรียกซ้ำด้วยพารามิเตอร์ temp และรายการที่เยี่ยมชมแล้ว
ตัวอย่างโค้ด
class Solution(object):
def isHappy(self, n):
"""
:type n: int
:rtype: bool
"""
return self.solve(n, {})
def solve(self, n, visited):
if n == 1:
return True
if n in visited:
return False
visited[n] = 1
n = str(n)
l = list(n)
l = list(map(int, l))
temp = 0
for i in l:
temp += (i ** 2)
return self.solve(temp, visited)
ob1 = Solution()
op = ob1.isHappy(19)
print("Is Happy:", op)
อินพุต
19
เอาต์พุต
Is Happy: True
