Leetcode 第272场周赛题解(C++版)

PS:最近的周赛越来越简单了

Problem A -

题意 给你一个字符串数组，找出并返回数组中的 第一个回文字符串 思路 按题意模拟即可。 代码

class Solution {
public:
    bool jud(string s){
        string str=s;
        reverse(s.begin(),s.end());
        return str==s;
    }
    string firstPalindrome(vector<string>& words) {
        for(auto i:words) if(jud(i)) return i;
        return string("");
    }
};

Problem B -

题意 给你一个字符串,以及一个整数数组spaces，在整数数组指示的每一个位置添加空格。 思路 按题意模拟，如果对于字符串的每一个位置都找是不是要添加，那么复杂度达到 O ( m n ) O(mn) O(mn)，肯定会超时。注意到我们从前往后检查spaces数组且其是严格递增的，我们考虑设定一个变量指示当前走到了spaces的哪一位，由此可 O ( n ) O(n) O(n)地解决该问题。 代码

class Solution {
public:
    long long subArrayRanges(vector<int>& nums) {
        int n=nums.size();
        long long dp[2][n][n],ans=0;
        for(int i=0;i<n;i++) dp[0][i][i]=dp[1][i][i]=nums[i];
        for(int i=1;i<n;i++){
            for(int j=1;j<=i;j++){
                dp[0][i][i-j]=min(dp[0][i-1][i-j],dp[0][i][i-j+1]);
                dp[1][i][i-j]=max(dp[1][i-1][i-j],dp[1][i][i-j+1]);
                ans+=dp[1][i][i-j]-dp[0][i][i-j];
            }
        }
        return ans;
    }
};

Problem C -

题意 给你一个整数数组，找出其所有子数组（连续）中有多少个公差为-1的等差数列。 思路 判断每一位和前一位是否符合”平滑下跌“，如是，记录长度+1，否则重新置1，这样每一位的len记录的是“以当前位置结束的平滑下跌阶段的数目”，每次累加即可，三行解决。 代码

class Solution {
public:
    long long getDescentPeriods(vector<int>& prices) {
        long long n=prices.size(),ans=1,len=1;
        for(int i=1;i<n;i++) len=(prices[i]==prices[i-1]-1)?len+1:1,ans+=len;
        return ans;
    }
};

Problem D -

题意 给定一个序列 { a 0 , a 1 , . . . , a n } {a_0,a_1,...,a_n} { a0,a1,...,an}和一个k，如果对于每个满足$ k le i le n-1$ 的下标 i ，都有 a r r [ i − k ] ≤ a r r [ i ] arr[i-k] le arr[i] arr[i−k]≤arr[i] ，那么我们称 arr 是 K 递增 的。问最少修改几个数能使序列满足"K 递增"。 思路 考虑以原数组的 a i ( 0 ≤ i ≤ k ) a_i(0 le i le k) ai(0≤i≤k)为首项，分成k组，例如：

a = [4, 1, 5, 2, 6, 2] ， k = 2 可分为： { a 0 , a 2 , a 4 } { a 1 , a 3 , a 5 } {a_0,a_2,a_4}\ {a_1,a_3,a_5} { a0,a2,a4}{ a1,a3,a5}

这样问题转化为将某一个数组变成非递减序列的最少操作次数，对于这个问题显然想到经典LIS问题，其答案就是数组长度减去最长非递减子序列的长度。对于每个子问题答案累加，即得到本题答案。复杂度为 O ( k m l o g ( m ) ) , m = ( n / k ) O(k mlog(m)),m=(n/k) O(kmlog(m)),m=(n/k) 代码

#define INF 0x3f3f3f3f
class Solution {
public:
    int LIS(vector<int>& a){
        int n=a.size(),pos=1;
        int dp[n+1];
        fill(dp,dp+n+1,0);
        dp[1]=a[0];
        for(int i=1;i<n;i++){
            if(a[i]>=dp[pos]) dp[++pos]=a[i];
            else dp[upper_bound(dp+1,dp+pos+1,a[i])-dp]=a[i];
        }
        return n-pos;
    }
    int kIncreasing(vector<int>& arr, int k) {
        int n=arr.size(),ans=0;
        if(k>n) return 0;
        for(int i=0;i<k;i++){
            vector<int> tmp;
            for(int j=i;j<n;j+=k) tmp.push_back(arr[j]);
            ans+=LIS(tmp);
        }
        return ans;
    }
};