Leetcode 246场周赛
- 懵圈的我只干出来前两道问题
1903.字符串中最大的奇数
给你一个字符串 num ，表示一个大整数。请你在字符串 num 的所有 非空子字符串中找出值最大的奇数 ，并以字符串形式返回。如果不存在奇数，则返回一个空字符串 "" 。
子字符串是字符串中的一个连续的字符序列。
样例
示例1:
输入：num = "52"
输出："5"
解释：非空子字符串仅有 "5"、"2" 和 "52" 。"5" 是其中唯一的奇数。
示例2:
输入：num = "4206"
输出：""
解释：在 "4206" 中不存在奇数。
示例3:
输入：num = "35427"
输出："35427"
解释："35427" 本身就是一个奇数。提示:
- num 仅由数字组成且不含前导零
算法1 (直接遍历一遍)
思路分析
奇数特征: 个位 % 2 == 1, 从提示知道num数字不含有前导0, 最大的奇数在这里即为长度最长, 这里不存在分段问题, 不可能在num序列中被分为了两段, 因为如果后面一段是奇数序列的话, 由于后面一段的个位是奇数, 故必然能从最左边开始拼成一个更长的, 故算法思路就是从头往后遍历, 直到遍历到离左边最远的那个奇数即可, 然后返回子串
C++ 代码
class Solution
{
public:
string largestOddNumber(string num)
{
int r = -1;
for(int i = 0; i < num.size(); ++i)
// 这里判断是不是奇数, 可以直接 % 2, 虽然是字符,但 0 的 acsll码为48, 故可以直接运算
if(num[i] % 2) r = i;
if(r == -1) return "";
return num.substr(0, r + 1);
}
};时间复杂度
1904. 你完成的完整对局数
题目链接: leetcode 1904.你完成的完整对局数
一款新的在线电子游戏在近期发布，在该电子游戏中，以 刻钟 为周期规划若干时长为 15 分钟 的游戏对局。这意味着，在 HH:00、HH:15、HH:30 和 HH:45 ，将会开始一个新的对局，其中 HH 用一个从 00 到 23 的整数表示。游戏中使用 24 小时制的时钟 ，所以一天中最早的时间是 00:00 ，最晚的时间是 23:59 。
给你两个字符串 startTime 和 finishTime ，均符合 "HH:MM" 格式，分别表示你 进入 和 退出 游戏的确切时间，请计算在整个游戏会话期间，你完成的 完整对局的对局数 。
- 例如，如果 startTime = "05:20" 且 finishTime = "05:59" ，这意味着你仅仅完成从 05:30 到 05:45 这一个完整对局。而你没有完成从 05:15 到 05:30 的完整对局，因为你是在对局开始后进入的游戏；同时，你也没有完成从 05:45 到 06:00 的完整对局，因为你是在对局结束前退出的游戏。
如果 finishTime 早于 startTime ，这表示你玩了个通宵（也就是从 startTime 到午夜，再从午夜到 finishTime）。
假设你是从 startTime 进入游戏，并在 finishTime 退出游戏，请计算并返回你完成的 完整对局的对局数 。
样例
示例1:
输入：startTime = "12:01", finishTime = "12:44"
输出：1
解释：你完成了从 12:15 到 12:30 的一个完整对局。
你没有完成从 12:00 到 12:15 的完整对局，因为你是在对局开始后的 12:01 进入的游戏。
你没有完成从 12:30 到 12:45 的完整对局，因为你是在对局结束前的 12:44 退出的游戏。
示例2:
输入：startTime = "20:00", finishTime = "06:00"
输出：40
解释：你完成了从 20:00 到 00:00 的 16 个完整的对局，以及从 00:00 到 06:00 的 24 个完整的对局。
16 + 24 = 40
示例3:
输入：startTime = "00:00", finishTime = "23:59"
输出：95
解释：除最后一个小时你只完成了 3 个完整对局外，其余每个小时均完成了 4 场完整对局。
提示:
- startTime 和 finishTime 的格式为 HH:MM
- 00 <= HH <= 23
- 00 <= MM <= 59
- startTime 和 finishTime 不相等
算法1 (模拟)
思路分析
题目读完就知道这是一道模拟题, 游戏是15min一局, 然后游戏开始的时间点只有 HH:00, HH:15, HH:30, HH:45, 即一个小时内最多可以玩4盘, 然后这里还有可能出现通宵的情况, 即发现结束时间比开始时间要早.
C++ 代码
class Solution
{
public:
int numberOfRounds(string startTime, string finishTime)
{
// sh表示开始时间的小时部分, sm表示开始时间的分钟部分, fh, fm同样的处理
int sh = stoi(startTime.substr(0,2)), sm = stoi(startTime.substr(3, 2));
int fh = stoi(finishTime.substr(0,2)), fm = stoi(finishTime.substr(3, 2));
int res = 0; // 结果
int flag = 0; // 通宵标记
if(sh == fh && sm > fm) flag = 1;
while(sh != fh || flag) // 当前的小时部分未达到结束时间的小时部分
{
// 第一次进入循环时, 执行if分支的其中一条, 经过第一次循环之后sm被置为0,初始的sm对应三个时间段
if(sm == 0) res += 4;
else if(sm > 0 && sm <= 15) res += 3;
else if(sm > 15 && sm <= 30) res += 2;
else if(sm > 30 && sm <= 45) res += 1;
sh = (sh + 1) % 24;
if(sh == fh) flag = 0; // 通宵标记置为0
sm = 0;
}
int t = fm / 15; // 最后一个小时内最多可能玩几次 .
if(sm == 0) res += t;
else if(sm > 0 && sm <= 15) res += t - 1;
else if(sm > 15 && sm <= 30) res += t - 2;
else if(sm > 30 && sm <= 45) res += t - 3;
return res;
}
};算法2 (开始和结束时间均转化为分钟)
思路分析
将开始时间和结束均转化为分钟表示, 由于游戏是从一天的0点开始的, 故只需计算一下当前的结束时间中可以有多少个15min, 即包含多少盘一局游戏的时间, 然后将开始时间转化为分钟算一下其包含了多少个15min(这里需要作上取整处理, 因为没到四个时间点的不能算是一局完整的游戏), 然后二者相减得到的就是从开始到结束一共进行的游戏局数. 但这里由于通宵情况的存在, 故如果判断 finishTime < startTime ， 这时 finishTime 要加上 60 * 24 , 即加上一天.
C++ 代码
class Solution
{
public:
int get(string s)
{
int h, m
sscanf(s.c_str(), "%d:%d", &h, &m); // sscanf 处理字符串问题很好用
return h * 60 + m;
}
int numberOfRounds(string a, string b)
{
int x = get(a), y = get(b);
if (x > y) y += 24 * 60;
x = (x + 14) / 15, y /= 15; // 注意上取整的写法 x = (x + 15 - 1) / 15 等价于 x / 15上取整
return y - x;
}
};1905. 统计子岛屿
题目链接: leetcode 1905.统计子岛屿
给你两个 m x n 的二进制矩阵 grid1 和 grid2 ，它们只包含 0（表示水域）和 1（表示陆地）。一个岛屿是由四个方向（水平或者竖直）上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。
如果 grid2 的一个岛屿，被 grid1 的一个岛屿 完全 包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含，那么我们称 grid2 中的这个岛屿为 子岛屿 。
请你返回 grid2中子岛屿的数目 。
示例1
示例2
样例
示例1:
输入：grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
输出：3
解释：如上图所示，左边为 grid1 ，右边为 grid2 。
grid2 中标红的 1 区域是子岛屿，总共有 3 个子岛屿。
示例2:
输入：grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]], grid2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]
输出：2
解释：如上图所示，左边为 grid1 ，右边为 grid2 。
grid2 中标红的 1 区域是子岛屿，总共有 2 个子岛屿。提示:
算法1 (FloodFill算法 -- DFS实现)
思路分析
题目大意是要在grid2找一个连通块, 若grid2这一个连通块能被grid1的一个连通块完全包含, 则grid2的这一块连通块被称之为子岛屿, 题目要求就是计算grid2中的子岛屿数量. 首先直接模拟的话思路就是在grid2中找到一个连通块, 如果该连通块在grid1中对应的是0表示grid1并不完全包含grid2的连通块, 那么反之如果在grid2扩展连通块的过程中, 其中grid2的每一块都能在grid1找到对应, 那么同理说明grid1的也是一整块连通块, 因为grid2是连通块区域且与grid1一一对应, 故这里对于判断grid1是否完全包含grid2连通块的问题并不需要复杂处理, 直接在扩展过程中, 边扩展边判断即可. 扩展连通块的问题这里就用到了FloodFill算法, 这里FloodFill算法实现又分为两个版本, dfs和bfs两个版本.
C++ 代码 DFS实现
class Solution
{
public:
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n, m;
int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2)
{
int res = 0;
n = grid1.size(), m = grid1[0].size();
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
if(!grid2[i][j]) continue;
else
if(dfs(grid1, grid2, i, j)) ++res;
return res;
}
bool dfs(vector<vector<int>> &g1, vector<vector<int>> &g2, int x, int y)
{
g2[x][y] = 0; // 表示该位置已被遍历
bool res = true;
if(!g1[x][y]) res = false;
for(int i = 0; i < 4; ++i)
{
int a = x + dx[i], b = y + dy[i];
if(a >= n || a < 0 || b >= m || b < 0 || !g2[a][b]) continue;
if(!dfs(g1, g2, a, b)) res = false;
}
return res;
}
};C++代码实现 BFS实现
class Solution
{
public:
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
using PII = pair<int, int>;
int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2)
{
int res = 0;
int n = grid1.size(), m = grid1[0].size();
queue<PII> q;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < m; ++j)
{
if(!grid2[i][j]) continue;
q.emplace(i, j);
grid2[i][j] = 0; // 表示已经在队列中
bool flag = true;
while(q.size())
{
auto iter = q.front(); q.pop();
int x = iter.first, y = iter.second;
if(!grid1[x][y]) flag = false;
for(int k = 0; k < 4; ++k)
{
int a = x + dx[k], b = y + dy[k];
if(a >= n || a < 0 || b >= m || b < 0 || !grid2[a][b]) continue;
q.emplace(a, b);
grid2[a][b] = 0; // 表示已加入队列
}
}
queue<PII> empty;
swap(q, empty);
if(flag) ++res;
}
}
return res;
}
};时间复杂度
1906.查询差绝对值的最小值
题目链接: leetcode 1906. 查询差绝对值的最小值
一个数组 a 的 差绝对值的最小值 定义为：0 <= i < j < a.length 且 a[i] != a[j] 的 |a[i] - a[j]| 的 最小值。如果 a 中所有元素都 相同 ，那么差绝对值的最小值为 -1 。
比方说，数组 [5,2,3,7,2] 差绝对值的最小值是 |2 - 3| = 1 。注意答案不为 0 ，因为 a[i] 和 a[j] 必须不相等。
给你一个整数数组 nums 和查询数组 queries ，其中 。对于每个查询 i ，计算子数组 中 差绝对值的最小值 ，子数组 包含 nums 数组（下标从 0 开始）中下标在 li 和 ri 之间的所有元素（包含 li 和 ri 在内）。
请你返回 ans 数组，其中 ans[i] 是第 i 个查询的答案。
子数组 是一个数组中连续的一段元素。
|x| 的值定义为：
- 如果 x >= 0 ，那么值为 x 。
- 如果 x < 0 ，那么值为 -x 。
样例
示例1:
输入：nums = [1,3,4,8], queries = [[0,1],[1,2],[2,3],[0,3]]
输出：[2,1,4,1]
解释：查询结果如下：
- queries[0] = [0,1]：子数组是 [1,3] ，差绝对值的最小值为 |1-3| = 2 。
- queries[1] = [1,2]：子数组是 [3,4] ，差绝对值的最小值为 |3-4| = 1 。
- queries[2] = [2,3]：子数组是 [4,8] ，差绝对值的最小值为 |4-8| = 4 。
- queries[3] = [0,3]：子数组是 [1,3,4,8] ，差的绝对值的最小值为 |3-4| = 1 。
示例2:
输入：nums = [4,5,2,2,7,10], queries = [[2,3],[0,2],[0,5],[3,5]]
输出：[-1,1,1,3]
解释：查询结果如下：
- queries[0] = [2,3]：子数组是 [2,2] ，差绝对值的最小值为 -1 ，因为所有元素相等。
- queries[1] = [0,2]：子数组是 [4,5,2] ，差绝对值的最小值为 |4-5| = 1 。
- queries[2] = [0,5]：子数组是 [4,5,2,2,7,10] ，差绝对值的最小值为 |4-5| = 1 。
- queries[3] = [3,5]：子数组是 [2,7,10] ，差绝对值的最小值为 |7-10| = 3 。提示:
算法1 (前缀和)
思路分析
首先我们从提示入手, 我们发现虽然整个nums的长度虽然可以达到 级别, 但是 nums[i] 里每一个元素的值却只有 1 ~ 100的范围, 故对于一个询问，在[l, r]区间中, 我们可以从小到大依次枚举1 ~ 100 中的数在不在这个区间中, 用last记录上次枚举到的数, 若当前枚举到的数cur在这个区间中, 且 cur - last 的差值小于上次得到一组差值, 更新答案. 那么这个过程最重要的是如何快速地判断[l, r] 区间中 x 是否存在, 这里就用到了前缀和, 这里的前缀和用到的是个数前缀和, 用两维表示, 即表示的是在 nums数组的 1 ~ i 个数中数值j出现的次数. 那么判断一段区间[l, r]中是否存在x, 只需判断 - > 0， 若大于0说明[l, r]区间存在x, 否则在[l, r] 中不存在x。
C++ 代码
constexpr int N = 1e+5 + 10, M = 110;
int s[N][M];
class Solution
{
public:
vector<int> minDifference(vector<int>& nums, vector<vector<int>>& queries)
{
int n = nums.size(), m = queries.size();
// 预处理前缀和数组, 前缀和下标习惯从0开始
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= 100; ++j)
{
s[i][j] = s[i - 1][j];
// 若 nums[i - 1] == j, 1 ~ i中包含j的个数相比 s[i - 1][j] + 1
if(nums[i - 1] == j) ++s[i][j];
}
vector<int> res;
// 处理询问
for(int i = 0; i < m; ++i)
{
int l = queries[i][0] + 1, r = queries[i][1] + 1, last = -1, ans = M;
for(int j = 1; j <= 100; ++j)
if(s[r][j] - s[l - 1][j])
{
if(last != -1) ans = min(ans, j - last);
last = j;
}
if(ans == M) ans = -1;
res.push_back(ans) ;
}
return res;
}
};