565. Array nesting / Sword finger offer II 001 Integer division

565. Array nesting 【 Medium question 】【 A daily topic 】

Ideas ：【 Drawing 】【 In situ marking 】

At first, I thought it was to build a graph to find the length of connectivity , The meaning of the solution is , Each connectedness is actually a ring , Because my array elements are not repeated , Then according to my pointing rule , My input and output of each node are 1, Then there must be a ring .
So we start at any node , The degree of 1, After the visit, the entry is set to 0（ Here, it can be simplified to mark the node as accessed , Optional tag array or in place tag 【 That is, it is marked as a number outside the value range 】）, Then move to the next node pointed , Judge whether the next node penetration is 0, When the penetration is also 0 when , It shows that our ring has reached the end , Start from entering the ring , Through a counting variable cnt, Every node visited , Count variables and add 1.
At the end of the ring ,cnt The value of is the length of the current ring , That is, the set of topics S The length of , We can pick out the longest of these rings and return .

Code ：

class Solution {
    
    public int arrayNesting(int[] nums) {
    
        int n = nums.length,ans = 0;
        // Traversal array , The current figure is nums[i]
        for (int i = 0; i < n; i++) {
    
            int cnt = 0;
            // Access the array in the order it points to the currently traversed number , Set the accessed element to n Indicates that you have visited （ Elements that have not been accessed must be smaller than n）
            while (nums[i] < n){
    
                // Mark the current number as  num
                int num = nums[i];
                // Set the current position element in the array to  n  Indicates that you have visited 
                nums[i] = n;
                // Move the pointer i, According to the topic rules , The subscript pointing to the next position is the current number num
                i = num;
                // Count variables +1, Indicates that another element is added to the ring 
                cnt++;
            }
            //cnt That is, the length of the current ring , use cnt To update the maximum length ans
            ans = Math.max(ans,cnt);
        }
        return ans;
    }
}

The finger of the sword Offer II 001. Integer division 【 Simple questions 】

Ideas ：

This simple question is not simple at all ~
I put it off until now , The whole sword finger Offer II I'll write it when I'm almost finished , It's over , This list of questions is left 5 Difficult questions , No more writing, no more writing , Let's finish with this question .

Obviously, this problem still depends on the solution , In fact, it is also a very smooth idea , First, exclude the special circumstances of the boundary , Then the divisor and divisor are all processed into negative numbers according to the data range , Because the range of negative numbers is a little wider .

Then the simulation of the division process, I think the explanation of the question is not particularly clear , To be straightforward and understandable, you have to be a boss yukiyama The antithesis of .

Big guys usually post questions in the official interpretation comment area , So I can only post links to the boss' homepage .

I wrote notes for the specific implementation , Not here .

Code ：

class Solution {
    
    public int divide(int a, int b) {
    
        int MIN = Integer.MIN_VALUE,MAX = Integer.MAX_VALUE,MIN_LIMIT = MIN >> 1;
        // The divisor is 0 when , The result is 0
        if (a == 0){
    
            return 0;
        }
        // The divisor is MIN when , If the divisor is -1, The result overflows , Return to MAX; If the divisor is 1, The result is MIN
        if (a == MIN){
    
            if (b == 1){
    
                return MIN;
            }
            if (b == -1){
    
                return MAX;
            }
        }
        // Divisor is MIN when , When the dividend is also MIN when , return 1, Otherwise return to 0
        if (b == MIN){
    
            return a == MIN ? 1 : 0;
        }
        // When two numbers have the same number , The result of division is a positive number  ; When there is a different sign , The result of division is negative . Then we can mark whether the two numbers have the same number , Then treat the two numbers as the same number , The final answer ans Decide to return according to whether the two numbers have the same sign ans still -ans that will do 
        boolean isPos = (a > 0 && b > 0) || (a < 0 && b < 0);
        // Treat two numbers with the same number , It can be treated as positive , It can also be treated as the same negative , When processed into the same timing , May cause data removal , For example, divisor a by MIN, Taking the opposite number will cause data overflow , So we take the same negative , In this way, the data range of taking the opposite number is wider 
        if (a > 0){
    
            a = -a;
        }
        if (b > 0){
    
            b = -b;
        }
        // Record the result of division , Initialize to 0
        int ans = 0;
        // Because division cannot be used , Then we use subtraction , Use continuously through exponential expansion a-b, if a and b All positive , Then when a<b Time means the end is reached ; if a and b All negative , So just the opposite , When a>b Only then divide to the end 
        // because a and b Have been processed as negative numbers , So the cycle condition of division operation is  a <= b
        while (a <= b){
    
            // Mark the current exponential expansion minuend as  d, For the initial  b, Define the number of times to be reduced as  c（ The number of times this is reduced is  a  Divide  b The quotient of the exponential power of ）
            int d = b,c = 1;
            //d Not less than MIN_LIMIT（ Notice the d It's a negative number ）, Otherwise the data will overflow , And  d  Not less than  a  Half of , Otherwise, if the divisor exceeds the dividend 
            while (d >= MIN_LIMIT && d + d >= a){
    
                // Under legal circumstances , Multiply d
                d += d;
                //c That is to say b The exponent of the power of 
                c += c;
            }
            // When the above cycle exits ,d That is in a The largest one that can be reduced in the range of b The power of , here c Is the exponent of this power ,ans You need to add this index 
            a -= d;
            ans += c;
            // Then reuse the remaining a To subtract b The maximum power that can be reached at this time 
            // When  a > b  when , Division is over 
        }
        // If initially a、b Same number , Then return to ans; If initially a、b Different sign , Then return to -ans
        return isPos ? ans : -ans;
    }
}