565. Array Nesting

LeetCode medium original: C# #array #csharp #hash-table #leetcode #math #medium
Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.
LeetCode Static

Дан mảng целых чисел nums длиной n, где nums является перестановкой чисел в диапазоне [0, n - 1].

Вы должны построить множество s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ...} при соблюдении следующего правила:

Первый element в s[k] начинается с выбора elementа nums[k] с индексом k.

Следующий element в s[k] должен быть nums[nums[k]], затем nums[nums[nums[k]]], и так далее.

Мы прекращаем добавлять elementы непосредственно перед тем, как в s[k] появится дубликат.

return длину самого длинного множества s[k].

Ví dụ:

Input: nums = [5,4,0,3,1,6,2]

Output: 4

Explanation:

nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2.

One of the longest sets s[k]:

s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}

C# lời giải

đã khớp/gốc 
public class Solution {
    public int ArrayNesting(int[] nums) {
        bool[] visited = new bool[nums.Length];
        int maxLength = 0;
        
        for (int i = 0; i < nums.Length; i++) {
            if (!visited[i]) {
                int start = i;
                int count = 0;
                while (!visited[start]) {
                    visited[start] = true;
                    start = nums[start];
                    count++;
                }
                maxLength = Math.Max(maxLength, count);
            }
        }
        
        return maxLength;
    }
}

C++ lời giải

bản nháp tự động, xem lại trước khi gửi 
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int ArrayNesting(vector<int>& nums) {
        bool[] visited = new bool[nums.size()];
        int maxLength = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            if (!visited[i]) {
                int start = i;
                int count = 0;
                while (!visited[start]) {
                    visited[start] = true;
                    start = nums[start];
                    count++;
                }
                maxLength = max(maxLength, count);
            }
        }
        
        return maxLength;
    }
}

Java lời giải

đã khớp/gốc 
public class Solution {
    public int arrayNesting(int[] nums) {
        boolean[] visited = new boolean[nums.length];
        int maxLength = 0;
        
        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                int start = i;
                int count = 0;
                while (!visited[start]) {
                    visited[start] = true;
                    start = nums[start];
                    count++;
                }
                maxLength = Math.max(maxLength, count);
            }
        }
        
        return maxLength;
    }
}

JavaScript lời giải

đã khớp/gốc 
class Solution {
    arrayNesting(nums) {
        const visited = new Array(nums.length).fill(false);
        let maxLength = 0;
        
        for (let i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                let start = i;
                let count = 0;
                while (!visited[start]) {
                    visited[start] = true;
                    start = nums[start];
                    count++;
                }
                maxLength = Math.max(maxLength, count);
            }
        }
        
        return maxLength;
    }
}

Python lời giải

đã khớp/gốc 
class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        visited = [False] * len(nums)
        max_length = 0
        
        for i in range(len(nums)):
            if not visited[i]:
                start = i
                count = 0
                while not visited[start]:
                    visited[start] = True
                    start = nums[start]
                    count += 1
                max_length = max(max_length, count)
        
        return max_length

Go lời giải

đã khớp/gốc 
func arrayNesting(nums []int) int {
    visited := make([]bool, len(nums))
    maxLength := 0
    
    for i := 0; i < len(nums); i++ {
        if !visited[i] {
            start := i
            count := 0
            for !visited[start] {
                visited[start] = true
                start = nums[start]
                count++
            }
            if count > maxLength {
                maxLength = count
            }
        }
    }
    
    return maxLength
}

Algorithm

Создайте mảng для отслеживания посещенных elementов.

Для каждого elementа в nums, если он не посещен, начните формирование множества s[k], последовательно переходя по elementам, пока не встретится уже посещенный element.

Обновите максимальную длину найденного множества.

😎

Vacancies for this task

việc làm đang hoạt động with overlapping task tags are đã hiển thị.

Tất cả việc làm
Chưa có việc làm đang hoạt động.