Leetcode.565. array nesting____ Violent dfs- > pruning dfs- > in situ modification

565. Array nesting

Index from 0 Start length is N Array of A, contain 0 To N - 1 All integers of . Find the largest set S And return its size , among S[i] = {A[i], A[A[i]], A[A[A[i]]], … } And abide by the following rules .

Suppose the selection index is i The elements of A[i] by S The first element of ,S The next element of should be A[A[i]], And then A[A[A[i]]]… And so on , Keep adding until S Duplicate elements appear .

Example 1:

Input : A = [5,4,0,3,1,6,2]
Output : 4
explain :
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
One of the longest S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

Tips ：

• 1 <= nums.length <= 105
• 0 <= nums[i] < nums.length
• A There are no duplicate elements in the .

Solution1( violence dfs):

• Choose a starting point at any time , Then make it keep walking , Mark while walking , Until I can't go on , Judge the length , Then mark the array for backtracking , Continue from the next starting point .

• Such direct violence will timeout , Because of the characteristics of the ring , So in fact, there is no need for backtracking .

Code1:

/*  violence 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());
        }
    }
}

Solution2( prune dfs):

• First, grasp the characteristics of the ring , That is to say Loop structure , This ring can be traversed completely from any starting point ;
• about o~n-1 The array in which each number appears once must form one or more Independent The ring of , This array must be divided into Several independent rings , And no matter from which point of this ring, you can finish this ring at once , So once you have passed the point, you can directly mark that it has passed , Because other rings won't walk it ;

Code2:

class Solution {
    

    //  This is pruned dfs How to write it , Straight back violence search dfs The writing method is also OK , But it will time out 
    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());
        }
    }
}


/*  In fact, it can not be used list To specifically store the internal elements of the ring , Just get the elements you want to point to each time and the total number of elements in the ring  */
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);
        }
    }
}

Solution3( Modify in place ):

• We can avoid recursion , Use for+while that will do , And because a certain point in the array will not be reused after being used , So we don't need to open a special array to mark , You can mark directly on the original array , This is because we don't need backtracking . And our mark is not for our own ring. When traversing, we will repeatedly find other rings , Because they are independent of each other , Is to make their own ring will not be traversed and searched all the time , That is Mark yourself around Of ;

Code3:

/*  Modify in place  */
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;
    }

}