leetcode LCCUP 2022

只能说水了三道题目，第四题 dp 某个转移公式推的不对。

LCP 61. 气温变化趋势

题目

力扣城计划在两地设立「力扣嘉年华」的分会场，气象小组正在分析两地区的气温变化趋势，对于第 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=2image.png

示例 2：

输入： temperatureA = [5,10,16,-6,15,11,3] temperatureB = [16,22,23,23,25,3,-16]

输出：3

提示：

2 <= temperatureA.length == temperatureB.length <= 1000
-20 <= temperatureA[i], temperatureB[i] <= 40

地址

https://leetcode.cn/problems/6CE719/

题意

模拟

思路

刚开始理解错了，后来发现其实很简单，只需要判断相邻的两天，两个温度记录的变换趋势是否相同：

同时增减；
同时减少；
同时相等；

复杂度分析：

时间复杂度：$O(n \log n)$，其中 $n$ 表示数组的长度。
空间复杂度：$O(n \log n)$，其中 $n$ 表示数组的长度。

代码

class Solution {
public:
    bool checkSameTrend(int a1, int a2, int b1, int b2) {
        if ((a2 > a1 && b2 > b1) || (a2 < a1 && b2 < b1) || (a2 == a1 && b2 == b1)) {
            return true;
        } else {
            return false;
        }
    }
    
    int temperatureTrend(vector<int>& temperatureA, vector<int>& temperatureB) {
        int n = temperatureA.size();
        int ans = 0;
        int cur = 0;
        for (int i = 1; i < n; i++) {
            if (checkSameTrend(temperatureA[i - 1], temperatureA[i], 
                               temperatureB[i - 1], temperatureB[i])) {
                cur++;
            } else {
                cur = 0;
            }
            ans = max(ans, cur);
        }
        return ans;
    }
};

LCP 62. 交通枢纽

题目

为了缓解「力扣嘉年华」期间的人流压力，组委会在活动期间开设了一些交通专线。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 不存在任何通往其他地点的交通专线。image.png

示例 2：

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

输出：-1

解释：如下图所示：不存在满足 交通枢纽 的地点。image.png

提示：

1 <= path.length <= 1000
0 <= path[i][0], path[i][1] <= 1000
path[i][0] 与 path[i][1] 不相等

地址

https://leetcode.cn/contest/cnunionpay2022/problems/6olJmJ/

题意

图论

思路

根据题意可知在有向图中交通枢纽即入度为 $n-1$，出度为 $0$ 的节点，所以我们直接统计每个节点的出度与入度即可。
复杂度分析：

时间复杂度：时间复杂度为 $O(n)$，其中 $n$ 表示每节点的数目。
空间复杂度：空间复杂度为 $O(n)$，其中 $n$ 表示每节点的数目。

代码

class Solution {
public:
    int transportationHub(vector<vector<int>>& path) {
        vector<int> indegree(1001);
        vector<int> outdegree(1001);
        unordered_set<int> vertx;
        for (auto v : path) {
            indegree[v[1]]++;
            outdegree[v[0]]++;
            vertx.emplace(v[0]);
            vertx.emplace(v[1]);
        }
        int n = vertx.size();
        for (auto v : vertx) {
            if (indegree[v] == n - 1 && outdegree[v] == 0) {
                return v;
            }
        }
        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 步进入洞中。
b054955158a99167b8d51da0e22a54da.gif

示例 2：

输入：
num = 5
plate = [".....","..E..",".WO..","....."]

输出：[[0,1],[1,0],[2,4],[3,2]]

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

示例 3：

输入：
num = 3
plate = [".....","....O","....O","....."]

输出：[]

解释：
由于弹珠被击中后只能前进 3 步，且不能在弹珠洞和弹珠盘四角打入弹珠，故不存在能让弹珠入洞的打入位置。

提示：

1 <= num <= 10^6
1 <= plate.length, plate[i].length <= 1000
plate[i][j] 仅包含 "O"、"W"、"E"、"."

地址

https://leetcode.cn/contest/season/2022-fall/problems/EXvqDp/

题意

BFS

思路

感觉这个题目暴力模拟即可，由于只有两个方向改变，所以可能每个弹珠的轨迹不会成环。所以我们只需要进行暴力模拟即可。
复杂度分析

时间复杂度：时间复杂度为 $O(n^2)$，$n$ 为矩阵的行数。
空间复杂度：时间复杂度为 $O(n^2)$，$n$ 为矩阵的行数。

代码

class Solution {
public:
    bool check(int step, int x, int y, int d, vector<string>& plate) {
        int m = plate.size();
        int n = plate[0].size();
        int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        while (step >= 0) {
            if (plate[x][y] == 'O') {
                return true;
            } else if (plate[x][y] == '.') {
                int nx = dirs[d][0] + x;
                int ny = dirs[d][1] + y;
                if (nx >= 0 && ny >= 0 && nx < m && ny < n) {
                    x = nx;
                    y = ny;

                    step--;
                } else {
                    break;
                }
            } else if (plate[x][y] == 'E') {
                int nx = dirs[(d + 1 + 4) % 4][0] + x;
                int ny = dirs[(d + 1 + 4) % 4][1] + y;
                if (nx >= 0 && ny >= 0 && nx < m && ny < n) {
                    x = nx;
                    y = ny;
                    d = (d + 1 + 4) % 4;
        
                    step--;
                } else {
                    break;
                }
            } else if (plate[x][y] == 'W') {
                int nx = dirs[(d - 1 + 4) % 4][0] + x;
                int ny = dirs[(d - 1 + 4) % 4][1] + y;
                if (nx >= 0 && ny >= 0 && nx < m && ny < n) {
                    x = nx;
                    y = ny;
                    d = (d - 1 + 4) % 4;
                   
                    step--;
                } else {
                    break;
                }
            }
            if (step < 0) {
                break;
            }
        }
        return false;
    }
    
    vector<vector<int>> ballGame(int num, vector<string>& plate) {
        int m = plate.size();
        int n = plate[0].size();
        vector<vector<int>> ans;
        for (int i = 1; i < m - 1; i++) {
            if (plate[i][0] == '.') {
                if (check(num, i, 0, 0, plate)) {
                    ans.push_back({i, 0});
                }
            }
        }
        for (int i = 1; i < n - 1; i++) {
            if (plate[0][i] == '.') {
                if (check(num, 0, i, 1, plate)) {
                    ans.push_back({0, i});
                }
            }
        }
        for (int i = 1; i < m - 1; i++) {
            if (plate[i][n - 1] == '.') { 
                if (check(num, i, n - 1, 2, plate)) {
                    ans.push_back({i, n - 1});
                }
            }
        }
        for (int i = 1; i < n - 1; i++) {
            if (plate[m - 1][i] == '.') {
                if (check(num, m - 1, i, 3, plate)) {
                    ans.push_back({m - 1, i});
                }
            }
        }
        return ans;
    }
};

4. 二叉树灯饰

题目

「力扣嘉年华」的中心广场放置了一个巨型的二叉树形状的装饰树。每个节点上均有一盏灯和三个开关。节点值为 0 表示灯处于「关闭」状态，节点值为 1 表示灯处于「开启」状态。每个节点上的三个开关各自功能如下：

开关 1：切换当前节点的灯的状态；
开关 2：切换以当前节点为根的子树中，所有节点上的灯的状态，；
开关 3：切换当前节点及其左右子节点（若存在的话）上的灯的状态；
给定该装饰的初始状态 root ，请返回最少需要操作多少次开关，可以关闭所有节点的灯。

示例 1：

输入：root = [1,1,0,null,null,null,1]

输出：2

解释：以下是最佳的方案之一，如图所示
b71b95bf405e3b223e00b2820a062ba4.gif

示例 2：

输入：root = [1,1,1,1,null,null,1]

输出：1

解释：以下是最佳的方案，如图所示
a4091b6448a0089b4d9e8f0390ff9ac6.gif

示例 3：

输入：root = [0,null,0]

输出：0

解释：无需操作开关，当前所有节点上的灯均已关闭

提示：

1 <= 节点个数 <= 10^5
0 <= Node.val <= 1

地址

https://leetcode.cn/contest/season/2022-fall/problems/U7WvvU/

题意

动态规划

思路

最设以 $root$ 为根节点的子树可以变为以下四种形态:

第一种形态：所有的节点均为 $0$；
第二种形态：所有的节点均为 $1$；
第三种形态：$root$为 $0$，其余节点均为 $1$；
第四种形态：$root$为 $1$，其余节点均为 $0$；
我们分别设将子树变为以上四种状态所需要的最小操作次数分别为 $a_{00},a_{01},a_{10},a_{11}$，假设 $root$ 的左子树与右子树分别变换为以上四种形态的最小步骤分别为:
$$
(l_{00},l_{01},l_{10},l_{11}),(r_{00},r_{01},r_{10},r_{11})
$$
我们知道以上四种形态的变换方式如下:
装换为第一种形态：所有的节点均为 $0$。
- 将两个孩子节点的子树分别变为所有节点均为 $0$，然后使用开关 $1$将 $root$ 变为 $0$；
- 将两个孩子节点的子树分别变为所有节点均为 $1$，然后使用开关 $1$ 将 $root$ 变为 $1$，然后再使用开关 $3$ 将整颗子树反转；
- 将两个孩子节点的子树分别变为第三种形态，即根节点为 $0$，其余节点为 $1$，然后利用开关 $1$ 将 $root$ 变为 $0$，然后在利用开关 $2$ 将 $root$ 与孩子节点反装，然后再利用开关 $3$ 将整颗子树反转；
- 将两个孩子节点的子树分别变为第四种形态，即根节点为 $1$，其余节点为 $0$，然后利用开关 $1$ 将 $root$ 变为 $1$，然后在利用开关 $2$ 将 $root$ 与孩子节点反装；
装换为第二种形态：所有的节点均为 $1$。
- 将两个孩子节点的子树分别变为所有节点均为 $1$，然后使用开关 $1$将 $root$ 变为 $1$；
- 将两个孩子节点的子树分别变为所有节点均为 $0$，然后使用开关 $1$ 将 $root$ 变为 $0$，然后再使用开关 $3$ 将整颗子树反转；
- 将两个孩子节点的子树分别变为第三种形态，即根节点为 $0$，其余节点为 $1$，然后利用开关 $1$ 将 $root$ 变为 $0$，然后在利用开关 $2$ 将 $root$ 与孩子节点反装；
- 将两个孩子节点的子树分别变为第四种形态，即根节点为 $1$，其余节点为 $0$，然后利用开关 $1$ 将 $root$ 变为 $1$，然后在利用开关 $2$ 将 $root$ 与孩子节点反装，然后利用开关 $3$ 将整颗子树反转；
装换为第三种形态：$root$为 $0$，其余节点均为 $1$。
- 将两个孩子节点的子树分别变为所有节点均为 $1$，然后使用开关 $1$将 $root$ 变为 $0$；
- 将两个孩子节点的子树分别变为所有节点均为 $0$，然后使用开关 $1$ 将 $root$ 变为 $1$，然后再使用开关 $3$ 将整颗子树反转；
- 将两个孩子节点的子树分别变为第三种形态，即根节点为 $0$，其余节点为 $1$，然后利用开关 $1$ 将 $root$ 变为 $1$，然后在利用开关 $2$ 将 $root$ 与孩子节点反装；
- 将两个孩子节点的子树分别变为第四种形态，即根节点为 $1$，其余节点为 $0$，然后利用开关 $1$ 将 $root$ 变为 $0$，然后在利用开关 $2$ 将 $root$ 与孩子节点反装，然后利用开关 $3$ 将整颗子树反转；
装换为第四种形态：$root$为 $1$，其余节点均为 $0$。
- 将两个孩子节点的子树分别变为所有节点均为 $0$，然后使用开关 $1$将 $root$ 变为 $1$；
- 将两个孩子节点的子树分别变为所有节点均为 $1$，然后使用开关 $1$ 将 $root$ 变为 $0$，然后再使用开关 $3$ 将整颗子树反转；
- 将两个孩子节点的子树分别变为第三种形态，即根节点为 $0$，其余节点为 $1$，然后利用开关 $1$ 将 $root$ 变为 $1$，然后在利用开关 $2$ 将 $root$ 与孩子节点反装，然后利用开关 $3$ 将整颗子树反转；
- 将两个孩子节点的子树分别变为第四种形态，即根节点为 $1$，其余节点为 $0$，然后利用开关 $1$ 将 $root$ 变为 $0$，然后在利用开关 $2$ 将 $root$ 与孩子节点反装；

复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 表示节点的数目。
空间复杂度：$O(C)$，其中 $n$ 表示节点的数目。

代码

class Solution {
public:
    tuple<int,int,int,int> dfs(TreeNode * root) {
        if (!root) {
            return {0, 0, 0, 0};
        }    
        
        auto [l00, l01, l10, l11] = dfs(root->left);
        auto [r00, r01, r10, r11] = dfs(root->right);
        int a00 = INT_MAX;
        int a01 = INT_MAX;
        int a10 = INT_MAX;
        int a11 = INT_MAX;
        
        /* all zero */
        a00 = min(a00, l00 + r00 + (root->val != 0));
        a00 = min(a00, l11 + r11 + (root->val != 1) + 1);
        a00 = min(a00, l10 + r10 + (root->val != 1) + 1);
        a00 = min(a00, l01 + r01 + (root->val != 0) + 2);
        
        /* all one */
        a11 = min(a11, l00 + r00 + (root->val != 0) + 1);
        a11 = min(a11, l11 + r11 + (root->val != 1));
        a11 = min(a11, l01 + r01 + (root->val != 0) + 1);
        a11 = min(a11, l10 + r10 + (root->val != 1) + 2);
        
        /* one - zero */
        a10 = min(a10, l00 + r00 + (root->val != 1));
        a10 = min(a10, l11 + r11 + (root->val != 0) + 1);
        a10 = min(a10, l10 + r10 + (root->val != 0) + 1);
        a10 = min(a10, l01 + r01 + (root->val != 1) + 2);
        
        /* zero - one */
        a01 = min(a01, l11 + r11 + (root->val != 0));
        a01 = min(a01, l00 + r00 + (root->val != 1) + 1);
        a01 = min(a01, l01 + r01 + (root->val != 1) + 1);
        a01 = min(a01, l10 + r10 + (root->val != 0) + 2);
        
        return {a00, a01, a10, a11};
    }
    
    int closeLampInTree(TreeNode* root) {
        auto [a00, a01, a10, a11] = dfs(root);
        return a00;
    }
};

LCP 65. 舒适的湿度

题目

力扣嘉年华为了确保更舒适的游览环境条件，在会场的各处设置了湿度调节装置，这些调节装置受控于总控室中的一台控制器。控制器中已经预设了一些调节指令，整数数组operate[i] 表示第 i 条指令增加空气湿度的大小。现在你可以将任意数量的指令修改为降低湿度（变化的数值不变），以确保湿度尽可能的适宜：

控制器会选择一段连续的指令，从而进行湿度调节的操作；
这段指令最终对湿度影响的绝对值，即为当前操作的「不适宜度」
在控制器所有可能的操作中，最大的「不适宜度」即为「整体不适宜度」
请返回在所有修改指令的方案中，可以得到的最小「整体不适宜度」。

示例 1：

输入：operate = [5,3,7]

输出：8

解释：对于方案 2 的 [5,3,-7] 操作指令 [5],[3],[-7] 的「不适宜度」分别为 5,3,7 操作指令 [5,3],[3,-7] 的「不适宜度」分别为 8,4 操作指令 [5,3,-7] 的「不适宜度」为 1， 因此对于方案 [5,3,-7]的「整体不适宜度」为 8，其余方案的「整体不适宜度」均不小于 8，如下表所示：image.png

示例 2：

输入：operate = [20,10]

输出：20

提示：

1 <= operate.length <= 1000
1 <= operate[i] <= 1000

地址

https://leetcode.cn/problems/3aqs1c/

题意

动态规划

思路

感觉确实是个不错的题目，详细的题解可以参考「题解」，确实可以再推导一遍。确实其中的状态转移确实难了一点。
复杂度分析：

时间复杂度：$O(nU)$，其中 $n$ 表示数组的长度, $U$ 表示数组中的最大元素。
空间复杂度：$O(U)$，其中 $n$ 表示数组的长度，$U$ 表示数组中的最大元素。

代码

class Solution {
public:
    int unSuitability(vector<int>& operate) {
        int n = operate.size();
        int u = *max_element(operate.begin(), operate.end());
        u = u * 2;
        vector<int> pre(u + 1, INT_MAX);
        pre[0] = 0;
        for (int x : operate) {
            vector<int> dp(u + 1, INT_MAX);
            for (int i = 0; i <= u; i++) {
                if (pre[i] == INT_MAX) {
                    continue;
                }
                if (i + x <= u) {
                    dp[i + x] = min(dp[i + x], max(pre[i], i + x));
                }
                if (i - x >= 0) {
                    dp[i - x] = min(dp[i - x], pre[i]);
                } else {
                    dp[0] = min(dp[0], pre[i] - i + x);
                }
            }
            pre = move(dp);
        }
        return *min_element(pre.begin(), pre.end());
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: http://mikemeng.org/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 力扣周赛

← 天堂硅谷·数字经济算法编程大赛【MIT 6.S081】 lab10 network →

扫描二维码，分享此文章