LeetCode解题 Day01

565. Array Nesting

https://leetcode.com/problems/array-nesting/

题目介绍:

你会得到一个长度是n，范围是[0 ~ n-1]的 nums
并且要组合一个集合 s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ... }
详细规则我们以Example 1 解释

Example 1:

一开始的集合是 s[0] ，我们第一个元素就是 nums[0] = 5 ，第二个元素则是 nums[5] = 6 ，以此类推直到 nums[i] 等於 0。

而我们的任务是回传最长的 s[k] 的长度

解法1:

这题的难度是Medium，不过其实蛮简单的，很快就能想到硬干的方法

只要照字面意思run过每个集合，并回传最大的长度就好

但是，这种解法遇到长度很长的测试案例就会超过时间了，送出去会显示 Time Limit Exceeded。

程序码:

class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
    
        res = 0
        
        for i in range(len(nums)):
            count = 1
            j = nums[i]
            while nums[j] != nums[i]:
                j = nums[j]
                count += 1
            
            res = max(count, res) #纪录最大的长度
            
        return res

解法修改:

上一个解法是因为我们会重复计算好几个过程

像是 example1 中的 s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}

我们可以知道 k = 0 时集合为长度4的 {5,6,2,0}

那我们就可以知道 k 为 5, 6, 2, 0时，就都是长度为4的集合，就像下图绕圈圈的这种感觉

那我们就没必要重复run过 k=5, k=6, k=2 了

程序码:

class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        
        res = 0
        visted = set()
        
        for i in range(len(nums)):
            
            if nums[i] in visted:
                continue
            
            count = 1
            j = nums[i]
            while nums[j] != nums[i]:
                visted.add(j) #记录可以省略的数字
                j = nums[j]
                count += 1
            
            res = max(count, res)
            
        return res