蓝湖的题，不错！
蓝湖联名力扣周赛出的题目还不错，前三题比较温暖，最后一题带一点套路，总的来说都不难
涉及知识点：模拟，字符串，动态规划，最长上升子序列，二分优化
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;
}
};
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2021-12-20，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录