LeetCode.565. 数组嵌套____暴力dfs-＞剪枝dfs-＞原地修改

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}

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] < nums.length
• A中不含有重复的元素。

Solution1(暴力dfs):

• 每次任选一个起点开始，接着使其不断的走，边走边进行标记，直到无法继续走后，判断长度即可，接着标记数组进行回溯，从下一个起点再继续走。

• 这样为直接暴力会超时，因为环的特点，所以其实是不需要进行回溯操作的。

Code1:

/* 暴力dfs */
class Solution {
    int res = 0;
    
    public int arrayNesting(int[] nums) {
        int len = nums.length;
        boolean[] visited = new boolean[len];
        for(int i=len - 1;i >= 0;i--){
            List<Integer> list = new ArrayList<>();
            list.add(nums[i]);
            visited[i] = true;
            dfs(nums,list,visited,len);
            visited[i] = false;
        }
        return res;
    }

    public void dfs(int[] nums,List<Integer> list,boolean[] visited,int len){
        int top = list.get(list.size() - 1);
        if(!visited[top]){
            list.add(nums[top]);
            visited[top] = true;
            dfs(nums,list,visited,len);
            visited[top] = false;
        }
        else{
            res = Math.max(res,list.size());
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

Solution2(剪枝dfs):

• 首先把握好环的特点，即为循环结构，从任意起点出发均能遍历完全此环；
• 对于o~n-1的数列且每个数字出现一次的数组必然构成一个或者多个独立的环形，这个数组一定能被分为几个独立的环，且不论从这个环的哪个点开始都能一下子走完这个环，所以一旦走过的点直接标记已经走过即可，因为别的环是不会走它的；

Code2:

class Solution {

    // 这个是剪枝的dfs写法，直白回溯暴力查找的dfs写法也可以，但是会超时
    int res = 0;
    
    public int arrayNesting(int[] nums) {
        int len = nums.length;
        boolean[] visited = new boolean[len];
        for(int i=len - 1;i >= 0;i--){
            List<Integer> list = new ArrayList<>();
            list.add(nums[i]);
            visited[i] = true;
            dfs(nums,list,visited,len);
        }
        return res;
    }

    public void dfs(int[] nums,List<Integer> list,boolean[] visited,int len){
        int top = list.get(list.size() - 1);
        if(!visited[top]){
            list.add(nums[top]);
            visited[top] = true;
            dfs(nums,list,visited,len);
        }
        else{
            res = Math.max(res,list.size());
        }
    }
}


/* 其实也可以不用list来专门存储环的内部元素，只要拿到每次要指向的要素及环内元素总个数即可 */
class Solution {
    int res = 0;
    
    public int arrayNesting(int[] nums) {
        int len = nums.length;
        boolean[] visited = new boolean[len];
        for(int i=len - 1;i >= 0;i--){
            visited[i] = true;
            dfs(nums,nums[i],visited,len,1);
        }
        return res;
    }

    public void dfs(int[] nums,int dir,boolean[] visited,int len,int size){
        if(!visited[dir]){
            visited[dir] = true;
            dfs(nums,nums[dir],visited,len,size + 1);
        }
        else{
            res = Math.max(res,size);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

Solution3(原地修改):

• 我们可以不用递归，使用for+while即可，且我们因为数组中的某一点在用过之后一定不会被再用了，所以我们可以不用专门开一个数组来进行标记，可以直接在原数组上进行标记，这是因为我们不需要回溯操作。并且我们的标记不是为了自己的环遍历的时候会重复的查找其他的环，因为他们彼此是独立的，是为了使得自己的环不会被一直遍历查找，即是标记给自己环看的；

Code3:

/* 原地修改 */
class Solution {
   
    public int arrayNesting(int[] nums) {
        int len = nums.length;
        int max = 0;
        for(int i=0;i<len;i++){
            int dir = i;
            int temp_len = 0;
            while(nums[dir] != -1){
                int temp = nums[dir];
                nums[dir] = -1;
                dir = temp;
                temp_len++;
            }
            max = Math.max(max,temp_len);
            if(max > len/2)
                return max;
        }
        return max;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23