又是一个安静的周末，又是一个水水的周赛

ACM算法日常

发布于 2021-07-16 16:12:58

2790

发布于 2021-07-16 16:12:58

文章被收录于专栏：ACM算法日常

本次周赛不难，随便水水就做完了，心情舒适

涉及知识点：小学数学，模拟，深度优先搜索，并差集，桶排序，高性能算法

字符串中的最大奇数

给定一个表示正整数的字符串 s，输出字符串中的最大奇数子字符串，如果不存在奇数，返回空字符串

题解

奇数的个位一定是奇数，所以从后往前遍历字符串 s，找到第一个奇数的位置即可，如果找不到，就意味着不存在奇数

class Solution {
public:
    string largestOddNumber(string num) {
        int pos = -1;
        for (int i = num.length() - 1; i >= 0; --i) {
            if ((num[i] - '0') % 2) {pos = i; break;}
        }
        if (pos == -1) return "";
        else return num.substr(0, pos + 1);
    }
};

你完成的完整对局数

一个小时中，有四个时间点会开始一场分钟的完整对局，分别是 HH:00, HH:15, HH:30, HH:45

现在给定两个 HH:MM 格式的时间，分别表示开始时间和终止时间，计算完成的完整对局数

注意，如果终止时间的 HH 小于开始时间的 HH，说明玩了通宵，也就是说，玩到了第二天

题解

直接 if 特判多种情况

class Solution {
public:
    int t1(int x) {return x % 15 ? (x / 15 + 1) * 15 : x;}
    int t2(int x) {return x / 15 * 15;}
    int numberOfRounds(string st, string ft) {
        int h1 = (st[0] - '0') * 10 + st[1] - '0';
        int h2 = (ft[0] - '0') * 10 + ft[1] - '0';
        int m1 = (st[3] - '0') * 10 + st[4] - '0';
        int m2 = (ft[3] - '0') * 10 + ft[4] - '0';
        if (h2 < h1 || h2 == h1 && m2 < m1) h2 += 24;
        int ans = 0;
        if (h1 == h2) {
            ans += (4 + (t2(m2) - t1(m1) / 15)) % 4;
        }
        else if (m1 && m2) {
            ans += max(0, h2 - (h1 + 1)) * 4 + (60 - t1(m1)) / 15 + t2(m2) / 15;
        }
        else if (m1 && !m2) {
            ans += max(0, h2 - (h1 + 1)) * 4 + (60 - t1(m1)) / 15;
        }
        else if (!m1 && m2) {
            ans += max(0, h2 - h1) * 4 + t2(m2) / 15;    
        }
        else {
            ans += (h2 - h1) * 4;
        }
        return ans;
    }
};

统计子岛屿

给定长和宽一致的两个 01 矩阵，分别表示两个地图，正如你所猜想的那样，其中的1表示陆地，0 表示水域，岛屿就是连着的 1组成的区域

对于矩阵 2 中的岛屿，如果他是矩阵 1 中岛屿的子区域，那么我们称之为子岛屿，现在要统计子岛屿的数量

如上所示，标红的区域就是子岛屿，一共有 3 个子岛屿

题解

const int DX[] = {0, 1, 0, -1};
const int DY[] = {1, 0, -1, 0};
class Solution {
public:
    bool check(int x, int y, int m, int n)
    {
        return x >= 0 && x < m && y >= 0 && y < n;
    }
    void dfs(int x, int y, vector<vector<int>>& vis, vector<vector<int>>& grid1, vector<vector<int>>& grid2, int& flag) {
        int m = grid2.size();
        int n = grid2[0].size();
        vis[x][y] = 1;
        if (grid1[x][y] != 1) flag = 0;
        for (int i = 0; i < 4; ++i) {
            int tx = x + DX[i], ty = y + DY[i];
            if (check(tx, ty, m, n) && !vis[tx][ty] && grid2[tx][ty] == 1) {
                if (grid1[tx][ty] != 1) {
                    flag = 0;
                }
                dfs(tx, ty, vis, grid1, grid2, flag);
            }
        }
    }
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        int m = grid2.size();
        int n = grid2[0].size();
        vector<vector<int>> vis(m, vector<int>(n));
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (!vis[i][j] && grid2[i][j] == 1) {
                    int flag = 1;
                    dfs(i, j, vis, grid1, grid2, flag);
                    if (flag) {
                        //cout << i << ' ' << j << endl;
                        ans++;
                    }
                }
            }
        }
        return ans;
    }
};

查询差绝对值的最小值

题解

class Solution {
public:
    vector<int> minDifference(vector<int>& n, vector<vector<int>>& q) {
        vector<vector<int>> b(n.size() + 1, vector<int>(101));
        for (int i = 1; i <= n.size(); ++i) {
            b[i][n[i - 1]]++;
            for (int j = 1; j <= 100; ++j) {
                b[i][j] += b[i - 1][j];
            }
        }
        vector<int> ans;
        for (auto &i: q) {
            int L = i[0] + 1, R = i[1] + 1;
            vector<pair<int, int>> B;
            for (int j = 1; j <= 100; ++j) {
                int cnt = b[R][j] - b[L - 1][j]; // j 出现的次数
                if (cnt > 0) B.push_back(pair<int, int> {j, cnt});
            }
            int pos = 0, temp = 101;
            for (int j = 0; j < B.size() - 1; ++j) {
                pair<int, int> x = B[j], y = B[j + 1];
                temp = min(temp, y.first - x.first);
            }
            if (B[0].first == B[B.size() - 1].first) temp = -1;
            ans.push_back(temp);
        }
        return ans;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-06-21，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自 ACM算法日常微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度