算法疑难杂症

2022力扣秋季赛个人赛战报

字数统计: 1.2k字   |   阅读时长: 4分
,

摘要: 2022.09.24 力扣秋季赛个人赛战报

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

今天参加了力扣 2022 年的秋季赛的个人赛，这个比赛我是从 2020 年秋季赛开始打的，经过 2021 春季赛、2021 秋季赛、2022 春季赛，到这次的 2022 秋季赛，是第五次参赛。

以前或多或少在比赛前稍微准备一下，比如做几个力扣 LCP 开头的困难题，或者是把一些数学和图论的算法看一下等等。

这次应该是真正的裸赛，也就是赛前没有做任何准备，完全是靠以前的算法基础，以及积累的一些文章和代码片段来应对。成绩如下：

1300 多名，这一看感觉不是很理想，但是考虑到参赛有一万多人之多以及裸赛的因素，好像也能接受。

前两个题比较简单，一共 20 分钟解决。

第三题是属于那种想清楚好像不是很难但是实现很复杂的那种问题，值得好好拆解一下。这个题比赛的时候做了 1 小时 50 分钟，事后来看的话当时应该是误入歧途了，到最后半小时的时候发现了问题，走向正确轨道后就比较正常地完成了。

最后只剩了 20 分钟，搂了一眼第四题，确实不会，于是就提前结束了。

本文把前两个简单题过一下，磕磕绊绊过的第三题，以及后面不会的四五题在后续的文章中进行拆解。

第 1 题

分析两地区的气温变化趋势，对于第 i ~ (i+1) 天的气温变化趋势，将根据以下规则判断：

  • 若第 i+1 天的气温 高于 第 i 天，为 上升 趋势
  • 若第 i+1 天的气温 等于 第 i 天，为 平稳 趋势
  • 若第 i+1 天的气温 低于 第 i 天，为 下降 趋势

已知 temperatureA[i] 和 temperatureB[i] 分别表示第 i 天两地区的气温。

组委会希望找到一段天数尽可能多，且两地气温变化趋势相同的时间举办嘉年华活动。请分析并返回两地气温变化趋势相同的最大连续天数。

算法

从左到右枚举 i，考察 A 和 B 两个序列的变化趋势，如果相等则记为 1，如果不相等则记为 0。枚举完成后我们得到一串 01 序列，我们要做的是在这串 01 序列上找到最长的一串 1 的长度。

记录 01 序列和统计最长的一串 1 的长度可以在枚举 i 的时候同时进行，而不用真的把 01 序列记在数组里。

代码(C++)

下面是比赛现场的真实代码。

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
class Solution {
public:
    int temperatureTrend(vector<int>& temperatureA, vector<int>& temperatureB) {
        int n = temperatureA.size();
        int len = 0;
        int max_len = 0;
        for(int i = 0; i < n - 1; ++i)
        {
            int trendA = trend(temperatureA[i], temperatureA[i + 1]);
            int trendB = trend(temperatureB[i], temperatureB[i + 1]);
            if(trendA == trendB)
                len += 1;
            else
                len = 0;
            max_len = max(max_len, len);
        }
        return max_len;
    }

    int trend(int a, int b)
    {
        if(a > b)
            return 1;
        else if (a < b)
            return -1;
        else
            return 0;
    }
};

第 2 题

path[i] = [a, b] 表示有一条从地点 a通往地点 b 的 单向 交通专线。

若存在一个地点，满足以下要求，我们则称之为 交通枢纽：

  • 所有地点（除自身外）均有一条 单向 专线 直接 通往该地点；
  • 该地点不存在任何 通往其他地点 的单向专线。

请返回交通专线的 交通枢纽。若不存在，则返回 -1。

算法

交通枢纽的定义，抽象之后就是 n 个节点的有向图中的入度为 n - 1，而出度为 0 的节点。

枚举所有边，更新相应节点的入度出度，枚举结束后看是否有哪个节点的入度为 n - 1 且出度为 0 即可。

代码(C++)

以下为赛场真实代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int transportationHub(vector<vector<int>>& path) {
        vector<int> indegree(1005);
        vector<int> outdegree(1005);
        int n = 0;
        for(vector<int> e: path)
        {
            if(indegree[e[0]] == 0 && outdegree[e[0]] == 0)
                ++n;
            if(indegree[e[1]] == 0 && outdegree[e[1]] == 0)
                ++n;
            ++outdegree[e[0]];
            ++indegree[e[1]];
        }
        for(int i = 0; i < 1005; ++i)
            if(indegree[i] == n - 1 && outdegree[i] == 0)
                return i;
        return -1;
    }
};
Share