脚本宝典收集整理的这篇文章主要介绍了LeetCode 第 267 场周赛,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
本文对267场周赛题目做一个小结。周赛题目链接在此
有 n 个人前来排队买票,其中第 0 人站在队伍 最前方 ,第 (n - 1) 人站在队伍 最后方 。
给你一个下标从 0 开始的整数数组 tickets ,数组长度为 n ,其中第 i 人想要购买的票数为 tickets[i] 。
每个人买票都需要用掉 恰好 1 秒 。一个人 一次只能买一张票 ,如果需要购买更多票,他必须走到 队尾 重新排队(瞬间 发生,不计时间)。如果一个人没有剩下需要买的票,那他将会 离开 队伍。
返回位于位置 k(下标从 0 开始)的人完成买票需要的时间(以秒为单位)。
示例 1:
输入:tickets = [2,3,2], k = 2 输出:6 解释:
本题是例行签到题,数据范围不大,暴力实现就可以通过。 本题给定一个数组,表示有n个人每个人购买若干张票。一个人每次只能买一张,如果还需要购买就要重新排队。每次购票耗时1s,求第k个人买完自己的票要多久。 本题按照要求直接做即可。建一个队列,将编号0~n-1依次入队,每次出队一个编号,就把该编号的购票数减一,同时计数器加1,代表这个号的人买票一张,耗时1s。如果减一之后这个编号还有票需要购买,就再次入队。直到编号为k的购票数减少至0,返回计数器的数值即可。
由于本题数据范围很小,最多100人,每人购票最多100张,最多只需10000次操作,因此暴力不会超时。如果要更快,也可以从数值角度计算排在k之前和之后的人在k买好票时分别买了几张票,再加起来即可(这样可以从 O ( N 2 ) O(N^2) O(N2) 降到 O ( N ) O(N) O(N)
C++代码如下:
//No 1
int timeRequiredToBuy(vector<int>& tickets, int k) {
queue<int>q;
int n = tickets.size(), ans = 0;
for (int i = 0; i < n; ++i) {
q.push(i);
}
while (tickets[k] > 0) {
int c = q.front();
q.pop();
tickets[c]--;
++ans;
if (tickets[c] > 0)q.push(c);
}
return ans;
}
给你一个链表的头节点 head 。
链表中的节点 按顺序 划分成若干 非空 组,这些非空组的长度构成一个自然数序列(1, 2, 3, 4, …)。一个组的 长度 就是组中分配到的节点数目。换句话说:
节点 1 分配给第一组 节点 2 和 3 分配给第二组 节点 4、5 和 6 分配给第三组,以此类推 注意,最后一组的长度可能小于或者等于 1 + 倒数第二组的长度 。
反转 每个 偶数 长度组中的节点,并返回修改后链表的头节点 head 。
示例 1:
输入:head = [5,2,6,3,9,1,7,3,8,4] 输出:[5,6,2,3,9,1,4,8,3,7] 解释:
本题要求对链表按规则分组翻转。分组规则是,按照1,2,3,4的自然数数列递增,先选择第一个节点为1组,然后接下来2个节点一组,在之后3个节点划在一组,以此类推。最后一组很可能不够,那就剩下有多少节点就分在一组。分好组后,每组的长度就是1,2,3,4…last。last表示最后一组,其长度不一定是倒数第二组加1.然后对其中长度为偶数的每一组都做翻转,返回完成翻转后的链表。
本题其实也没什么技巧,就是按照题意去做分组,需要注意的地方是最后一组长度可能不够计划值,实际长度为偶数也需要做翻转。
考虑到链表分组翻转有很多细节要考虑,容易出错。我这里将其转化为数组,完成翻转后再构造一个新链表(题目没有说必须原地翻转)
首先将链表元素依次提出放入数组。数组下标从0开始,每次根据是否越界和当前这一组的长度,确定下一组开始位置和本组的范围与长度。如果长度是偶数,就通过swap操作交换元素实现局部的翻转。反转结束后,新建头结点,用数组元素值依次构造节点加入链表。
C++代码如下:
//No 2
ListNode* reverseEvenLengthGroups(ListNode* head) {
vector<int>l;
ListNode* p = head;
int n = 0;
while (p) {
l.push_back(p->val);
p = p->next;
++n;
}
int i = 0,k=1;
while (i < n) {
int curL = 0;
if (i + k <= n) curL = k;
else curL = n - i;
if (curL % 2 == 0) {
for (int j = 0; j < curL / 2; ++j) {
swap(l[i + j], l[i + j + curL / 2]);
}
}
i = i + curL;
++k;
}
ListNode* helper = new ListNode(-1);
p = helper;
for (auto v : l) {
p->next = new ListNode(v);
p = p->next;
}
return helper->next;
}
字符串 originalText 使用 斜向换位密码 ,经由 行数固定 为 rows 的矩阵辅助,加密得到一个字符串 encodedText 。 originalText 先按从左上到右下的方式放置到矩阵中。
先填充蓝色单元格,接着是红色单元格,然后是黄色单元格,以此类推,直到到达 originalText 末尾。箭头指示顺序即为单元格填充顺序。所有空单元格用 ’ ’ 进行填充。矩阵的列数需满足:用 originalText 填充之后,最右侧列 不为空 。
接着按行将字符附加到矩阵中,构造 encodedText 。 先把蓝色单元格中的字符附加到 encodedText 中,接着是红色单元格,最后是黄色单元格。箭头指示单元格访问顺序。
例如,如果 originalText = “cipher” 且 rows = 3 ,那么我们可以按下述方法将其编码:
蓝色箭头标识 originalText 是如何放入矩阵中的,红色箭头标识形成 encodedText 的顺序。在上述例子中,encodedText = “ch ie pr” 。 给你编码后的字符串 encodedText 和矩阵的行数 rows ,返回源字符串 originalText 。
注意:originalText 不 含任何尾随空格 ’ ’ 。生成的测试用例满足 仅存在一个 可能的 originalText 。
示例 1:
输入:encodedText = “ch ie pr”, rows = 3 输出:“cipher” 解释:此示例与问题描述中的例子相同。
本题给了一种字符串加密方式,先构造一定行数的二维网格,将原字符串按照左上到右下的对角线方向逐个填充,首先从第一行第一列开始,向右下角(行数+1,列数+1)填充;然后从第一行第二列开始,以此类推。最后将二维表格逐行读取拼接成字符串,作为加密后的字符串。现在本题给定加密后的字符串以及二维网格行数,让我们解析原字符串。
实际上本题也没有什么技巧可言,由于加密后的字符串包含了二维网格所有元素(未填充按空格记录),所以我们根据其长度和行数,就可以得到这个网格的列数,进而按照逐行填充的顺序,把加密字符串的每个字符填回二维网格中,再根据原有规则,从对角线方向读取恢复原字符串。
另外本题说明原始字符串没有结尾处的空格,回复之后要将末尾空格删去。
C++代码如下:
//No 3
string decodeCiphertext(string encodedText, int rows) {
int n = encodedText.size(),cols=n/rows;
vector<vector<char>> board(rows, vector<char>(cols));
for (int i = 0; i < n; ++i) {
int r = i / cols, c = i % cols;
board[r][c] = encodedText[i];
}
string ans;
for (int i = 0; i < cols; ++i) {
int sr = 0, sc = i;
while (sr < rows && sc < cols) {
ans.push_back(board[sr][sc]);
++sr;
++sc;
}
}
while (ans.back() == ' ') ans.pop_back();
return ans;
}
给你一个整数 n ,表示网络上的用户数目。每个用户按从 0 到 n - 1 进行编号。
给你一个下标从 0 开始的二维整数数组 restrictions ,其中 restrictions[i] = [xi, yi] 意味着用户 xi 和用户 yi 不能 成为 朋友 ,不管是 直接 还是通过其他用户 间接 。
最初,用户里没有人是其他用户的朋友。给你一个下标从 0 开始的二维整数数组 requests 表示好友请求的列表,其中 requests[j] = [uj, vj] 是用户 uj 和用户 vj 之间的一条好友请求。
如果 uj 和 vj 可以成为 朋友 ,那么好友请求将会 成功 。每个好友请求都会按列表中给出的顺序进行处理(即,requests[j] 会在 requests[j + 1] 前)。一旦请求成功,那么对所有未来的好友请求而言, uj 和 vj 将会 成为直接朋友 。
返回一个 布尔数组 result ,其中元素遵循此规则:如果第 j 个好友请求 成功 ,那么 result[j] 就是 true ;否则,为 false 。 注意:如果 uj 和 vj 已经是直接朋友,那么他们之间的请求将仍然 成功 。
示例 1: 输入:n = 3, restrictions = [[0,1]], requests = [[0,2],[2,1]] 输出:[true,false] 解释: 请求 0 :用户 0 和 用户 2 可以成为朋友,所以他们成为直接朋友。 请求 1 :用户 2 和 用户 1 不能成为朋友,因为这会使 用户 0 和 用户 1 成为间接朋友 (1–2--0) 。
本题要求我们对于编号0~n-1的n个用户,根据请求和约束确定他们之间的朋友关系,对于每个请求,如果请求的两个用户(v1,v2)建立朋友关系,就记为true,否则记为false,最后返回每个请求是否成功的数组。
这里我们需要判断和建立直接-间接朋友关系,也就是朋友关系是可以传递的。因此很容易想到采用数据结构并查集,一旦a和b建立了朋友关系,那么a和b原来各自的朋友之间也就建立了间接朋友关系。
因此我们采用并查集处理朋友关系。但是本题还有一个要求,有些用户被约束无法成为直接或间接的好友。因此,我们应当对于每一个请求,首先通过查询判断是否已经是好友了,是的话直接记录该请求结果为true;如果不是,我们要先判断将二者加为好友会不会违反一些约束,如果违反了,就记录为false并且不把这个朋友关系真的添加进去,如果不违反,再进行添加,添加后请求结果为true。
这个思路也比较简单粗暴,复杂度比较极限,正好能过。由于并查集没有删除的操作(并集之后无法还原),我这里用了很直接的方式。如果一个请求的两个用户还不是好友,就先把原并查集拷贝一份副本,在副本对象中进行添加好友关系,判断是否与约束条件有冲突。如果没有冲突,再把修改后的副本赋值给原并查集,添加成功;否则就认为这个添加无法进行,原并查集对象不做修改,该请求为false。
C++代码如下:
class UnionFind {
int n;
vector<int> parent;
vector<int> size;
public:
UnionFind(int n_) {
this->n = n_;
parent = vector<int>(n);
size = vector<int>(n, 1);
for (int i = 0; i < n; ++i)
parent[i] = i;
}
int find(int idx) {
if (parent[idx] == idx)
return idx;
return find(parent[idx]);
}
void connect(int a, int b) {
int fa = find(a), fb = find(b);
if (fa != fb) {
if (size[fa] > size[fb]) {
parent[fb] = fa;
size[fa] += size[fb];
}
else {
parent[fa] = fb;
size[fb] += size[fa];
}
}
}
};
//No 4
vector<bool> friendRequests(int n, vector<vector<int>>& restrictions, vector<vector<int>>& requests) {
int nre = requests.size();
vector<bool>ans(nre);
UnionFind UF(n);
for (int i = 0; i < nre; ++i) {
int v1 = requests[i][0], v2 = requests[i][1];
if (UF.find(v1) == UF.find(v2)) ans[i] = true;
else {
UnionFind UFtmp = UF;
UFtmp.connect(v1, v2);
bool can = true;
for (auto r : restrictions) {
if (UFtmp.find(r[0]) == UFtmp.find(r[1])) {
can = false;
break;
}
}
ans[i] = can;
if(can) UF.connect(v1, v2);
}
}
return ans;
}
以上是脚本宝典为你收集整理的LeetCode 第 267 场周赛全部内容,希望文章能够帮你解决LeetCode 第 267 场周赛所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。