[数据结构与算法]3.31 LeetCode 第 253 场周赛

1961. 检查字符串是否为数组前缀

• 题目大意
  给你一个字符串 s 和一个字符串数组 words ，请你判断 s 是否为 words 的前缀字符串 。
• 思路
  就是挨着一个个判断，但是要注意边界条件。
• code

class Solution {
public:
    bool isPrefixString(string s, vector<string>& words) {
        int n = s.length();
        int m = words.size();
        bool f=true;
        int x=0;
        for(int j=0;j<m;j++)
        {
            if(x==n) return f;
            x+=words[j].size();
            if(x>n) return false;
            for(int i=x-words[j].size(),k=0;i<x&&words[j].size();i++,k++)
            {
                if(s[i]!=words[j][k]) f=false;
                //cout<<words[j][k]<<' '<<s[i]<<endl;
            }      
        }
        if(n>x) f=false;
        return f;
        
    }
};

1962. 移除石子使总数最小

• 题目大意
  给定一堆石子，每堆石子个数为$piles[i]$，每次可以选择一堆石子将其一半取出，剩下的放回原来的位置。共有k次这样的操作，问最后剩余的石子总数最小是多少？
• 思路
  优先队列（堆）！
  要注意: 关于下取整的写法：y = (x&1)? (x+1)/2 : x/2。小小技巧很多地方都会用到的。
• code

class Solution {
public:
    int minStoneSum(vector<int>& piles, int k) {
        int n = piles.size();
        priority_queue<int> q;
        for(int i=0;i<n;i++) q.push(piles[i]);
        int ans=0;
        while(k--)
        {
            int x=q.top();
            q.pop();
            if(x==0) return 0;
            int y = (x&1)? (x+1)/2 : x/2;
            q.push(y);
        }
        while(!q.empty()) ans+=q.top(),q.pop();
        return ans;
    }
};

1963. 使字符串平衡的最小交换次数

• 题目大意
  给定长度为n（n为偶数）的 $[$ 和 $]$ 组成的序列。其中保证 $[$ 和 $]$ 分别出现$n/2$次。问要是括号完全匹配最少要交换多少次。
• 思路
  可以先把匹配的对数找出来。然后剩下没有匹配的括号对数为$x$，那么最少要交换多次呢？
  显然是$ceil(x/2)$。因为两个不匹配的对，可以进行一次交换使得两者都匹配。
• code

class Solution {
public:
    int minSwaps(string s) {
        int n = s.length();
        int x=0,y=0,ans=0;
        for(int i=0;i<n;i++)
        {
            if(s[i]=='[')
            {
                x++;
            }
            else if(s[i]==']')
            {
                if(x>0) x--;
                else y++;
            }
        }
        return (x+1)/2;
    }
};

1964. 找出到每个位置为止最长的有效障碍赛跑路线

• 题目大意
  在一个序列中，求每一个位置的最长不降子序列的长度。
• 思路

1. 简单的有$O(n^2)$的DP做法，$f[i]=f[j]+1,nums[j]<=nums[i],0<=j<i$，但是对于这道题复杂度是不够的。
2. 采用$O(nlogn)$的做法：贪心+二分：
   维护一个$f[len]$数组，表示长度为$len$的最长上升子序列最末的一个元素是多少。
   从前往后遍历$nums$每一个元素：
   若 $nums[i]$ >= 当前$len$（目前最长的不降子序列）的最后一个元素f$[len]$：要更新$len=len+1$，$f[len]=nums[i]$。
   否则：找到第一个末端元素大于当前元素$nums[i]$的位置，并用$nums[i]$替换这个位置的元素。贪心的思想：显然一个同样长度的不降子序列末端元素越小越好，而且这里寻找位置时采用二分查找可以做到$log(n)$。
3. 补充一个关于 $lower\_bond$ 和 $upper\_bond$ 的用法：
   注意：数组必须是排好序的数组。

lower_bond(begin, end, val)
在begin和end中的前闭后开区间，进行二分查找。返回从begin开始的第一个大于或等于val的元素的地址。如果所有元素都小于val，则返回end的地址。

upper_bond(begin, end, val)
在begin和end中的前闭后开区间，进行二分查找。返回从begin开始的第一个大于val的元素的地址。如果所有元素都小于val，则返回end的地址。

• code

class Solution {
public:
    vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
        #define N 10000005
        int n = obstacles.size();
        int f[N]={0}, len = 0;
        vector<int> ans(n,0); 
        for(int i=0;i<n;i++)
        {
            if(obstacles[i]>=f[len]) 
            {
                f[++len]=obstacles[i];
                ans[i]=len;
            }
            else
            {
                int j = upper_bound(f, f+len, obstacles[i]) - f;
                ans[i]=j;
                f[j]=obstacles[i];
            } 
        }                           
        for(int i=0;i<=len;i++) cout<<f[i]<<endl;
        cout<<endl;
        return ans;
    }
};