This week's competition is relatively simple. I wrote three questions in an hour. The last question, I forgot how to write the longest common subsequence of greedy plus two points. dp's card is lost, and I supplemented it after it.

5838. Check whether the string is an array prefix

class Solution {
    public boolean isPrefixString(String s, String[] words) {
        StringBuilder sb = new StringBuilder();
        for(String x:words){
            sb.append(x);
            if(sb.toString().equals(s)){
                return true;
            }
        }
        return false;
    }
}

5839. Remove stones to minimize the total

Give you an integer array of piles. The array subscript starts from 0, where piles[i] represents the number of stones in the ith pile of stones. Another integer k is given to you. Please perform the following operations exactly k times:

Select any pile of stones [i] and remove floor (piles[i] / 2 stones from it.
Note: you can perform this operation on the same pile of stones multiple times.

Returns the minimum total number of stones left after k operations.

floor(x) is the largest integer less than or equal to X. (that is, round down x).

Example 1:

Input: piles = [5,4,9], k = 2
Output: 12
Explanation: possible execution scenarios are as follows:

• When the removal operation is performed on the second pile of stones, the stone distribution becomes [5,4,5].
• When the removal operation is performed on the 0th pile of stones, the distribution of stones becomes [3,4,5].
  The total number of stones left is 12.
  Example 2:

Input: piles = [4,3,6,7], k = 3
Output: 12
Explanation: possible execution scenarios are as follows:

• When the second pile of stones is removed, the distribution of stones becomes [4,3,3,7].
• When the third pile of stones is removed, the distribution of stones becomes [4,3,3,4].
• When the removal operation is performed on the 0 th pile of stones, the distribution of stones becomes [2,3,3,4].
  The total number of stones left is 12.

Tips:

1 <= piles.length <= 105
1 <= piles[i] <= 104
1 <= k <= 105

class Solution {
    public int minStoneSum(int[] piles, int k) {
         PriorityQueue<Integer> queue = new PriorityQueue<Integer>(((o1, o2) -> {
            return o2 - o1;
        }));
        for(int x:piles){
            queue.offer(x);
        }
        while(k-- != 0){
            int x = queue.poll();

            queue.offer((int)Math.ceil(x/2.0));

        }
        int res = 0;
        for(int x: queue){ 
            res += x;
        }
        return res;
    }
}

5840. Minimum number of swaps to balance strings

class Solution {
    public int minSwaps(String s) {
         Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            if (!stack.isEmpty() && stack.peek()=='['&& s.charAt(i)==']') {
                stack.pop();
            }else{
                stack.push(s.charAt(i));
            }
        }
        int x = stack.size();
        if(x==0){
           return 0;
        }else{
            if(x>2){
               return x%4 == 0?x/4:x/4+1;
            }else{
                return x/2;
            }
        }


    }
}

5841. Find the longest effective obstacle race route to each position

You're going to build some obstacle routes. Give you an integer array obstacles with subscript starting from 0. The array length is n, where obstacles[i] represents the height of the ith obstacle.

For each subscript i between 0 and n - 1 (including 0 and n - 1), please find out the length of the longest obstacle route that obstacles can form on the premise of meeting the following conditions:

You can select any obstacle with a subscript between 0 and i (including 0 and i).
In this route, the ith obstacle must be included.
You must arrange the obstacles in the order they appear in obstacles.
Except for the first obstacle, the height of each obstacle in the route must be the same as or higher than the previous obstacle.
Returns an answer array ans of length n, where ans[i] is the length of the longest obstacle race route corresponding to the subscript I described above.

Example 1:

Input: obstacles = [1,2,3,2]
Output: [1,2,3,3]
Explanation: the longest effective obstacle route at each location is:

• i = 0: [1], [1] length is 1
• i = 1: [1,2], [1,2] length is 2
• i = 2: [1,2,3], [1,2,3] length is 3
• i = 3: [1,2,3,2], [1,2,2] length is 3
  Example 2:

Input: obstacles = [2,2,1]
Output: [1,2,1]
Explanation: the longest effective obstacle route at each location is:

• i = 0: [2], [2] length is 1
• i = 1: [2,2], [2,2] length is 2
• i = 2: [2,2,1], [1] length is 1
  Example 3:

Input: obstacles = [3,1,5,6,4,2]
Output: [1,1,2,3,2,2]
Explanation: the longest effective obstacle route at each location is:

• i = 0: [3], [3] length is 1
• i = 1: [3,1], [1] length is 1
• i = 2: [3,1,5], [3,5] length is 2, [1,5] is also an effective obstacle race route
• i = 3: [3,1,5,6], [3,5,6] length is 3, [1,5,6] is also an effective obstacle race route
• i = 4: [3,1,5,6,4], [3,4] length is 2, [1,4] is also an effective obstacle race route
• i = 5: [3,1,5,6,4,2], [1,2] length is 2

Tips:

n == obstacles.length
1 <= n <= 105
1 <= obstacles[i] <= 107

class Solution {
    public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
        int[] f = new int[obstacles.length];
        int[] ret = new int[obstacles.length];
        int cnt = 0;
        int m = obstacles.length;
        for (int i = 0; i < m; ++i) {
            int l = 0, r = cnt;
            Record the minimum value at the end of each length
            int num = obstacles[i];
            //Find the minimum value greater than num and use two points
            while(l < r) {
                int mid = (l+r)>>1;
                if(num < f[mid]) r = mid;
                else l = mid + 1;
            }
            f[r] = num;
            // //r+1 in the array is the longest subsequence length corresponding to each position
            ret[i] = r+1;
            if(r == cnt) ++cnt;
        }
        return ret;
    
    }
}