第289场周赛 6070. 计算字符串的数字和
题目描述
给你一个由若干数字（0-9）组成的字符串s，和一个整数k。 如果 s 的长度大于 k ，则可以执行一轮操作。在一轮操作中，需要完成以下工作： 将 s 拆分 成长度为 k 的若干 连续数字组 ，使得前 k 个字符都分在第一组，接下来的 k 个字符都分在第二组，依此类推。注意，最后一个数字组的长度可以小于 k 。 用表示每个数字组中所有数字之和的字符串来 替换 对应的数字组。例如，”346” 会替换为 “13” ，因为 3 + 4 + 6 = 13 。 合并 所有组以形成一个新字符串。如果新字符串的长度大于 k 则重复第一步。 返回在完成所有轮操作后的 s 。
解题思路
- 首先需要把这一堆数字每k个为一组分开，那么一共就有(n + k - 1) / k组。
- 之后将这k个数直接全部加起来。这k个数也需要用一次遍历。从i * k开始，到i * k + k结束。但我们需要注意最后一组不够k个的情况，因此需要将最后一组特殊化处理，也即在最后一组时，将字符串长度和i * k + k取小，这样就可以了。
- 由于字符串可以直接用等号赋值，所以直接将计算结果赋给s即可。
- 什么时候结束呢？字符串长度小于等于k时结束。因此大循环使用while语句即可。
代码如下
class Solution {
public:
string digitSum(string s, int k) {
//int n = s.size(); //这样会超时..
while(s.size() > k) {
int n = s.size(); //这个放里面才能通过，为啥？？
string res;
for(int i = 0; i < (n + k - 1) / k; i++) {
int sum = 0;
for(int j = i * k; j < min(n, i * k + k); j++) {
sum += s[j] - '0';
}
res += to_string(sum);
}
s = res;
}
return s;
}
};
由于进行了两次遍历，因此算法的时间复杂度为O(n^2)；由于使用了额外的字符串空间res，因此算法的空间复杂度为O(n)。
第 77 场力扣夜喵双周赛 6051. 统计是给定字符串前缀的字符串数目
代码如下：
int countPrefixes(vector<string>& words, string s) {
int res = 0;
for(auto &x : words) { //遍历words中的子串。。
if(s.find(x) == 0) ++res; //如果s中找到了x，那么就把结果数目+1
}
return res;
}
第 77 场力扣夜喵双周赛 6052. 最小平均差
题目描述：
给你一个下标从 0 开始长度为 n 的整数数组 nums 。 下标 i 处的平均差指的是 nums 中 前 i + 1 个元素平均值和后 n - i - 1 个元素平均值的 绝对差 。两个平均值都需要 向下取整 到最近的整数。 请你返回产生 最小平均差 的下标。如果有多个下标最小平均差相等，请你返回 最小 的一个下标。 注意： 两个数的 绝对差 是两者差的绝对值。 n 个元素的平均值是 n 个元素之 和 除以（整数除法） n 。 0 个元素的平均值视为 0 。
代码如下：
class Solution {
public:
typedef long long ll;
int minimumAverageDifference(vector<int>& nums) {
ll n = nums.size(), ans = LONG_MAX, index = -1; //注意越界问题，索性全部定义为long long
vector<ll> presum(n + 1); //开辟一个大小为 n + 1的数组空间，用于存放分子(i个数之和)
for (int i = 0; i < n; i++) {
presum[i + 1] = presum[i] + (ll)nums[i];
}
for (int i = 1; i <= n; i++) {
ll left = presum[i] / i, right = 0; //前i个数的平均值
if (i < n) right = (presum[n] - presum[i]) / (n - i);//后n-i-1个元素的平均值
if (ans > abs(left - right)) ans = abs(left - right), index = i - 1;//如果左-右的绝对值大于ans，就覆盖。与此同时下标-1
}
return index;
}
};
第293场周赛 5234. 计算字符串的数字和
解题思路
这题真不难！是判断异位词经典题目的延伸。
- 先写一个判断异位词的函数
- 如果前后两个单词是异位词，则push后一个元素入vector
代码如下：
class Solution {
public:
//该函数用于判断前后两个单词是否为字母异位词
bool isAnagram(string s, string t) {
unordered_map<char, int> pairs1;
if(s.length() != t.length()) return false;
for(int i = 0; i < s.length(); i++) {
pairs1[s[i]]++;
}
for(int i = 0; i < t.length(); i++) {
pairs1[t[i]]--;
}
for(int i = 0; i < t.length(); i++) {
if(pairs1[s[i]] != 0) {
return false;
}
}
return true;
}
vector<string> removeAnagrams(vector<string>& words) {
//先遍历这个vector数组，每个i就是一个单词
vector<string> res;
int n = words.size();
res.push_back(words[0]);//先把第一个单词push进去
for (int i = 1; i < n; ++i) {
if (isAnagram(words[i - 1], words[i])) continue;//如果前后两个单词是异位词，则push后一个元素入vector
res.push_back(words[i]);
}
return res;
}
};
第294场周赛
Historical moment!终于做出了周赛第一题，第二题也基本知道怎么做了！
6074. 字母在字符串中的百分比
- 用哈希表记录该字母出现的频次，之后用该频次除以字符串长度即可。
6075. 装满石头的背包的最大数量
- new一个数组，存放每个背包中缺少的石头数量并将其排序；用已有的石头总数依次减去该vector中的元素，减一次就将结果++，直到已有石头用完结束循环。
