⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 BaguTree Pro 知识星球提问。
学习数据结构与算法的关键在于掌握问题背后的算法思维框架，你的思考越抽象，它能覆盖的问题域就越广，理解难度也更复杂。在这个专栏里，小彭与你分享每场 LeetCode 周赛的解题报告，一起体会上分之旅。
本文是 LeetCode 上分之旅系列的第 37 篇文章，往期回顾请移步到文章末尾~
周赛 357
T1. 故障键盘（Easy）
- 标签：模拟、字符串
T2. 判断是否能拆分数组（Medium）
- 标签：思维
T3. 找出最安全路径（Medium）
- 标签：BFS、连通性、分层并查集、极大化极小、二分查找
T4. 子序列最大优雅度（Hard）
- 标签：贪心、排序、堆
T1. 故障键盘（Easy）
https://leetcode.cn/problems/faulty-keyboard/
题解（模拟）
简单模拟题。
- 在遇到
i字符时对已填入字符进行反转，时间复杂度是 O(n^2)； - 使用队列和标记位可以优化时间复杂度，在遇到
i时修改标记位和写入方向，在最后输出时根据标记位输出，避免中间的反转操作。
class Solution {
public:
string finalString(string s) {
vector<char> dst;
for (auto& c : s) {
if (c == 'i') {
reverse(dst.begin(), dst.end());
} else {
dst.push_back(c);
}
}
return string(dst.begin(), dst.end());
}
};
class Solution {
public:
string finalString(string s) {
deque<char> dst;
bool rear = true;
for (auto& c : s) {
if (c == 'i') {
rear = !rear;
} else {
if (rear) {
dst.push_back(c);
} else {
dst.push_front(c);
}
}
}
return rear ? string(dst.begin(), dst.end()) : string(dst.rbegin(), dst.rend());
}
};
复杂度分析：
- 时间复杂度：$O(n)$ 线性遍历和输出时间；
- 空间复杂度：$O(n)$ 临时字符串空间。
T2. 判断是否能拆分数组（Medium）
https://leetcode.cn/problems/check-if-it-is-possible-to-split-array/
题解（思维题）
思维题，主要题目的两个条件只要满足其中一个即可
标签：node,周赛,连通性,val,复杂度,safe,37,newX,newY From： https://www.cnblogs.com/pengxurui/p/17611136.html