นำตัวเลขลงมาที่ 1 ใน JavaScript

ปัญหา

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่ใช้ตัวเลข num เป็นอาร์กิวเมนต์เดียว

• ฟังก์ชันของเราสามารถทำได้เพียงสองการดำเนินการนี้กับ num:ถ้า num เป็นเลขคู่ เราสามารถแทนที่ num ด้วย num/2

• หาก num เป็นเลขคี่ เราสามารถแทนที่ num ด้วย num + 1 หรือ num - 1

การใช้เฉพาะการดำเนินการทั้งสองนี้ร่วมกัน ฟังก์ชันของเราต้องคำนวณจำนวนการดำเนินการขั้นต่ำที่ต้องใช้เพื่อลดจำนวนลงเหลือ 1 ฟังก์ชันควรคืนค่าจำนวนการดำเนินการขั้นต่ำ

ตัวอย่างเช่น หากอินพุตของฟังก์ชันคือ −

const num = 7;

จากนั้นผลลัพธ์ควรเป็น −

const output = 4;

คำอธิบายผลลัพธ์:

เนื่องจากการดำเนินการที่น้อยที่สุดที่เป็นไปได้คือ −

7 -> 8 -> 4 -> 2 -> 1
or
7 -> 6 -> 3 -> 2 -> 1

ตัวอย่าง

รหัสสำหรับสิ่งนี้จะเป็น −

const num = 7;
const downToOne = (num = 1) => {
   let min = Number.POSITIVE_INFINITY;
   let stack = [{ num: num, step: 0 }];
   let set = new Set();
   let next;
   let item;
   while (stack.length) {
      item = stack.shift();
      if (item.num === 1) {
         if (min > item.step) {
            min = item.step;
         }
         continue;
      }
      if (set.has(item.num) || item.step >= min) {
         continue;
      }
      set.add(item.num);
      next = item.step + 1;
      if (item.num % 2 === 0) {
         item.num /= 2;
         stack.push({ num: item.num, step: next });
      } else {
         stack.push({ num: item.num - 1, step: next });
         stack.push({ num: item.num + 1, step: next });
      }
   }
   return min;
};
console.log(downToOne(num));

ผลลัพธ์

ผลลัพธ์ในคอนโซลจะเป็น -

4