中国银联专场竞赛🏦

专场信息

比赛链接：中国银联专场竞赛（2023届校园招聘专场） - 力扣（LeetCode）

排名：

题目解析(Q1, Q2, Q3)

银联-1. 重构链表

题意分析

---

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

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

正解：

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

参考代码

---

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

---

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. 勘探补给

题意分析

---

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

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

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

参考代码

---

#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则向容器中加入电量(如果还有空间)

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

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

参考代码

---

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