Day 15 of leetcode

1 II. The maximum value of the queue

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 The average time complexity of is O(1). If the queue is empty ,pop_front and max_value Need to return -1

analysis ：

Create two queues , One Q It is used for the normal operation of entering and leaving the team , A double ended queue MaxQ It is used to maintain the maximum value in the current queue . Insert every element value when , from MaxQ At the end of the queue, the current elements are taken out in turn value Small elements , Until you come across an element larger than the current one value’ that will do .

class MaxQueue {
    
        Queue<Integer> Q;
        Deque<Integer> MaxQ;

        public MaxQueue() {
    
            Q = new LinkedList<>();
            MaxQ = new LinkedList<>();
        }

        public int max_value() {
    
            if (MaxQ.isEmpty()) return -1;
            return MaxQ.peekFirst();
        }

        public void push_back(int value) {
    
            while (!MaxQ.isEmpty() && MaxQ.peekLast() < value){
    
                MaxQ.pollLast();
            }
            MaxQ.offerLast(value);
            Q.offer(value);
        }

        public int pop_front() {
    
            if (Q.isEmpty()) return -1;
            int res = Q.poll();
            if (res == MaxQ.peekFirst()) MaxQ.pollFirst();
            return res;
        }
    }

2 Left rotation string

The left rotation operation of string is to transfer several characters in front of string to the end of string . Please define a function to implement the left rotation operation of string .
such as , Input string "abcdefg" And number 2, This function will return the result of rotating two bits to the left "cdefgab".

analysis ：

utilize substring() Function to implement .

class Solution {
    
    public String reverseLeftWords(String s, int n) {
    
        if (n > s.length())
            return null;
        return s.substring(n) + s.substring(0, n);
    }
}

3 Flip word order

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”.

analysis ：

Double pointer . Start traversing the string in reverse order , A pointer records the starting position , A pointer records the position when a space is encountered , Intercept the content between the two pointers and add it to res In the middle , Then start recording after traversing to the next position that is not a space .

class Solution:
    def reverseWords(self, s: str) -> str:
        s = s.strip() #  Delete leading and trailing spaces 
        i = j = len(s) - 1
        res = []
        while i >= 0:
            while i >= 0 and s[i] != ' ': i -= 1 #  Search for the first space 
            res.append(s[i + 1: j + 1]) #  Add words 
            while s[i] == ' ': i -= 1 #  Skip spaces between words 
            j = i # j  The last character pointing to the next word 
        return ' '.join(res) #  Splice and return 

class Solution {
    
    public String reverseWords(String s) {
    
        s = s.trim(); //  Delete leading and trailing spaces 
        int j = s.length() - 1, i = j;
        StringBuilder res = new StringBuilder();
        while(i >= 0) {
    
            while(i >= 0 && s.charAt(i) != ' ') i--; //  Search for the first space 
            res.append(s.substring(i + 1, j + 1) + " "); //  Add words 
            while(i >= 0 && s.charAt(i) == ' ') i--; //  Skip spaces between words 
            j = i; // j  The last character pointing to the next word 
        }
        return res.toString().trim(); //  Convert to a string and return 
    }
}

4 Play chips

Yes n A chip . The first i Where are the chips position[i] . We need to move all the chips to the same position . In one step , We can put i The position of chips is from position[i] Change for :

• position[i] + 2 or position[i] - 2 , here cost = 0
• position[i] + 1 or position[i] - 1 , here cost = 1

Returns the minimum cost of moving all chips to the same location .

analysis ：

It can be seen from the meaning of the question , When moving chips from odd position to odd position and from even position to even position , The price is 0. So we just need to see whether the subscript of the last digit is odd or even , If it is an odd number, the minimum cost is the number of all even subscripts ; If it is even, the minimum cost is the number of all odd subscripts .

class Solution {
    
    public int minCostToMoveChips(int[] position) {
    
        int odd = 0, even = 0;
        for (int i = 0; i < position.length; i++) {
    
            if (position[i] % 2 == 0) {
    
                even++;
            } else {
    
                odd++;
            }
        }
        return Math.min(odd, even);
    }
}