T1: 2108. 找出数组中的第一个回文字符串
思路
从头枚举,直至找到第一个回文字符串
Code
class Solution {
public:
bool test(string a){
string s=a;
reverse(a.begin(),a.end()); //将原字符串反转再进行比较
return a==s;
}
string firstPalindrome(vector<string>& words) {
bool flag=false;
for(auto& i:words){
if(test(i)){
return i;
}
}
return "";
}
};复杂度分析
时间复杂度：O(∑i*ni)，其中 ni为 words 数组中第 i 个字符串的长度。即为遍历寻找第一个回文字符串的时间复杂度。
空间复杂度：O(1)
T2: 2109. 向字符串添加空格
思路
遍历字符串时不断累加,在遍历到字符串指定位置时加上空格
Code
class Solution {
public:
string addSpaces(string s, vector<int>& a) {
string ret;
int n = s.size();
vector<int> c(n);
for(int i : a) c[i] = 1;
for(int i = 0; i < s.size(); ++i) {
if(c[i]) ret += " ";
ret += s[i];
}
return ret;
}
};复杂度分析
- 时间复杂度：O(n + m)，其中 n 是字符串 s 的长度，m 是数组 spaces 的长度。
- 空间复杂度：O(1) 或 O(n + m)，取决于使用的语言中字符串是否可以修改。
T3: 2110. 股票平滑下跌阶段的数目
思路
用双指针来计算连续区间，把所有满足区间的长度加起来（可以用sum(1, n) = n*(n+1)/2）
Code
class Solution {
public:
long long zong(int len){
long long le=len;
long long num=(le-1)*le/2;
return num;
}
long long getDescentPeriods(vector<int>& prices) {
int n=prices.size();
long long num=n;
deque<int>ha;
for(int r=0;r<n;++r){
if(ha.empty()){
ha.push_back(prices[r]);
continue;
}
if(ha.size()>0&&prices[r]==ha.back()-1){
ha.push_back(prices[r]);
}
else{
if(ha.size()>1)
num+=zong(ha.size());
ha.clear();
ha.push_back(prices[r]);
}
}
if(ha.size()>=2)
num+=zong(ha.size());
return num;
}
};复杂度分析
- 时间复杂度：O(n)，其中 n 为 prices 的长度。即为计算每个元素结尾的平滑下降阶段数目并求和的时间复杂度。
- 空间复杂度：O(1)。
T4: 2111. 使数组 K 递增的最少操作次数
思路
通过观察题目可知: arr[i]只受arr[i-k], arr[i-2k], arr[i-3k], …的影响，所以我们可以分组求出每个组的最长不下降子序列长度再累加，最后用总长度减去累加和即为需要改变的次数
Code
class Solution {
public:
template<typename T>
int lis(vector<T> a) {
vector<T> dp;
for(auto& x : a) {
auto it = upper_bound(dp.begin(), dp.end(), x);
//因为只要求最长不下降子序列，所以用upper求得大于的那个，然后更改
// 最长递增子序列用lower
if(it == dp.end()) dp.push_back(x); //如果找不打比x大的元素，那么将其加进去
else *it = x; //找到的话，对其进行修改
}
return dp.size();
}
int kIncreasing(vector<int>& a, int k) {
int n = a.size();
int ans = 0;
for(int i = 0; i < k; ++i) {
vector<int> b;
for(int j = i; j < n; j += k) {
b.push_back(a[j]);
}
ans += lis(b);
}
return n - ans;
}
};复杂度分析
- 时间复杂度：O(nlog kn)。每个序列的长度为 O(kn)，寻找其最长递增子序列需要的时间为 O( knlogkn)，而一共有 k 个序列，因此总时间复杂度为 O(nlog kn)。
- 空间复杂度：O(kn)，即为寻找单个序列的最长递增子序列时，数组 f 需要的空间。
额外拓展
本题采用的方法是分组然后求最长不下降子序列。
如果题目里的K递增的定义被改成严格递增，是不能用分组然后求最长递增子序列来做的，因为题目另一个限制条件是数组里必须存正整数，那么类似2,1,2,3,4这样的序列是不能改成0,1,2,3,4的，这种情况下难道只能暴力求解了吗？
答：把每个数减去其下标，然后对所有正整数求最长非降子序列。
举个例子，现在每 k 个数选一个数，假设选出来的数组是 [3,2,4,5,5,6,6]。
每个数减去其下标后就是 [ 3,1,2,2,1,1,0]。
对这个数组中的正整数求最长非降子序列，那就是 [1,1,1] 了，对应原始数组的[ *, 2 , * , * , 5 , 6 , * ]，这三个数字保留，其余数字修改完成后就是 [ 1,2,3,4,5,6,7]，符合严格递增且均为正整数的要求。
注：上述减去下标的技巧，主要是为了能让保留的数字之间可以容纳严格递增的数字。否则，若直接按照最长严格递增子序列的求法，会得到例如[ * , 2 , 4 , 5 , * , 6 , *] 这样的错误结果。
个人总结
本周题目比较简单，但第二题被卡了，本想暴力直接插入空格，却tle一发，浪费了很久。最后一题没有仔细审题，以致于一直卡在不知道该如何分组在lis。总结就是，手速还不够快，遇到简单题第一时间没能写出解法，平时练习还有欠缺，还有下次审题要仔细，与其罚坐不如好好审题！
