[数据结构与算法]Leetcode Weekly Contest 253（字符串、贪心、二分）

题目链接： Leetcode Weekly Contest 253

写在前面：

本次周赛做出第一题和第二题。

1、1961. Check If String Is a Prefix of Array

难度：Easy

代码：

class Solution {
    public boolean isPrefixString(String s, String[] words) {
        char[] arr=s.toCharArray();
        StringBuilder sb=new StringBuilder();
        for(String word:words){
            sb.append(word);
            if(sb.length()>=arr.length){
                break;
            }
        }
        if(sb.length()!=arr.length){
            return false;
        }
        int i=0,j=0;
        for( ;i<arr.length;i++,j++){
            if(arr[i]!=sb.charAt(j)){
                return false;
            }
        }
        return true;
    }
}

2、1962. Remove Stones to Minimize the Total

难度：Medium

题目大意：

详见题意。

思路：

贪心 ，每次选择数组中最大的元素来进行操作。

代码

class Solution {
    public int minStoneSum(int[] piles, int k) {
        PriorityQueue<Integer> pq=new PriorityQueue<>((a,b)->b-a);
        for(int n:piles){
            pq.offer(n);
        }
        while(k-->0){
            int n=pq.poll();
            n-=n/2;
            pq.offer(n);
        }
        int res=0;
        while(!pq.isEmpty()){
            res+=pq.poll();
        }
        return res;
    }
}

3、1963. Minimum Number of Swaps to Make the String Balanced

难度：Medium

题目大意：

括号匹配。

思路：

找规律，推导数学公式。参考高赞回答。

代码

class Solution {
    public int minSwaps(String s) {
        char[] arr=s.toCharArray();
        int misMatch=0;
        for(char c:arr){
            if(c=='['){
                misMatch++;
            }
            else{
                if(misMatch>0){
                    misMatch--;
                }
            }
        }
        return (misMatch+1)/2;
    }
}

4、1964. Find the Longest Valid Obstacle Course at Each Position

难度：Hard

题目大意：

详见题目。

思路

动态规划会超时，需要用二分+贪心，这一题与Leetcode 300. Longest Increasing Subsequence类似，可以参考Leetcode 300 官方题解。本题还参考了高赞回答。

代码

class Solution {
    public int[] longestObstacleCourseAtEachPosition(int[] nums) {
        int n=nums.length;
        int[] d=new int[n+1];
        //d[i]表示长度为i的最长递增子序列的最后一个元素的最小值
        int len=1;//最长递增子序列的长度
        d[1]=nums[0];
        int[] res=new int[n];
        res[0]=len;
        for(int i=1;i<n;i++){
            if(nums[i]>=d[len]){
                len++;
                d[len]=nums[i];
                res[i]=len;
            }
            else{
                int l=0,r=len;
                while(l<r){
                    //寻找小于等于nums[i]的元素的最大下标
                    int mid=l+(r-l+1)/2;
                    if(d[mid]>nums[i]){
                        r=mid-1;
                    }
                    else{
                        l=mid;
                    }
                }
                d[l+1]=nums[i];
                res[i]=l+1;
            }
        }
        return res;
    }
}