$LeetCode$ 第$ 246 $场周赛

比赛链接

A-字符串中的最大奇数

给你一个长度为 $n$​ 字符串 $num$​，表示一个大整数。请你在字符串 $num$​ 的所有非空子字符串中找出值最大的奇数，并以字符串形式返回。如果不存在奇数，则返回一个空字符串 “” 。（子字符串是字符串中的一个连续的字符序列）（$1 \le n \le 10^5$​​）

签到题，一个数是奇数还是偶数，只取决于它的最后一位是奇数还是偶数。因此我们可以从后往前枚举，找到第一个奇数（假设是第$i$位），则字符串前$i$位组成最大的奇数。

class Solution 
{
public:
    string largestOddNumber(string num) 
    {
        int n = num.length();
        
        int pos = 0;
        for (int i = n - 1; i >= 0; i--) // 找到最靠后的奇数
        {
            if ((num[i] - '0') % 2 == 1)
            {
                pos = i;
                break;
            }
        }
        
        // 将这个大整数的前i位取出来
        string Ans = "";
        for (int i = 0; i <= pos; i++)
            Ans += num[i];
        
        if (pos == 0 && (num[0] - '0') % 2 == 0)
            return "";
        else 
            return Ans;
    }
};

B-你完成的完整对局数

这个游戏在每小时的$00, 15, 30, 45$​​分钟时，会有一场开始一场对局（每局15分钟）。现在告诉你你进入游戏的时间和你退出游戏的时间，问你一共进行了几个完整的对局。（输入格式为$HH:MM$​，$24$​小时制，保证时间合法）

模拟题，可以先统计自己在游戏中度过了几个完整的小时，如果我们度过了$i$​​个完整的小时，那我们至少完成了$4\times i$​​个完整的对局。然后如果开头和结尾没有度过完整的一个小时，单独处理一下即可（用$if$​语句暴力写就行）。不过我这里，直接不管它开头结尾是不是满一个小时，我都单独去计算了，这样后果就是，如果开头和结尾在同一个小时中，就计算重复了。故而再次添加特判处理开头结尾在同一小时的情况。

class Solution 
{
public:
    int numberOfRounds(string startTime, string finishTime) 
    {
        // 将小时和分钟单独取出来，方便后面计算。
        int startH = (startTime[0] - '0') * 10 + (startTime[1] - '0');
        int endH = (finishTime[0] - '0') * 10 + (finishTime[1] - '0');
        int startM = (startTime[3] - '0') * 10 + (startTime[4] - '0');
        int endM = (finishTime[3] - '0') * 10 + (finishTime[4] - '0');
        
        int Ans = 0;
        // 这是开头和结尾在同一个小时中的情况。
        if (startH == endH && startM <= endM) 
        {
            int flag = 0;
            // 非常暴力，直接一分钟一分钟的度过，然后判断。
            for (int i = startM; i <= endM; i++)
            {
                if (flag == 1 && (i == 0 || i == 15 || i == 30 || i == 45 || i == 60))
                    Ans++;
                else if ((i == 0 || i == 15 || i == 30 || i == 45 || i == 60))
                    flag = 1;
            }
        }
        else 
        {
            // 单独处理开头。
            int flag = 0;
            for (int i = startM; i <=60; i++)
            {    
                if (flag == 1 && (i == 0 || i == 15 || i == 30 || i == 45 || i == 60))
                    Ans++;
                else if ((i == 0 || i == 15 || i == 30 || i == 45 || i == 60))
                    flag = 1;
            }
            
            // 计算中间有几个完整的一小时。
            if (startH < endH)
                Ans += max(0, (endH - startH - 1)) * 4;
            else
            {
                Ans += max(0, (24 - startH - 1)) * 4;
                Ans += max(0, (endH)) * 4;
            }
            
            // 单独处理结尾。
            for (int i = 0; i <= endM; i++)
            {
                if (flag == 1 && (i == 15 || i == 30 || i == 45 || i == 60))
                    Ans++;
                else if ((i == 0 || i == 15 || i == 30 || i == 45 || i == 60))
                    flag = 1;
            }   
        }
        
        return Ans;
    }
};

C-统计子岛屿

给你两个 $m \times n$​​​ 的二进制矩阵 $grid1$​​​ 和 $grid2$​​​，它们只包含 $0$​​​ （表示水域）和 $1$​​​ （表示陆地）。一个岛屿是由四个方向 （水平或者竖直）上相邻的 $1$​​​ 组成的区域。任何矩阵以外的区域都视为水域。如果 $grid2$​​​ 的一个岛屿，被 $grid1$​​​ 的一个岛屿 完全 包含，也就是说 $grid2$​​​ 中该岛屿的每一个格子都被 $grid1$​​​ 中同一个岛屿完全包含，那么我们称 $grid2$​​​ 中的这个岛屿为子岛屿 。而我们要求 $grid2$​​​ 中子岛屿的数目 。（$1 \le m,n \le 500$​）

搜索+模拟。

我采取了一个很暴力的做法，首先我对$grid1$​进行$dfs$​，并使用$vis1$​数组，把其中的不同岛屿标记上不同的数字。具体过程就是首先$vis1$​清零，随后由每一个$vis1$​为零且$grid1$​不为零的点开始$dfs$，将相邻的且$grid1$均为$1$的点，在$vis1$中标记为一个相同的整数。随后再对$grid2$​使用$dfs$​，并使用$vis2$​进行标记，不过在对$vis2$​进行标记的过程中，要不断和同位置上的$vis1$​进行比较，如果始终没有发现不同，则说明这是一个子岛屿。

由于两个 $m \times n$ 的矩阵中的每个点都最多被$dfs$访问一次，所以复杂度为$O(m \times n)$。

int vis1[510][510];
int vis2[510][510];

// 方向数组，便于dfs过程中确定下一个要求的点。
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int checkflag = 1;

class Solution 
{
private:
    int n;
    int m;
    
    void dfs1(int x,int y, vector<vector<int>>& grid1, int cnt)
    {
        // 标记。
        vis1[x][y] = cnt;
        
        for (int i = 0; i < 4; i++)
        {
            int newx = x + dx[i];
            int newy = y + dy[i];
            
            if (newx >= 0 && newx < n && newy >= 0 && newy < m)
            {
                // 去相邻的，grid1不为0且vis1不为0（即没被访问过的）。
                if (grid1[newx][newy] == 1 && !vis1[newx][newy])
                    dfs1(newx, newy, grid1, cnt);
            }
        }
    }
    
    void dfs2(int x,int y, vector<vector<int>>& grid2, int cnt)
    {
        vis2[x][y] = cnt;
        // 这说明在grid2中是1，但是在grid1中为0，必然不是子岛屿，故返回。
        if (vis1[x][y] == 0)
            checkflag = 0;
        
        for (int i = 0; i < 4; i++)
        {
            int newx = x + dx[i];
            int newy = y + dy[i];
            
            if (newx >= 0 && newx < n && newy >= 0 && newy < m)
            {
                if (grid2[newx][newy] == 1 && !vis2[newx][newy])
                    dfs2(newx, newy, grid2, cnt);
            }
        }
    }

public:
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) 
    {
        n = grid1.size();
        m = grid1[0].size();
        
        memset(vis1, 0, sizeof(vis1));
        memset(vis2, 0, sizeof(vis1));
        
        int count1 = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                // 对于每一个vis1不为0且grid1也不为零的点，dfs
                if (!vis1[i][j] && grid1[i][j] == 1)
                    dfs1(i, j, grid1, ++count1);
            }
        }
        
        int Ans = 0;
        int count2 = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (!vis2[i][j] && grid2[i][j] == 1)
                {
                    checkflag = 1;
                    dfs2(i, j, grid2, ++count2);
                    
                    if (checkflag)
                        Ans++;
                }
            }
        }
        
        return Ans;
    }
};

D-查询差绝对值的最小值

从给定的$n$​个数中任取两个不同的数，其之差的绝对值的最小值为这$n$​个数的差绝对值的最小值。现在给你一个长度为$n$​的数组$a$​，和$m$​个询问，每个询问给定一组$l, r$​，要求出对于每个询问，区间$l,r$​中数的差绝对值的最小值。（$1 \le n \le 10^5$​， $1 \le m \le 2\times 10^4$​，$1 \le a[i] \le 100$​）

直接暴力的话，最差复杂度得有$n^2 \times m$​​​​​了。如果我们每次可以快速获得一个排好序的$l,r$​​​​​区间，那后续计算的复杂度就变成最差$O(n)$​​​​​了，因为只需要比较每一对相邻两数的差就可以了。当然这样就算我们可以$O(1)$​​获得排好序的区间，总复杂度仍有$O(n \times m)$​​，我们依旧接受不了，还要再优化。这时候我们发现：题目说数的范围仅$[1,100]$​​。这不就说明，如果我们可以快速获得一个去重且排好序的$l,r$​​区间，那么后续计算复杂度就变成了最差$O(100)$​​​​了，便可以接受了。

那么现在的任务是快速获得一个去重且排好序的$l,r$​​​​​​区间，其实这个也很容易，答案是利用二分。（自从发现自己屡次手写二分出$bug$​​​​​​改半天改不完后，我就暂时放弃了使用C#写算法题，回归了C++）我们可以开一个vector Count[101]，其中$Count[i]$​​​​用来记录数字$i$​​​​都出现在了哪些位置。这样当我们面对一个询问区间$l, r$​​​​，我们可以从$1\sim100$​​​​枚举数字$i$​​​​，因为我们是按顺序将每个数字出现的位置存到$Count$​​​​中的，故而可以对$Count[i]$​​​​二分查找其中有没有属于$[l,r]$​​​​的数，如果有，则说明数字 $i$​​​​ 在$[l,r]$​​​​中。我们可以另一个vector CompareA存储下所有这样的$i$​​​，显然在$CompareA$​​中最多只有$100$​​​​​​个数，然后暴力计算$CompareA$中数的差的绝对值的最小值，即为询问$[l,r]$的答案。

vector<int> Count[101];
vector<int> CompareA;
vector<int> Ans;

class Solution 
{
public:
    vector<int> minDifference(vector<int>& nums, vector<vector<int>>& queries) 
    {
        for (int i = 0; i <= 100; i++) Count[i].clear();
        int n = nums.size();
        // 记录下每个数字出现的位置
        for (int i = 0; i < n; i++)
            Count[nums[i]].push_back(i);
        
        Ans.clear();
        int m = queries.size();
        for (int i = 0; i < m; i++)
        {
            int l = queries[i][0], r = queries[i][1];
            
            CompareA.clear();
            for (int i = 1; i <= 100; i++)
            {
                if (Count[i].size() != 0)
                {
                    int pos = lower_bound(Count[i].begin(), Count[i].end(), l) - Count[i].begin(); 
                    
                    // 这说明数字i存在于[l,r]中
                    if (pos < Count[i].size())
                    {
                        if (Count[i][pos] >= l && Count[i][pos] <= r)
                            CompareA.push_back(i);
                    }
                }
            }
            
            int ans = 0x3f3f3f3f;
            if (CompareA.size() == 1)
                ans = -1;
            for (int i = 1; i < CompareA.size(); i++)
                ans = min(ans, CompareA[i] - CompareA[i - 1]);
            
            Ans.push_back(ans);
        }
        
        return Ans;
    }
};