การหาและคืนค่าความยาวเซตที่ยาวที่สุดใน JavaScript

ปัญหา

เราต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ตัวเลข arr เป็นอาร์กิวเมนต์แรกและเดียว อาร์เรย์ arr ความยาว N มีจำนวนเต็มทั้งหมดจาก 0 ถึง N-1 ฟังก์ชันควรหาและคืนค่าความยาวที่ยาวที่สุดของเซต S โดยที่ S[i] = {A[i], A[A[i]], A[A[A[i]]], ... } ภายใต้กติกาด้านล่าง

สมมติสมาชิกแรกใน S เริ่มจากการเลือก A[i] ดัชนี = i สมาชิกถัดไปใน S ควรเป็น A[A[i]] แล้ว A[A[A[i]]]... ตาม аналогия นี้ เราหยุดเพิ่มทันทีก่อนที่จะมีสมาชิกซ้ำใน S

เช่น ถ้าอินพุตคือ:

const arr = [5, 4, 0, 3, 1, 6, 2];

ผลลัพธ์ควรเป็น:

const output = 4;

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

A[0]=5, A[1]=4, A[2]=0, A[3]=3, A[4]=1, A[5]=6, A[6]=2 หนึ่งใน S[K] ที่ยาวที่สุด:

S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

ตัวอย่าง

โค้ดตัวอย่างด้านล่าง:

const arr = [5, 4, 0, 3, 1, 6, 2];
const arrayNesting = (arr = []) => {
  const visited = {};
  const aux = (index) => {
    if (visited[index]) {
      return 0;
    }
    visited[index] = true;
    return aux(arr[index], visited) + 1;
  };
  let max = 0;
  arr.forEach((n, index) => {
    if (!visited[index]) {
      max = Math.max(max, aux(index));
    }
  });
  return max;
};
console.log(arrayNesting(arr));

ผลลัพธ์

4

คำอธิบายเพิ่มเติม

นี่คือปัญหา "Array Nesting" (LeetCode 565) หา cycle ยาวที่สุดใน permutation array ใช้ visited set กันนับซ้ำ DFS recursive นับความยาว cycle แต่ละ component