Daily question brushing record (XV)

The first question is : The finger of the sword Offer 57. And for s Two numbers of

LeetCode: The finger of the sword Offer 57. And for s Two numbers of
Add link description
describe :
Enter an ascending array and a number s, Find two numbers in an array , So that their sum is exactly s. If the sum of many pairs of numbers is equal to s, Then output any pair .

Their thinking :

1. The title here says array nums Is an incremental sort . You can use the double pointer method
2. use left Point to 0 Subscript , use right Point to nums.length-1 Subscript
3. If nums[left] + nums[right] > target , At this time and big , Just choose a small number , Give Way right--
4. If nums[left] + nums[right] < target , At this time and small , Just choose a large array , Give Way left++
5. If at this time nums[left] + nums[right] = target , Return the value of this subscript .
   

Code implementation :

class Solution {
    
    public int[] twoSum(int[] nums, int target) {
    
        int left = 0;
        int right = nums.length-1;
        while(left < right) {
    
            int total = nums[left] + nums[right];
            if (total > target) {
    
                right--;
            }else if(total < target) {
    
                left++;
            }else{
    
                return new int[]{
    nums[left],nums[right]};
            }
        }
        return new int[]{
    };
    }
}

The second question is : The finger of the sword Offer 57 - II. And for s Continuous positive sequence of

LeetCode: The finger of the sword Offer 57 - II. And for s Continuous positive sequence of

describe :
Enter a positive integer target , Output all and as target A sequence of continuous positive integers （ Contains at least two numbers ）.

The numbers in the sequence are arranged from small to large , The different sequences are arranged in descending order according to the first number .

Their thinking :

1. Here is also the method of using double pointers .
2. Give Way left = 1, Give Way right=2, from 1, 2 To traverse the
3. In Mathematics 1~n Sum up , Gauss theorem , (n + 1) * (n - 1 + 1) / 2, So get [left , right] And for , (right+left) * (right-left+1) / 2
4. If the current sum total > target, Give Way left++
5. If the current sum total < target, Give Way right++
6. If the current sum total = target, take [left,right] Join the result set . And let left++( Otherwise you can't get out of the loop )

Code implementation :

class Solution {
    
    public int[][] findContinuousSequence(int target) {
    
        List<int[]> res = new ArrayList<>();
        int left = 1;
        int right = 2;
        while(left < right) {
    
            int total = (right + left) * (right - left + 1) / 2;
            if(total > target) {
    
                left++;
            }else if(total < target){
    
                right++;
            }else{
    
                int[] tmp = new int[right-left+1];
                for(int i = 0; i < tmp.length; i++) {
    
                    tmp[i] = i + left;
                }
                res.add(tmp);
                left++;
            }
        }
        int[][] ans = new int[res.size()][];
        for(int i = 0; i < res.size(); i++) {
    
            ans[i] = res.get(i);
        }
        return ans;
    }
}

Third question : The finger of the sword Offer 58 - I. Flip word order

LeetCode: The finger of the sword Offer 58 - I. Flip word order

describe :
Enter an English sentence , Turn over the order of the words in the sentence , But the order of the characters in the word is the same . For the sake of simplicity , Punctuation is treated like ordinary letters . For example, input string "I am a student. “, The output "student. a am I”.

Their thinking :

1. For this question , First, remove the extra space at the beginning and end of the string .
2. Then according to the space , Split into string arrays
3. Then traverse from back to front , remember , There may be multiple spaces ,
4. If the current string is empty , continue
   5, Not empty , Add the current string directly , Then pay attention to the situation of adding spaces

Code implementation :

class Solution {
    
    public String reverseWords(String s) {
    
        s = s.trim();
        String[] str = s.split(" ");
        StringBuilder sb = new StringBuilder();
        for(int i = str.length-1; i >=0; i--) {
    
            if(str[i].equals("")) continue;
            sb.append(str[i]);
            if(i != 0) {
    
                sb.append(" ");
            }
        }
        return sb.toString();
    }
}

Fourth question : The finger of the sword Offer 59 - I. Maximum sliding window

LeetCode: The finger of the sword Offer 59 - I. Maximum sliding window

describe :
Given an array nums And the size of the sliding window k, Please find the maximum value in all sliding windows .

Their thinking :

1. Here construct a size of k Sliding window of
2. If the left border of the current sliding window , Not in the initial position , And The right border of the window > The maximum value of the previous window , Then directly make the maximum value of this window equal to the maximum value of the previous window .
3. If the left boundary of the current sliding window is not in the initial position , And The previous value of the left boundary of the window , Less than the maximum value of the previous window , that , Let the maximum value of this window equal to the minimum value of the previous window .( Because the newly added value , It is not as big as the maximum value of the previous window , Value to discard , Smaller than the maximum value of the previous window , that , This maximum has not changed )
4. dissatisfaction 2, 3 Directly traverse to find the maximum value .
5. Finally, return the maximum value of each window .
   

Code implementation :

class Solution {
    
    public int[] maxSlidingWindow(int[] nums, int k) {
    
        if(nums.length == 0) return new int[]{
    };
        int left = 0;
        int right = k - 1;
        int[] ans = new int[nums.length-k+1];
        while (right < nums.length) {
    
            if(left > 0 && nums[right] > ans[left-1]) {
    
                ans[left] = nums[right];
            }else if(left > 0 && nums[left-1] < ans[left-1]){
    
                ans[left] = ans[left-1];
            }else {
    
                int max = Integer.MIN_VALUE;
                for(int i = left; i <= right; i++) {
    
                    max = Math.max(max,nums[i]);
                }  
                ans[left] = max;
            }
            left++;
            right++;
        }
        return ans;
    }


}

Fifth question : The finger of the sword Offer 59 - II. The maximum value of the queue

LeetCode: The finger of the sword Offer 59 - II. The maximum value of the queue

describe :
Please define a queue and implement the function max_value Get the maximum in the queue , Function required max_value、push_back and pop_front Of The average time complexity is O(1).

If the queue is empty ,pop_front and max_value Need to return -1

Their thinking :

1. The idea of this question is to use a queue , Additive elements . Use a double ended queue , Add the maximum value
2. At the time of joining the team , Judge whether the current double ended queue is empty , If it is not empty, compare
   • If you insert value It should be larger than the tail element , Just pop up the tail element , Until it is smaller than the end of the team , Or the team is empty
   • The maximum value of the current queue is always placed in this double ended queue .
3. When out of the team , Return directly if it is empty -1, If it's not empty . Compare the queue head value of the queue and the double ended queue , Have you been , If it's not consistent , It means that the current maximum has not been out of the team , Never mind . At this time, only the first element of the team is used , There is no need to produce a double ended queue header element .
4. When the maximum value is obtained , If the queue is empty, return -1, If it's not empty , Directly return the first element of the double ended queue .

Code implementation :

class MaxQueue {
    
    private Queue<Integer> res;
    private Deque<Integer> tmp;
    public MaxQueue() {
    
        res = new LinkedList<>();
        tmp = new LinkedList<>();
    }
    
    public int max_value() {
    
        if(res.isEmpty()) {
    
            return -1;
        }
        return tmp.peekFirst();
    }
    
    public void push_back(int value) {
    
        res.offer(value);
        while(!tmp.isEmpty() && value > tmp.peekLast()) {
    
            tmp.pollLast();
        }
        tmp.offerLast(value);
    }
    
    public int pop_front() {
    
        if(res.isEmpty()) {
    
            return -1;
        }
        int val = res.poll();
        if(val == tmp.peekFirst()){
    
            tmp.pollFirst();
        }
        return val;
    }
}

/** * Your MaxQueue object will be instantiated and called as such: * MaxQueue obj = new MaxQueue(); * int param_1 = obj.max_value(); * obj.push_back(value); * int param_3 = obj.pop_front(); */

Sixth question : The finger of the sword Offer 60. n The number of dice

LeetCode: The finger of the sword Offer 60. n The number of dice

describe :
hold n A dice on the ground , The sum of the points on the up side of all dice is s. Input n, Print out s The probability that all possible values of the .

You need to return the answer with an array of floating-point numbers , Among them the first i The elements represent this n The number of points that a die can roll i The probability of the smaller one .

Their thinking :

1. Dynamic programming is used here
2. Dynamic planning ideas :

• state F(i,j): Said yes i A sieve , Points for j Probability
• State transition equation : F(i,j) = dp[i-1][j-k] * 1/6 (j>k)
• The initial state : F(1,j) = 1/6;
• Return results : F

Code implementation :

class Solution {
    
    public double[] dicesProbability(int n) {
    
    	//  points j [1~6*n]
        double[][] dp = new double[n+1][6*n+1];
        //  The initial state 
        for (int i = 1; i <= 6; i++) {
    
            dp[1][i] = 1/6.0;
        }
        for(int i = 2; i <= n; i++) {
    
            // j The scope of the [i,6i]
            for(int j = i; j <= 6*i; j++) {
    
                for(int k = 1; k <= 6; k++) {
    
                    //  When  j > k  When , Only the number of points can be found, and it is impossible to throw them out 0 -1
                    if(j>k) {
    
                        dp[i][j] += dp[i-1][j-k] * 1 / 6.0;
                    }else{
    
                    	//  Just here  j<=k,  The latter situation will only be smaller ,  Just skip 
                        break;
                    }
                }
            }
        }
        // n A sieve , The result is [n,6n],  Altogether , (6n-n)+1 = 5n+1 Number 
        double[] res = new double[5*n+1];
        for(int i = 0; i < 5 * n + 1; i++) {
    
            res[i] = dp[n][n+i];
        }
        return res;
    }
}

Question seven : The finger of the sword Offer 61. Shunzi in playing cards

LeetCode: The finger of the sword Offer 61. Shunzi in playing cards

describe :
Draw at random from several sets of playing cards 5 card , Judge whether it's a down son , Is this 5 Are cards continuous .2～10 For the number itself ,A by 1,J by 11,Q by 12,K by 13, And big 、 Wang Wei 0 , It can be seen as any number .A Can't be regarded as 14.

Their thinking :

1. The meaning of this question is , 0 It can be used as other cards
2. Here is the first sorting .
3. Then record zero The number of times
4. zero After recording , Check whether the difference between the two arrays is 1,
   • If the difference is 1, continue
   • If two are equal , Go straight back to false;
   • If there are other situations , Get the difference in the number of cards , Calculation formula right - left -1, According to this data , see zero Is it enough , If zero<0 Go straight back to false.
5. End of traversal , return true

Code implementation :

class Solution {
    
    public boolean isStraight(int[] nums) {
    
        Arrays.sort(nums);
        int zero = 0;
        int index = 0;
        for(int i = 0; i < nums.length - 1; i++) {
    
            if (nums[i] == 0) {
    
                zero++;
            }else{
     
                if(nums[i] == nums[i+1]) {
    
                    return false;
                }
                if(nums[i+1] - nums[i] != 1){
    
                    zero -= nums[i+1] - nums[i] - 1;
                    if(zero < 0) return false;
                }
            }
        }
        return true;
    }
}