力扣周赛267
A. 买票需要的时间
有
个人排队买票，每次花费一秒钟时间买一张票，买完离队，还要买就得到队尾继续排队
请问第
个人买完的时候一共花了多长时间？
题解
数据量很小，直接上队列模拟
// cpp
class Solution {
public:
int timeRequiredToBuy(vector<int>& t, int k) {
queue<int> q;
int n = static_cast<int>(t.size());
for (int i = 0; i < n; ++i) q.push(i);
int cnt = 0, ans = 0;
while (!q.empty()) {
int temp = q.front(); q.pop();
if (temp == k && t[temp] == 1) {ans = ++cnt; break;}
if (t[temp] > 1) q.push(temp);
cnt++, t[temp]--;
}
return ans;
}
};
B. 反转偶数长度组的节点
给定一个链表，从头到尾按照长度
分组，如果链表的长度为偶数则反转，输出最后的链表
注意，最后一组的长度不一定为前一组的长度加
题解
这里偷个懒，不打算用空间
的做法，直接上 STL
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseEvenLengthGroups(ListNode* head) {
vector<int> vec;
while (head) vec.emplace_back(head->val), head = head->next;
int cnt = 1, n = static_cast<int>(vec.size()), i = 0;
while (i < n) {
int L = min(cnt, n - i);
if (L % 2 == 0) reverse(vec.begin() + i, vec.begin() + i + L);
i = min(i + cnt, n);
++cnt;
}
ListNode* ans = new ListNode(-1), *cur = ans;
for (auto& i: vec) cur->next = new ListNode(i), cur = cur->next;
return ans->next;
}
};
C. 解码斜向换位密码
把明文按照对角线排列在二维矩阵里面，横向遍历得到密文
现在给定密文
，给定矩阵长度
，按照规则解密
题解
先把一维的密码
排列在二维矩阵里面，然后对角线遍历即可，最后去除后导零
// cpp
class Solution {
public:
string decodeCiphertext(string e, int m) {
int sz = static_cast<int>(e.size());
int n = sz / m;
vector<vector<char>> vec(m, vector<char>(n));
for (int i = 0; i < sz; ++i) {
vec[i / n][i % n] = e[i];
}
string ans;
for (int j = 0; j < n; ++j) {
int k = j;
for (int i = 0; i < m; ++i) {
ans += vec[i][k++];
if (k == n) break;
}
}
int pos = 0;
for (int i = static_cast<int>(ans.size()); i >= 1; --i)
if (ans[i - 1] != ' ') {pos = i; break;}
return pos >= 1 ? ans.substr(0, pos) : "";
}
};
D. 处理含限制条件的好友请求
给定
个人，给定一个 res 数组，每个元素含有两个元素，表示这两个人不能结为朋友，再给定一个 req 数组，每个元素也含有两个元素，表示这两个人想要结成朋友
最初的时候，每个人没有朋友，现在对于 req 数组中的每一个请求，如果对应的两个人可以结成朋友，返回 true，如果不行，返回 false，输出对应的 bool 数组
题解
对于两个人 u, v，我们可以依次遍历 res 数组中的限制关系，判断 u, v 各自的好友集合是否存在限制，如果没有可以合并集合，否则就得返回 false，直接用并查集来维护就可以
// cpp
class Set {
int n;
vector<int> pre;
vector<int> rk;
public:
Set(int _n):
n(_n), pre(vector<int>(_n + 1)), rk(vector<int>(_n + 1)) {
for (int i = 0; i <= n; ++i) rk[i] = 1, pre[i] = i;
}
int findPre(int x) {
return x == pre[x] ? x : pre[x] = findPre(pre[x]);
}
void uni(int x, int y) {
int fx = findPre(x), fy = findPre(y);
if (fx == fy) return;
if (rk[fx] <= rk[fy]) pre[fx] = fy, rk[fy] += rk[fx];
else pre[fy] = fx, rk[fx] += rk[fy];
}
bool isCommon(int x, int y) {return findPre(x) == findPre(y);}
};
class Solution {
public:
bool check(Set* st, int u, int v, int x, int y) {
return (st->isCommon(u, x) && st->isCommon(v, y) || st->isCommon(u, y) && st->isCommon(v, x));
}
vector<bool> friendRequests(int n, vector<vector<int>>& res, vector<vector<int>>& req) {
Set* st = new Set(n);
vector<bool> ans;
for (auto& i: req) {
int u = i[0], v = i[1];
bool flag = true;
for (auto& j: res) {
int x = j[0], y = j[1];
if (check(st, u, v, x, y)) {flag = false; break;}
}
if (flag) st->uni(u, v);
ans.push_back(flag);
}
return ans;
}
};
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-11-15，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
