社区首页 >专栏 >蓝湖的题，不错！

蓝湖的题，不错！

ACM算法日常

发布于 2021-12-20 10:25:56

79800

代码可运行

文章被收录于专栏：ACM算法日常ACM算法日常

运行总次数：0

代码可运行

蓝湖联名力扣周赛出的题目还不错，前三题比较温暖，最后一题带一点套路，总的来说都不难

涉及知识点：模拟，字符串，动态规划，最长上升子序列，二分优化

5956. 找出数组中的第一个回文字符串

给定一个字典 w ，找到第一个回文字符串，如果没有输出空字符串

题解

模拟

// cpp
class Solution {
public:
    bool check(const string& s) {
        int i = 0, j = s.length() - 1;
        while (i <= j) {
            if (s[i++] != s[j--]) return 0;
        }
        return 1;
    }
    string firstPalindrome(vector<string>& w) {
        for (auto& i: w) if (check(i)) return i;
        return "";
    }
};

5957. 向字符串添加空格

给定一个字符串 s 和一个正整数数组 a ，按照 a 中的值给 s 中的对应位置添加空格

题解

两个指针扫描

// cpp
class Solution {
public:
    string addSpaces(string s, vector<int>& spaces) {
        int j = 0;
        string ans;
        for (int i = 0; i < s.length(); ++i) {
            if (j < spaces.size() && i == spaces[j]) ans += ' ', ++j;
            ans += s[i];
        }
        return ans;
    }
};

5958. 股票平滑下跌阶段的数目

给定一个正整数数组 a 表示每天的股价，如果有一段区间依次递减 1 ，我们称之为平滑下跌，计算 a 中平滑下跌的区间个数

题解

简单 dp，定义 dp[i] 表示以第 i 天结尾，平滑下跌的天数，那么

若 a[i] + 1 = a[i - 1] ，则dp[i] = dp[i - 1] + 1
否则，dp[i] = 1

根据状态转移方程计算，最后累加 dp 数组即可

// cpp
class Solution {
public:
    long long getDescentPeriods(vector<int>& p) {
        int n = p.size();
        typedef long long LL;
        vector<LL> dp(n);
        dp[0] = 1;
        for (int i = 1; i < n; ++i) {
            if (p[i - 1] - 1 == p[i]) dp[i] = dp[i - 1] + 1;
            else dp[i] = 1;
        }
        LL ans = 0;
        for (int i = 0; i < n; ++i) ans += dp[i];
        return ans;
    }
};

5959. 使数组 K 递增的最少操作次数

给定一个正整数数组 a 和一个正整数 k ，如果对于每一个位置 i 都有 a[i - k] \leq a[i] ，那么我们称之为 k 递增现在你可以花费一个操作数，将 i 位置的元素 a]i] 变为任意正整数，请计算让 a 变得 k 递增的最小操作数数据规定，数组 a 的长度 n 满足1\leq n\leq 10^5

题解

一个简单的发现，变换后的数组满足a[i] \leq a[i + k]\leq a[i + 2k]\leq ... 因此我们把原数组可以拆成 k 个长为 \lfloor\frac{n}{k}\rfloor 的子数组

考虑子问题，给定一个长度为 m 的正整数数组 b ，可以任意变换元素的值，最少花费多少操作数使得 b 单调不减？

只需要计算最长不降子序列的长度 l ，那么答案即为 m - l ，具体可以参考 dilworth 定理我们对每个子数组都做这样的计算，最后求和即可，时间复杂度为\mathcal{O}(n\log\lfloor\frac{n}{k}\rfloor)

// cpp
class Solution {
public:
    int kIncreasing(vector<int>& arr, int k) {
        int n = arr.size(), ans = 0;
        for (int i = 0; i < k; ++i) {
            vector<int> dp;
            int cnt = 0;
            for (int j = i; j < n; j += k) {
                auto it = upper_bound(dp.begin(), dp.end(), arr[j]);
                if (it == dp.end()) dp.push_back(arr[j]);
                else *it = arr[j];
                ++cnt;
            }
            ans += cnt - dp.size();
        }
        return ans;
    }
};