蓝湖的题，不错！

ACM算法日常

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

80800

代码可运行

文章被收录于专栏：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;
    }
};