Daily question brushing record (I)

The first question is : massagist

LeetCode Interview questions 17.16. massagist

describe :
A famous masseuse will receive a steady stream of appointment requests , Every appointment can be accepted or not . There should be a break between appointments , So she can't accept the next appointment . Given an appointment request sequence , Find the best set of appointments for the masseuse （ The longest total appointment time ）, Return the total minutes .

Their thinking :

Dynamic planning ideas :

• state F(i) : Indicates the current maximum appointment time
• State transition equation : F(i) = Max( F(i-2)+nums[i] , F(i-1) )
• The initial state : F(0) = nums[0] ,F(1) = Max( nums[0] , nums[1] )
• Return results : F(len-1)

 
The main consideration here is , Total appointment time at the time of addition , It may not be as long as not being separated .( General dynamic gauges cannot be taken continuously , You need to consider this situation if you want to rest )
for example : [1,5,2] there 1+ 2 < 5, therefore dp The array element is [1,5,5]
End of traversal , dp The last element , Is the longest appointment time

Code implementation :

class Solution {
    
    public int massage(int[] nums) {
    
    	//  Here are two special cases 
        if(nums.length==0) return 0;
        if(nums.length==1) return nums[0];
        //  Definition dp Array 
        int[] dp = new int[nums.length];
        //  The initial state 
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for(int i = 2; i < nums.length; i++){
    
        	//  State transition equation 
            dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        //  result 
        return dp[nums.length-1];
    }
}

The second question is : Main elements

LeetCode Interview questions 17.10. Main elements

describe :
More than half of the elements in an array are called major elements . To give you one Integers Array , Find out the main elements . If there is no , return -1 .
Please design the time complexity as O(N) 、 The space complexity is O(1) Solutions for .

Their thinking :

You can use a hash table here , Sorting and so on , However, the time complexity of failure to reach is O(N) 、 The space complexity is O(1)
 
Use the Moore voting method to do :

1. Traverse current array nums, count Indicates the number of times the current number , num For the current number
2. When count by 0 When , Give Way num be equal to nums[i], count++;
3. When count Not for 0 When , nums[i] It's not equal to num, let count–; Equal to let count++;
4. After the traversal is over , Traverse again , Verify the current num Whether the number of times is greater than half of the total elements

Code implementation :

Moore voting

class Solution {
    
    public int majorityElement(int[] nums) {
    
        int num = 0;
        int count = 0;
        for(int val : nums) {
    
        	//  The number of votes is 0,  New voters 
            if(count == 0) num = val;
            //  If it is the current voter's vote ++
            if(num == val) count++;
            //  Not the current voter's vote --
            else count--;
        }
        count = 0;
        //  Judge whether the current voter has more than half the votes 
        for(int val : nums) {
    
            if(val == num) {
    
                count++;
            }
        }
        if(count>nums.length/2) return num;
        else return -1;
    }
}

HashMap Methods

class Solution {
    
    public int majorityElement(int[] nums) {
    
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int val : nums) {
    
            map.put(val,map.getOrDefault(val,0)+1);
            if(map.get(val) > nums.length/2) return val;
        }
        return -1;
    }
}

Third question : The first k Number

LeetCode Interview questions 17.09. The first k Number
describe :
Some numbers have prime factors only 3,5,7, Please design an algorithm to find out the k Number . Be careful , It's not necessary to have these prime factors , It must not contain other prime factors . for example , The first few numbers should be in order 1,3,5,7,9,15,21.

Their thinking :

Dynamic planning ideas :

• state F(i) : The first i+1 Which factor is the number
• State transition equation : F(i) = Min(dp[x3] * 3, dp[x5] * 5, dp[x7] * 7)
• The initial state : F(0) = 1
• Return results : F(len-1)
   

there dp[x3]*3,dp[x5]*5,dp[x7]*7 It is equivalent to three series of ugly numbers

• dp[0]*3, dp[1]*3,dp[2]*3, … , dp[n]*3
• dp[0]*5, dp[1]*5,dp[2]*5, … , dp[n]*5
• dp[0]*7, dp[1]*7,dp[2]*7, … , dp[n]*7

Combine by taking the minimum value of these three series , To form a complete series of ugly numbers . After fetching a column of data each time , Let this column of data be added back 1,
for example

Code implementation :

class Solution {
    
    public int getKthMagicNumber(int k) {
    
    	//  The initial subscripts are all from 0 Start 
        int x3 = 0;
        int x5 = 0;
        int x7 = 0;
        //  Define the ugly number sequence  dp
        int[] dp = new int[k];
        //  initialization 
        dp[0] = 1;
        for(int i = 1; i < k;i++) {
    
            //  Get the minimum 
            dp[i] = Math.min(Math.min(dp[x3]*3,dp[x5]*5),dp[x7]*7);
            //  Use here  3 individual if  You can eliminate duplication 
            if(dp[i] == dp[x3]*3) x3++;
            if(dp[i] == dp[x5]*5) x5++;
            if(dp[i] == dp[x7]*7) x7++;
        }
        return dp[k-1];
    }
}

Fourth question : Continuous sequence of numbers

LeetCode Interview questions 16.17. Continuous sequence of numbers
describe :
Given an array of integers , Find the sequence with the largest sum , And return the sum .

Their thinking :

Dynamic planning ideas :

• state F(i) : i The maximum sum of coordinates
• State transition equation : F(i) = Max( nums[i]+F(i-1),nums[i])
• The initial state : F(0) = nums[0]
• Return results : Max(F(i))
   

The basic kinematic solution , Just record the maximum value .

Code implementation :

class Solution {
    
    public int maxSubArray(int[] nums) {
    
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int res=dp[0];
        for(int i = 1; i < nums.length; i++){
    
            dp[i] = Math.max(nums[i]+dp[i-1],nums[i]);
            //  Record the maximum 
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}

Fifth question : Interview questions 16.15. Zhuji wonderful calculation

LeetCode Interview questions 16.15. Zhuji wonderful calculation
describe :
Abas magic calculation game （the game of master mind） Here's how to play .

Computers have 4 Slot , Put a ball in each slot , The color could be red （R）、 yellow （Y）、 green （G） Or blue （B）. for example , Computers may have RGGB 4 Kind of （ Slot 1 In red , Slot 2、3 It's green , Slot 4 For blue ）. As the user , You try to guess the color combination . For example , You might guess YRGB. If you guess the color of a slot , It's one time “ Guess right ”; If you only guess the right color, but the slot is wrong , It's one time “ A false guess ”. Be careful ,“ Guess right ” Can't count into “ A false guess ”.

Given a color combination solution And a guess guess, Write a method , Returns the number of hits and false guesses answer, among answer[0] For the number of guesses ,answer[1] The number of false guesses .

Their thinking :

This question means , If the current guess is right , Guess right +1, The rest is wrong , If you guess the right color, it will be a false guess , But it doesn't count the one you guessed right .

for example solution="RGBY" guess="GGRR'
You guessed right here i=1 Coordinates G, solution The remaining “RBY” guess The remaining "GRR", The corresponding can only be counted as one false guess

1. Go through the first time , Count the number of guesses , Then record the missing elements .
2. Traverse the missing elements again , Calculate the current number of false guesses .

Code implementation :

class Solution {
    
    public int[] masterMind(String solution, String guess) {
    
        int[] answer = new int[2];
        // str The record missed the character 
        StringBuilder str = new StringBuilder();
        // s Record the number of characters left on the computer 
        int[] s = new int[130];
        for(int i = 0; i < 4; i++) {
    
            char ch1 = solution.charAt(i);
            char ch2 = guess.charAt(i);
            if(ch1 == ch2){
    
            	// Here is the number of guesses 
                answer[0]++;
            }else{
    
                s[ch1-'A']++;
                str.append(ch2);
            }
        }
        for(int i = 0; i < str.length() ; i++){
    
            char ch = str.charAt(i);
            //  If I guess the color ,  There is still something left in the computer , Even if the false guess is right 
            if(s[ch-'A'] != 0){
    
                s[ch-'A']--;
                answer[1]++;
            }
        }
        return answer;
    }
}

Sixth question : Partial sorting

LeetCode Interview questions 16.16. Partial sorting
describe :
Given an array of integers , Write a function , Find the index m and n, Just index the range [m,n] The elements of are in order , The whole array is ordered . Be careful ：n-m As little as possible , in other words , Find the shortest sequence that meets the conditions . The return value of the function is [m,n], If there is no such m and n（ For example, the whole array is ordered ）, Please return [-1,-1].

Their thinking :

1. Copy an array , Sort the copied array .
2. Then find out the coordinates of the first mismatch left And the coordinates of the last mismatch right
3. At the time of initial definition Definition left =-1 right =-1 So when there are no mismatched coordinates , I can go back [-1,-1]

Code implementation :

class Solution {
    
    public int[] subSort(int[] array) {
    
        int[] arr = Arrays.copyOf(array,array.length);
        Arrays.sort(arr);
        int left=-1;
        int right =-1;
        for(int i = 0; i < arr.length; i++) {
    
            if (arr[i] != array[i]){
    
            	// left Only the coordinates of the first mismatch are recorded 
                if(left == -1) {
    
                    left = i;
                }
                // right Record the coordinates of the last mismatch 
                right = i;
            }
        }
        //  If all match , left right  Namely  [-1,-1]
        return new int[]{
    left,right};
    }
}