LeetCode 周赛上分之旅 # 37 多源 BFS 与连通性问题

周赛 357

T1. 故障键盘（Easy）

• 标签：模拟、字符串

T2. 判断是否能拆分数组（Medium）

• 标签：思维

T3. 找出最安全路径（Medium）

• 标签：BFS、连通性、分层并查集、极大化极小、二分查找

T4. 子序列最大优雅度（Hard）

• 标签：贪心、排序、堆

---

T1. 故障键盘（Easy）

代码语言：javascript复制

https://leetcode.cn/problems/faulty-keyboard/

题解（模拟）

简单模拟题。

• 在遇到 i 字符时对已填入字符进行反转，时间复杂度是 O(n^2)；
• 使用队列和标记位可以优化时间复杂度，在遇到 i 时修改标记位和写入方向，在最后输出时根据标记位输出，避免中间的反转操作。

代码语言：javascript复制

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());
    }
};

代码语言：javascript复制

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）

代码语言：javascript复制

https://leetcode.cn/problems/check-if-it-is-possible-to-split-array/

题解（思维题）

思维题，主要题目的两个条件只要满足其中一个即可