通知：代码随想录算法训练营 46期在下周三（9月11日）开营，目前可以报名，提前拉群坐等开营。
上周四（8月29日 ）晚上卡码网举办了三十二期周赛（阿里云23年笔试真题）。
阿里云这次算法题，堪称贪心大杂烩，都是贪心题。
23年各大厂笔试题，大家可以在卡码网（https://kamacoder.com/contest.php）去练习：
题目的评论区有各个语言的版本，也有很多录友分享的解题思路，都很不错。
以下为阿里云23年笔试算法题，解题报告：（其他语言版本，可以看题目链接评论区）
优秀数组
题目链接：https://kamacoder.com/problempage.php?pid=1241
解题思路
1、初始分析
给定一个排列 p，我们首先构建一个pos数组，使得pos[i]表示i在排列p中的位置。我们需要判断数组 a是否是一个优秀数组，即pos[a[i]] < pos[a[i+1]] <= pos[a[i]] + d对于所有i都成立。我们的目标是通过最少的相邻元素交换，使得数组 a不再是一个优秀数组。
2、思路
要使数组 a不再是优秀数组，我们只需要打破条件pos[a[i]] < pos[a[i+1]] <= pos[a[i]] + d中的某一个。一种简单的做法是让 pos[a[i]]和pos[a[i+1]]之间的距离超过d，或者直接让pos[a[i]] >= pos[a[i+1]]。
3、具体方法
只需要考虑 a中相邻元素的顺序，并判断如何交换p中相邻元素使得其顺序被打破。假设我们需要在 p中交换某些元素来实现上述目标，那么最小的交换次数是将a[i]和a[i+1]的位置交换。如果 pos[a[i]] + 1 == pos[a[i+1]]，则需要一步交换。
4、特别情况
还需要考虑，如果通过交换相邻元素无法解决问题的情况。比如 pos[a[i+1]]的位置无法移到pos[a[i]]的前面或超过d。
C++代码如下：
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int main() {
int n, m, d;
cin >> n >> m >> d;
vector<int> p(n + 1);
vector<int> pos(n + 1);
// 读取排列 p，并构建位置数组 pos
for (int i = 1; i <= n; i++) {
cin >> p[i];
pos[p[i]] = i;
}
vector<int> a(m);
for (int i = 0; i < m; i++) {
cin >> a[i];
}
int min_operations = INT_MAX;
// 遍历数组 a 的相邻元素
for (int i = 0; i < m - 1; i++) {
int current_pos = pos[a[i]];
int next_pos = pos[a[i + 1]];
// 检查 pos[a[i]] < pos[a[i+1]] <= pos[a[i]] + d 是否成立
if (current_pos < next_pos && next_pos <= current_pos + d) {
// 计算需要的最少操作次数
int distance = next_pos - current_pos;
// Case 1: 交换 current_pos 和 next_pos
min_operations = min(min_operations, distance);
// Case 2: 如果 next_pos + d <= n，考虑使 pos[a[i+1]] 超过 pos[a[i]] + d
if (current_pos + d + 1 <= n) {
min_operations = min(min_operations, d + 1 - distance);
}
} else {
min_operations = 0;
}
}
cout << min_operations << endl;
return 0;
}
时间复杂度为 O(m)
升序数组
题目链接：https://kamacoder.com/problempage.php?pid=1241
解题思路
贪心思路
计算相邻元素差值：
对于数组 a，计算每对相邻元素的差值diff[i] = a[i+1] - a[i]。如果 diff[i]为负数，意味着a[i+1]比a[i]小或相等，需要通过操作使a[i+1]变大。确定最小操作次数：
计算所有相邻元素中的最小差值 minDifference，即minDifference = min(diff[i])。如果 minDifference为负数或零，则需要进行-minDifference + 1次操作，使得a[i+1]大于a[i]，从而使数组严格递增。实现细节：
遍历数组的每对相邻元素，找出最小的差值。 根据最小差值，计算出最少的操作次数。
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> arr(n); // 用于存储输入数组
vector<int> differences; // 用于存储相邻元素的差值
for(int i = 0; i < n; i++) {
cin >> arr[i];
if(i > 0) differences.push_back(arr[i] - arr[i - 1]);
}
int minDifference = INT_MAX;
// 寻找最小的差值
for(int diff : differences) {
if(diff < minDifference) {
minDifference = diff;
}
}
// 如果最小差值是负数或零，计算所需的操作次数
int minOperations = max(0, -minDifference + 1);
cout << minOperations << endl;
return 0;
}
最大字典序无重复串
题目链接：https://kamacoder.com/problempage.php?pid=1243
解题思路
贪心思路
为了保证字典序最大，我们优先放置字母 b，然后再放置字母 a。在放置字符时，我们还需注意不能超过连续 k 次相同字符：
如果当前已经连续放置了 k次相同字符，必须切换到另一个字符。每次放置字符后，相应的字符数量减少，同时更新当前字符的连续计数。
实现步骤：
初始化：根据输入的 x,y,k值，检查是否有可能构造出满足条件的字符串。初始化结果字符串的大小，并设置初始计数器。循环放置字符： 优先放置字符 b，如果b的数量已经足够，或者已经放置了k次字符b，则放置字符a。如果已经放置了 k次相同字符，则强制切换到另一个字符。
C++代码如下：
#include<iostream>
#include<string>
using namespace std;
int main() {
int countA, countB, maxRepeat;
cin >> countA >> countB >> maxRepeat;
// 检查是否有可能生成满足条件的字符串
if (countA > (countB + 1) * maxRepeat || countB > (countA + 1) * maxRepeat) {
cout << -1 << endl;
return 0;
}
string result(countA + countB, ' '); // 预先分配字符串大小
int currentA = 0, currentB = 0; // 当前连续 'a' 和 'b' 的计数
int pos = 0; // 当前填充位置
while (countA > 0 || countB > 0) {
// 当可以继续添加 'a' 或 'b' 且没有超过最大连续限制时
if (currentA < maxRepeat && currentB < maxRepeat) {
if (countA <= countB * maxRepeat) {
result[pos++] = 'b';
countB--;
currentB++;
currentA = 0;
} else {
result[pos++] = 'a';
countA--;
currentA++;
currentB = 0;
}
}
// 当当前字符达到最大连续限制时，切换到另一个字符
if (currentA == maxRepeat || currentB == maxRepeat) {
if (result[pos - 1] == 'a') {
result[pos++] = 'b';
countB--;
currentB = 1;
currentA = 0;
} else {
result[pos++] = 'a';
countA--;
currentA = 1;
currentB = 0;
}
}
}
cout << result << endl;
return 0;
}
时间复杂度：O(n)
