leetcode 第 263 场算法比赛

零、背景

这次比赛的题都不难，我却想复杂了，最后一题比赛结束后才通过。

PS1：昨天参加了腾讯的 TPC 2021年度总决赛。
面对那么多 ACM 的 final 与金牌选手，我这个银牌边缘选手竟然去做没人通过的最后一题，果然是膨胀了。
最后浪费了一个小时半，如果跟着榜单走的话，应该可以进去前50名吧。

PS2：举办第一届 TPC 比赛的时候，官方说考虑到大家都工作这么多年了，不出高级算法，只出基础的数据结构与数学题。
结果第二届开始，TPC 就变味了，题目已经与 ACM 难度一模一样了。

PS3：下周 leetcode 第 264 场算法比赛应该不能参加了，因为公司组织团建，去湖南郴州。

一、检查句子中的数字是否递增

题意：给一个由单词组成的句子，单词时间使用空格分割。
问数字单词是否是严格递增的？

思路：顺序提取出数字，判断是否大于上一个数字即可。

##　二、简易银行系统

题意：给一个银行账户数组，可以进行转账、提款、存款。
问三个操作是否可以正常进行。

思路：先判断账户是否合法，合法后对于转账与取钱判断下钱是否够即可。

三、统计按位或能得到最大值的子集数目

题意：给一个数组，可以求出所有数字的最大或值。
问有多少个子集，也可以得到这个最大或值。

思路：数组最大 16，暴力枚举即可。

思考题：假设数组很大，比如几千几万，这道题又该如何做呢？

四、到达目的地的第二短时间

题意：给一个无向连通道路图。
每个顶点有一个红绿灯，红绿灯定时每隔 change 秒切换一次红绿灯。
每条道路通过时间固定为 time 。
绿灯时间必须从顶点出发，而进入顶点则不需要关心红绿灯的颜色。

问从起点1 到达终点 n的第二小时间（去重）。

思路：显然最小时间就是最短路的跳数计算出的时间。

这道题有多个方法，我比赛的时候选择了最难的方法，被卡超时了。

方法一：贪心。

假设最短路长度是 k，显然，如果存在 k+1 的次短路，答案肯定是 k+1 跳的时间。
如果不存在 k+1 的此短路，则答案为 k+1 跳的时间，即最后一个点跳回去再跳回来。

BfsStep(); // BFS 求出单源最短路
InitStepTime(); // 求 n+2 跳的所有答案

if(DfsCheck(1, 0)) {
    return stepToTime[step[1] + 1];
} else {
    return stepToTime[step[1] + 2];
}

方法二：次小值剪枝。

既然是求第二小的答案，通过优先队列搜索，限制每个点只能到达两次，这样就可以求出每个点的第二小时间了。

ans.resize(n+1);
priority_queue<Node> que; // 队列的时间为到达时间

que.push(Node{0, 1});
UpdateAns(1, 0);

while(!que.empty()) {
    auto p = que.top(); que.pop();
    int t = p.first;
    int u = p.second;
    // printf("t=%d u=%d\n", t, u);
    // 修正对齐 t 时间
    if((t / change) % 2 == 1) {
        // 等待到绿灯
        t += change - (t % change);
    }
    t += time; // 赶路时间
    
    for(auto v: path[u]) {
        // 到达终点
        if(UpdateAns(v, t)) { //判断是否是最小值或者次小值
            que.push(Node{t, v});
        }
    }
}

方法三：启发式剪枝。

预选计算出最小值：最短路 k 跳。
一种可能的次小值：最短路 k + 2 跳。

然后使用优先队列搜索，入队的时候，判断当前时间加上剩余时间是否小于目前次小值。

剩余时间计算方法：先对齐红绿灯时间，剩下的就是最短路跳数的时间。
最短路跳数和时间可以预处理得到。

注意实现：优先队列搜索的时候，第一维度是时间，第二维度建议是当前节点的最短路跳数。
毕竟跳数越小时间越少，从而可以把后面的都剪枝掉。

bool Skip(int v, int t){ // 剪枝：当前时间加剩余时间
    if((t / change) % 2 == 1) {
        // 等待到绿灯
        t += change - (t % change);
    }
    return t + stepToTime[step[v]] >= GetSecondAns();
}


CalTmpAns(); // 计算临时次优答案，用于剪枝
InitStepTime(); //

priority_queue<Node> que; // 队列的时间为到达时间
que.push(Node{0, 1});

while(!que.empty()) {
    Node p = que.top(); que.pop();
    int u = p.u;
    int t = p.t;
    // printf("t=%d u=%d\n", t, u);
    // 修正对齐 t 时间
    if((t / change) % 2 == 1) {
        // 等待到绿灯
        t += change - (t % change);
    }
    t += time; // 赶路时间
    
    for(auto v: path[u]) {
        // 到达终点
        if(v == n) UpdateAns(t);
        
        // printf("u=%d v=%d t=%d step=%d secondAns=%d\n", u, v, t, step[v], GetSecondAns());
        if(Skip(v, t)) {
            // printf("skip\n");
            continue; // 剪枝：全是绿灯，依旧大于 secondAns
        }
        que.push(Node{t, v});
    }
}

方法四：次短路算法

既然是求次小时间，显然的次短路问题。
如果存在环，则枚举所有顶点的边尝试进程松弛，判断是否可以使得最小跳加一。

这个方法类似于方法一的贪心。

五、最后

这次比赛前三道题 16 分钟做完了，结果最后一题又翻车了。

最后一题我采用的启发式搜索。
本来想大概剪枝一下就行了，结果被某些特殊样例卡超时了。
最后改成精确剪枝后，就通过了。

加油，算法人。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code

本文首发于公众号：天空的代码世界，微信号：tiankonguse
如果你想留言，可以在微信里面关注公众号进行留言。