中国银联专场竞赛🏦

本文最后更新于:2022年10月24日 晚上

专场信息

比赛链接:中国银联专场竞赛(2023届校园招聘专场) - 力扣(LeetCode)

排名:

cdsCE.png

题目解析(Q1, Q2, Q3)

银联-1. 重构链表

题意分析


给定一个链表,删除其中的所有偶数的节点

链表题大多数都可以用线性表水过去,笔者在此提供水版和正解版两种

正解:

  • 使用一个哨兵节点,选择性地将链表中的元素加入其中

参考代码


1
2
3
4
5
6
7
8
9
10
11
12
13
14
using vi = vector<int>;
class Solution { //水题版
public:
ListNode* reContruct(ListNode* head) {
vi a;
while(head)a.push_back(head->val),head=head->next;
auto* ans=new ListNode(-1),*p=ans;

for(int v:a){
if(v%2)p->next=new ListNode(v),p=p->next;
}
return ans->next;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {		//正解
public:
ListNode* reContruct(ListNode* head) {
auto *dummy=new ListNode(-1),*p=dummy;
while(head){
if(head->val%2){
p->next=new ListNode(head->val);
p=p->next;
}
head=head->next;
}
return dummy->next;
}
};

银联-2. 勘探补给

题意分析


给定工程队的位置和所有补给点的位置,返回工程队选择补给的位置下标

二分查找每一个工程队的补给位置即可(这里采用maplower_bound方法);

本题中使用了统计最大最小值的方法,来巧妙处理边界问题(实际上就是边界WA了好几次懒得改了)

参考代码


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#define pb push_back

class Solution {
public:
vector<int> explorationSupply(vector<int> &station, vector<int> &pos) {
vector<int> ans;
map<int, int> map;
int maxx=*max_element(all(station)), minn=*min_element(all(station));
for (int i = 0; i < station.size(); ++i) {
map[station[i]] = i;
}
for (int p: pos) {
if(p>=maxx){
ans.push_back(station.size()-1);
continue;
}else if (p<minn){
ans.push_back(0);
continue;
}

auto it = map.lower_bound(p);
if (it->first == p) {
ans.push_back(it->second);
continue;
}
if (it != map.begin())--it;

if (it == map.end()) {
--it;
ans.pb(it->second);
} else if (it == map.begin()) {
int i1 = it->second, i2 = i32;
++it;
if (it != map.end())i2 = it->second;
if (abs(station[i1] - p) <= abs(station[i2] - p))ans.pb(i1);
else ans.pb(i2);
} else {
int i1 = it->second, i2, i3 = i32;
--it;
i2 = it->second;
++it;
++it;
if (it != map.end())i3 = it->second;

int d1 = abs(p - station[i1]), d2 = abs(p - station[i2]), d3 = abs(p - station[i3]);
if (d1 <= d2 && d1 <= d3)ans.pb(i1);
else if (d2 <= d1 && d2 <= d3)ans.pb(i2);
else ans.pb(i3);
}
}
return ans;
}
};

银联-3. 风能发电

题意分析


给定容量为storeLimit的容器,在每一个使用区间内:

  • 若此时的供电量小于minSupply则从容器中去除电量(如果有富余)
  • 若此时的供电量大于maxSupply则向容器中加入电量(如果还有空间)

随时间变化,供电的最大最小需求也会不同,返回最终容器中剩余的电荷量

双指针模拟,一个指向供电,一个指向时间戳

参考代码


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int StoredEnergy(int storeLimit, const vector<int>& power, const vector<vector<int>>& supply){
int i=0,j=0,m=power.size(),n=supply.size(),time=0;
int limit=0;
while (i<m){
if(time>=supply[min(j+1,n-1)][0])j=min(j+1,n-1);
int p=power[i];

if(p<=supply[j][1])limit=max(limit-(supply[j][1]-p),0);
else if(p>= supply[j][2])limit=min(storeLimit, limit+(p-supply[j][2]));
++i;
++time;
}
return limit;
}
};

中国银联专场竞赛🏦
http://example.com/2022/09/16/CNUPC2022/
作者
Haruko
发布于
2022年9月16日
更新于
2022年10月24日
许可协议