LeetCode 565. 数组嵌套

.LeetCode 565. 数组嵌套

索引从0开始长度为N的数组A，包含0到N - 1的所有整数。找到并返回最大的集合S，S[i] = {A[i], A[A[i]], A[A[A[i]]], ... }且遵守以下的规则。
假设选择索引为i的元素A[i]为S的第一个元素，S的下一个元素应该是A[A[i]]，之后是A[A[A[i]]]... 以此类推，不断添加直到S出现重复的元素。
示例 1:
输入: A = [5,4,0,3,1,6,2]
输出: 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}
注意:
N是[1, 20,000]之间的整数。
A中不含有重复的元素。
A中的元素大小在[0, N-1]之间。

思路 : 如下图

    class Solution {
    Map<Integer,Integer> map = new HashMap<>();

    
    public int arrayNesting(int[] nums) {
        boolean[] isUse = new boolean[nums.length];
        List<Integer> list = new ArrayList<>();
        
        for(int x=0;x<nums.length;x++){
            list.add(dfs(nums,isUse,x,0));
        }
        
        int max = 0;
        for(Integer num:list){
            if(num>max){
                max = num;
            }
        }
        
        return max;
    }
    
    int dfs(int[] nums,boolean[] isUse,int next,int len){
        if(map.containsKey(next)){
            return map.get(next);
        }
        if(isUse[next] == true){
            return len;
        }
        isUse[next] = true;
        int sum = dfs(nums,isUse,nums[next],len+1);
        map.put(next,sum);
        isUse[next] = false;
        return sum;
    }
    
}

总结

使用Map来记录数据 减少不必要的递归

反馈与建议

• QQ：[3441242166]
• 邮箱：3441242166@qq.com