The first question is : 1394. Find the lucky number in the array

LeetCode: 1394. Find the lucky number in the array

describe :
In an array of integers , If the frequency of an integer is the same as its value , We call this whole number 「 Lucky number 」.

Give you an array of integers arr, Please find out and return a lucky number .

• If there are more than one lucky number in the array , Just go back Maximum the .
• If there are no lucky numbers in the array , Then return to -1 .

Their thinking :

1. First use a length of 501 Array of , For storage , Store the number of occurrences of each number .
2. To return the same number of occurrences , And the biggest .
3. In this way, you can directly consider the array length , Because the maximum number of occurrences is the array length , So give priority to array length .
4. And then smaller and smaller to find out whether there is one that meets the conditions .

Code implementation :

class Solution {
    
    public int findLucky(int[] arr) {
    
        int[] count = new int[501];
        for(int val : arr) {
    
            count[val]++;
        }
        for(int i = arr.length; i>0 ;i--) {
    
            if(count[i] == i){
    
                return i;
            }
        }
        return -1;
    }
}

The second question is : 1512. A good number of pairs

LeetCode: 1512. A good number of pairs

describe :
Give you an array of integers nums .

If a set of numbers (i,j) Satisfy nums[i] == nums[j] And i < j , You can think of this as a group Good number of pairs .

Returns the number of good pairs .

Their thinking :

1. First create a length of 101 Array of , Used to store the number of occurrences .
2. For the first appearance of numbers , Do not add , After each occurrence, add the number of occurrences .
3. for example 1, 1, 1, 3
   • First appearance 1, res Do not add , Now count 1 Time
   • The second time 1, res Add up , res=1, Now count 2 Time
   • A third time 1, res Add up , res=3, Now count 3 Time
4. End of traversal return res

Code implementation :

class Solution {
    
    public int numIdenticalPairs(int[] nums) {
    
        int[] count = new int[101];
        int res = 0;
        for(int num : nums) {
    
            res += count[num];
            count[num]++;
        }
        return res;
    }
}

Third question : Interview questions 10.11. Peak and valley

LeetCode: Interview questions 10.11. Peak and valley

describe :
In an array of integers ,“ peak ” Is an element greater than or equal to an adjacent integer , Accordingly ,“ valley ” Is an element less than or equal to an adjacent integer . for example , In the array {5, 8, 4, 2, 3, 4, 6} in ,{8, 6} It's the peak , {5, 2} It's the valley . Now, given an array of integers , Sort the array in alternating order of peaks and valleys .

Their thinking :

1. This question means one big and one small , Alternate .
2. You can sort the array .
3. Then use the double pointer , A pointing head , One points to the tail .
4. Put the largest one at a time (right–), Put another smallest (left++),

Code implementation :

class Solution {
    
    public void wiggleSort(int[] nums) {
    
        int[] arr = new int[nums.length];
        for(int i = 0; i < nums.length; i++) {
    
            arr[i] = nums[i];
        }
        Arrays.sort(arr);
        int left = 0;
        int right = arr.length-1;
        for(int i = 0; i < nums.length; i++) {
    
            if(i%2==0){
    
                nums[i] = arr[right--];
            }else{
    
                nums[i] = arr[left++];
            }
        }
    }
}

Fourth question : Interview questions 16.26. Calculator

LeetCode: Interview questions 16.26. Calculator

describe :
Given an integer containing a positive integer 、 Add (+)、 reduce (-)、 ride (*)、 except (/) Arithmetic expression of ( Except brackets ), Calculate the result .

The expression contains only non negative integers ,+, - ,*,/ Four operators and spaces . Division of integers preserves only the integral part .

Their thinking :

1. Here a stack is used to store data .
2. Store the current data , it is to be noted that , There will be continuous numbers
3. The first operation , Directly stack , Then record the operator .
4. If it's time to add, subtract, multiply and divide again , See what the previous operator is
   • If it is -, Deposit in -num
   • If it is +, Deposit in num
   • If it is *, Deposit in stack.pop() * num
   • If it is / , Deposit in stack.pop() / num
5. After the traversal , Stack storage is all data , At this point, the result is to add all the data directly

Code implementation :

class Solution {
    
    public int calculate(String s) {
    
        Stack<Integer> stack = new Stack<>();
        //  It's convenient to directly stack for the first time 
        char opt = '+';
        int num = 0;
        for(int i = 0; i < s.length(); i++) {
    
            if(Character.isDigit(s.charAt(i))){
    
                num = num * 10 + (s.charAt(i) - '0');
            }
            if((!Character.isDigit(s.charAt(i)) && s.charAt(i)!=' ') || i == s.length() - 1){
    
                if(opt == '+') stack.push(num);
                else if(opt == '-') stack.push(-num);
                else if(opt == '*') stack.push(stack.pop() * num);
                else stack.push(stack.pop() / num);
                num = 0;
                opt = s.charAt(i);
            }
        }
        int res = 0;
        while(!stack.isEmpty()){
    
            res += stack.pop();
        }
        return res;
    }
}

Fifth question : Interview questions 17.12. BiNode

LeetCode: Interview questions 17.12. BiNode

describe :
Binary tree data structure TreeNode Can be used to represent a one-way list （ among left empty ,right For the next linked list node ）. Implement a method , The binary search tree into a one-way list , The requirements still conform to the nature of binary search tree , The conversion operation should be original , That is to modify it directly on the original binary search tree .

Returns the header node of the converted unidirectional linked list .

Their thinking :

1. Here we use the method of middle order traversal .
2. First, there is a precursor node , Used to link .
3. In the sequence traversal , Let the pioneer node link ( Link on the right node ), And leave the left node of the node empty . Let this node point to root.
4. Finally, return to the next node of the precursor node .

Code implementation :

class Solution {
    
    TreeNode cur = new TreeNode(-1);
    TreeNode pre = cur;
    public TreeNode convertBiNode(TreeNode root) {
    
        if (root == null) return null;
        convertBiNode(root.left);
        cur.right = root;
        root.left = null;
        cur = root;
        convertBiNode(root.right);
        return pre.right;
    }
}

Sixth question : Interview questions 17.19. Two missing numbers

LeetCode: Interview questions 17.19. Two missing numbers

describe :
Given an array , Contains from 1 To N All integers , But two numbers are missing . Can you in O(N) Only in time O(1) Space to find them ？

Return these two numbers in any order .

Their thinking :

1. The mathematical idea used here
2. First, find the total sum of the array total
3. And then use it Summation formula Get 1 ~ len(nums)+2 And sum.
4. And then let this sum - total Find the sum of two vanishing numbers .
5. Then find the average of these two numbers mid
6. Traverse... Again , Seek less than mid And , 1 ~ mid There must be a missing number in .
7. Let the sum at this time subtract The sum that satisfies the condition in the array . Is one of the results .
8. Let the sum of two numbers Subtracting one result is the other result .

Code implementation :

class Solution {
    
    public int[] missingTwo(int[] nums) {
    
        int total = 0;
        for(int num : nums) {
    
            total += num;
        }
        int sum = (nums.length+2+1)*(nums.length+2)/2 - total;
        int mid = sum/2;
        total = 0;
        for(int num : nums) {
    
            if(num <= mid) {
    
                total += num;
            }
        }
        int res = (1+mid)*mid/2 - total;
        return new int[]{
    res, sum-res};
    }
}