LeetCode 2022秋季编程赛总结

0.前言

刚开始迟到了十几分钟，一个半小时，只A了三道，后面两道战术性放弃。最终排名836，也算是意料之外了。

1.气温变化趋势

题目

力扣城计划在两地设立「力扣嘉年华」的分会场，气象小组正在分析两地区的气温变化趋势，对于第 i ~ (i+1) 天的气温变化趋势，将根据以下规则判断：

若第 i+1 天的气温 高于 第 i 天，为 上升 趋势
若第 i+1 天的气温 等于 第 i 天，为 平稳 趋势
若第 i+1 天的气温 低于 第 i 天，为 下降 趋势
已知 temperatureA[i] 和 temperatureB[i] 分别表示第 i 天两地区的气温。
组委会希望找到一段天数尽可能多，且两地气温变化趋势相同的时间举办嘉年华活动。请分析并返回两地气温变化趋势相同的最大连续天数。

即最大的 n，使得第 i~i+n 天之间，两地气温变化趋势相同

示例 1：

输入：
temperatureA = [21,18,18,18,31]
temperatureB = [34,32,16,16,17]

输出：2

解释：如下表所示， 第 2～4 天两地气温变化趋势相同，且持续时间最长，因此返回 4-2=2

思路

• 直接计算出A、B两地的气温变换趋势，存入两个数组
• 遍历数组，更新最大相同子数组长度
• 时间复杂度：$O(n)$；空间复杂度：$O(n)$

代码

class Solution {
    public int temperatureTrend(int[] temperatureA, int[] temperatureB) {
        int n = temperatureA.length;
        int[] a = new int[n-1];
        int[] b = new int[n-1];
        for ( int i = 1; i < n; i++ ) {
            a[i-1] = gao(temperatureA[i], temperatureA[i-1]);
            b[i-1] = gao(temperatureB[i], temperatureB[i-1]);
        }

        int res = 0, cnt = 0;
        for ( int i = 0; i < n-1; i++ ) {
            if ( a[i] == b[i] ) cnt++;
			// 更新最大值，重新计数
            else {
                res = Math.max(res, cnt);
                cnt = 0;
            }
        }
        return Math.max(res, cnt);
    }
    int gao(int a, int b) {
        return a == b ? 0 : (a > b ? 1 : -1);
    }
}

2.交通枢纽

题目

为了缓解「力扣嘉年华」期间的人流压力，组委会在活动期间开设了一些交通专线。path[i] = [a, b] 表示有一条从地点 a通往地点 b 的 单向 交通专线。
若存在一个地点，满足以下要求，我们则称之为 交通枢纽：

• 所有地点（除自身外）均有一条 单向 专线 直接 通往该地点；
• 该地点不存在任何 通往其他地点 的单向专线。
  请返回交通专线的 交通枢纽。若不存在，则返回 -1。

注意：

• 对于任意一个地点，至少被一条专线连通。

示例 1：

输入：path = [[0,1],[0,3],[1,3],[2,0],[2,3]]

输出：3

解释：如下图所示：
地点 0,1,2 各有一条通往地点 3 的交通专线，
且地点 3 不存在任何通往其他地点的交通专线。

思路

无需建图，直接统计节点出入度数。出度0 && 入度n-1的节点就是交通枢纽

代码

class Solution {
    public int transportationHub(int[][] path) {
        int[] in = new int[1001];
        int[] out = new int[1001];
		// 统计节点个数
        Set<Integer> set = new HashSet<>();
        for ( int[] p : path ) {
            out[p[0]]++;
            in[p[1]]++;
            set.add(p[0]);
            set.add(p[1]);
        }
        for ( int i = 0; i < 1001; i++ ) {
            if ( in[i] == set.size()-1 && out[i] == 0 ) return i;
        }
        return -1;
    }
} 	

3.弹珠游戏

题目

欢迎各位来到「力扣嘉年华」，接下来将为各位介绍在活动中广受好评的弹珠游戏。

N*M 大小的弹珠盘的初始状态信息记录于一维字符串型数组 plate 中，数组中的每个元素为仅由 “O”、“W”、“E”、"." 组成的字符串。其中：

• “O” 表示弹珠洞（弹珠到达后会落入洞中，并停止前进）；
• “W” 表示逆时针转向器（弹珠经过时方向将逆时针旋转 90 度）；
• “E” 表示顺时针转向器（弹珠经过时方向将顺时针旋转 90 度）；
• “.” 表示空白区域（弹珠可通行）。

游戏规则要求仅能在边缘位置的 空白区域 处（弹珠盘的四角除外）沿 与边缘垂直 的方向打入弹珠，并且打入后的每颗弹珠最多能 前进 num 步。请返回符合上述要求且可以使弹珠最终入洞的所有打入位置。你可以 按任意顺序 返回答案。

注意：

• 若弹珠已到达弹珠盘边缘并且仍沿着出界方向继续前进，则将直接出界

示例 1：

输入：
num = 4
plate = ["..E.",".EOW","..W."]

输出：[[2,1]]

解释：
在 [2,1] 处打入弹珠，弹珠前进 1 步后遇到转向器，前进方向顺时针旋转 90 度，再前进 1 步进入洞中。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/EXvqDp
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

直接DFS，从四个边界开始，看在num步之内是否能到达“O”之处。注意，四个边角要除外；另外，方向的处理使用dir数组来取模转移。

int[][] dirs = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

代码

class Solution {
    char[][] g;
    int num;
    // 上，右，下，左（顺时针）
    int[][] dirs = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    List<int[]> res = new ArrayList<>();
    public int[][] ballGame(int _num, String[] plate) {
        num = _num;
        int n = plate.length, m = plate[0].length();
        g = new char[n][m];
        for ( int i = 0; i < n; i++ ) g[i] = plate[i].toCharArray();
        
        // 从第一行，最后一行开始进入
        for ( int i = 1; i < m-1; i++ ) {
            if ( g[0][i] == '.' && dfs(0, i, 0, 2) ) {
                res.add(new int[]{0, i});
            }
            if ( g[n-1][i] == '.' && dfs(n-1, i, 0, 0) ) {
                res.add(new int[]{n-1, i});
            }
        }
        // 第一列，最后一列
        for ( int i = 1; i < n-1; i++ ) {
            if ( g[i][0] == '.' && dfs(i, 0, 0, 1) ) {
                res.add(new int[]{i, 0});
            }
            if ( g[i][m-1] == '.' && dfs(i, m-1, 0, 3) ) {
                res.add(new int[]{i, m-1});
            }
        }

        int[][] ans = new int[res.size()][2];
        int idx = 0;
        for (int[] tt : res) ans[idx++] =tt;
        return ans;

    }
    boolean dfs(int i, int j, int step, int idx) {
        if ( step > num ) return false;
        if ( g[i][j] == 'O' ) return true;
        // 新坐标
        int dx = i + dirs[idx][0], dy = j + dirs[idx][1];
        if ( out(dx, dy) ) return false;
        return dfs(dx, dy, step+1, nextIdx(dx, dy, idx));
    }
    boolean out(int i, int j) {
        return i < 0 || i >= g.length || j< 0 || j >= g[0].length;
    }
    int nextIdx(int i, int j, int idx) {
        // 逆时针，+3
        if ( g[i][j] == 'W' ) idx = (idx+3) % 4;
        // 顺时针，+1
        else if ( g[i][j] == 'E' ) idx = (idx+1) % 4;
        return idx;
    }
}