leetcode 第 246 场算法比赛

零、背景

这次打比赛录了视频，差点翻车，还好最后都做出来了。

第一题签到题，第二题模拟题，第三题搜索题，第四题我是按统计题水过去的。

一、字符串中的最大奇数

题意：给一个字符串大整数，求最大的奇数子串。

思路：奇数只要求最后一位是奇数，所以答案肯定是某个前缀。
想要奇数最大，前缀需要更长一些。
所以只需要从后到前找到第一个奇数，取前缀即可。

二、你完成的完整对局数

题意：每轮游戏都是从整点时刻开始（0分、15分、30分、45分为整点时刻）。
给一个开始时间和结束时间，问可以完整经历几轮游戏。

分析：首先是理解题意，边界如何处理。
题目给了一个例子，结束时间是 05:59 时，最后一个时刻不算完整的游戏。 所以这里可以理解为 05:59 代表 05:59:00，最后一分钟还处于游戏中，所以不算一轮完整的游戏。

思路1：模拟，不断找到下个时刻其实时间，判断当前一轮是否完整。
由于有时间回退的数据，所以还需要特殊判断时间是否是回退 还是游戏结束。
情况比较复杂。

思路2：时间转化为时间轴，时间线对齐到整点时刻，计算有多少个整点时刻即可。

int numberOfRounds(string& startTime, string& finishTime) {
    int s = Trans(startTime);
    int e = Trans(finishTime);
    if(s > e) {
        e += 24 * 60;
    }
    
    if(s % 15 > 0){
        s += 15 - s % 15;
    }
    if(e % 15 > 0){
        e -= e % 15;
    }
    return (e - s)/15;
}

三、统计子岛屿

题意：给两个地图，有若干岛屿，问右边地图的岛屿里面，有多少岛屿被左边地图的岛屿覆盖。
覆盖定义：右边地图的一个岛屿的所有坐标，在左边地图里，也都是陆地。

思路：DFS 搜索即可。

一种比较清晰的思路是分两个函数，一个判断函数，一个清空岛屿函数。
我两个函数合在一起了。

关键代码：发现岛屿不满足要求时，需要继续递归，清空所有相连的岛屿。

PS：这里差点翻车了。输入是整数，我理解成字符串了。

int Dfs(int x, int y){
    if(x < 0 || y < 0 || x >= n || y >= m) return 0;
    if(grid2[x][y] == 0) return 0;
    
    int ans = 1;
    grid2[x][y] = 0;
    
    if(grid1[x][y] == 0) {
        ans = -1;
    }
    
    
    for(int i = 0; i < 4; i++){
        int X = x + dir[i][0];
        int Y = y + dir[i][1];
        int v = Dfs(X, Y);
        if(v == -1 || ans == -1){
            ans = -1;
            continue;
        }
        ans += v;
    }
    
    return ans;
}

int ans = 0;
for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
        if(grid2[i][j] == 1){
            if(Dfs(i, j) > 0){
                ans++;
            }
            
        }
    }
}
return ans;

四、查询差绝对值的最小值

题意：给一个数组。
差绝对值的最小值的定义：数组中所有元素之间的差绝对值的最小值。
特殊情况：如果所有值都相等，则差绝对值的最小值按 -1 处理。

现在给一堆子数组的起始位置和结束位置，求这些子数组的差绝对值的最小值。

分析：看数据范围，数组最大为10^5个，子数组个数为2 * 10^4 个。
比较特殊的是数组的值最大为 100。
所以这道题的突破口就在数组的值这里了。

预先统计出所有前缀数组值的集合与个数，最多 100 个。

求一个子数组的差绝对值的最小值时，我们只需要关心不同值之间的差值。
所以通过两个前缀统计求差积，就可以找到当前子数组的所有值的统计结果。

差绝对值最小时，显然可以看出来相邻的数字差最小。
所以我们只需要求相邻数字的差值即可。

原先我使用 vector<map> 做的这道题，超时了。
后来改成二维数组后，就通过了。

使用 vector<vector> 也许也可以通过吧。

五、最后

这次比赛的题整体偏简单，最后一题我使用暴力的方法水过去了。

不知道标准的做法是什么，你是怎么做的呢？

加油，算法人。

《完》

-EOF-

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