Leetcode: 397. การแทนที่จำนวนเต็ม

Leetcode 397 Integer Replacement



ระบุจำนวนเต็มบวก n คุณสามารถทำสิ่งต่อไปนี้:

ถ้า n ถ้าเท่ากันให้ใช้ n / 2 แทนที่ n
2. ถ้า n เป็นเลขคี่คุณสามารถใช้ n + 1 หรือ n - 1 แทนที่ n
n จำนวนการเปลี่ยนขั้นต่ำที่ต้องมีเพื่อให้กลายเป็น 1 คืออะไร?



ตัวอย่างที่ 1:



 Enter:  8  Output:  3  Explanation:  8 -> 4 -> 2 -> 1 

ตัวอย่างที่ 2:



 Enter:  7  Output:  4  Explanation:  7 -> 8 -> 4 -> 2 -> 1 Or 7 -> 6 -> 3 -> 2 -> 1

แนวคิดในการแก้ปัญหา:

การวางแผนแบบไดนามิกการเรียกซ้ำ ให้ dp [n] เป็นจำนวนครั้งที่จำนวน n ถูกแปลงเป็น 1 โดยเฉพาะ dp [1] = 1 ตามความหมายของคำถามเราจะได้รับความสัมพันธ์แบบเรียกซ้ำดังต่อไปนี้:

  • เมื่อ n เป็นจำนวนคี่ dp [n] = min (dp [n + 1], dp [n-1]) + 1
  • เมื่อ n เป็นเลขคู่ dp [n] = dp [n / 2] +1

โปรดสังเกตว่าถ้าเลขคี่เขียนการวนซ้ำนี้และ n เป็นประเภท int ดังนั้น n + 1 อาจล้นจำนวนเต็มดังนั้นจึงไม่ดี เนื่องจาก n + 1 จำเป็นต้องเป็นเลขคู่จึงสามารถทำการปรับปรุงต่อไปนี้ได้:



  • เมื่อ n เป็นจำนวนคี่ dp [n] = min (dp [(n >> 1) +1] +1, dp [n-1]) + 1

เพื่อหลีกเลี่ยงปรากฏการณ์ล้น

นอกจากนี้ยังมีหลายเส้นทางสำหรับการเรียกซ้ำแบบวนซ้ำและมีบางกรณีที่มีการเข้าถึง n เดียวกันซ้ำ ๆ เพื่อหลีกเลี่ยงการเรียกซ้ำซ้ำค่าที่เรียกซ้ำก่อนหน้านี้จะถูกเก็บไว้ในตารางแฮชและสามารถใช้ unordered_map ได้ วิธีนี้อัลกอริทึมเกือบจะสมบูรณ์แบบ

รหัส C ++
class Solution {
สาธารณะ:
int integerReplacement (int n) {
ถ้า (mp [n]> 0) ส่งคืน mp [n]
อื่น mp.erase (n)
ถ้า (n == 1) ส่งคืน 0
ถ้า ((n & 1) == 0) {
int num1 = integerReplacement (n >> 1) + 1
mp [n] = num1
ส่งคืน num1
}
int add = integerReplacement ((n >> 1) + 1) + 2
int del = integerReplacement (n - 1) + 1
int เล็ก = นาที (เพิ่มเดล)
mp [n] = เล็ก
กลับเล็ก
}
unordered_map mp
}