上分掉分，不过一念之间罢

ACM算法日常

发布于 2021-12-06 15:59:43

4790

发布于 2021-12-06 15:59:43

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

久违的双周赛和单周赛连开。

开局以为上大分，结束之后掉大分，人生如戏罢！

涉及知识点：模拟，贪心，曼哈顿距离，前缀和，图论，搜索，分层图

双周赛 66

统计出现过一次的公共字符串

给定两个字典

w_1,\ w_2

，计算在两个字典中只出现一次的公共字符串个数

题解

维护两个哈希表，一个去重的集合即可，时间复杂度为

\mathcal{O}(|w_1| + |w_2|)

// cpp
class Solution {
public:
    int countWords(vector<string>& w1, vector<string>& w2) {
        set<string> st;
        map<string, int> mp1, mp2;
        for (auto& i: w1) mp1[i]++, st.insert(i);
        for (auto& i: w2) mp2[i]++, st.insert(i);
        int ans = 0;
        for (auto& i: st) if (mp1[i] == 1 && mp2[i] == 1) ans++;
        return ans;
    }
};

从房屋收集雨水需要的最少水桶数

给定只含有 H 和 . 的字符串，前者表示房屋，后者表示空地

现在可以在空地放水桶，位置 i 的水桶可以服务 i - 1, i + 1 位置的房屋

请计算每个房屋都被水桶服务的情况下，放置的最少的水桶数，如果始终没法满足所有的房屋，返回 -1

字符串长度不超过

10^5

题解

先计算能够服务两个房屋的水桶位置，再去放置剩下的水桶，维护水桶的个数

用 mark 数组标记每个房屋被服务的情况，最后遍历 mark 数组，如果有一个房子没被服务，就返回 -1，否则返回水桶的个数，时间复杂度为

\mathcal{O}(n)

// cpp
class Solution {
public:
    int minimumBuckets(string s) {
        int n = s.size(), ans = 0;
        vector<int> mark(n);
        for (int i = 1; i < n - 1; ++i) {
            if (s[i] != '.') continue;
            if (s[i - 1] == 'H' && s[i + 1] == 'H' && !mark[i - 1] && !mark[i + 1]) {
                ans++;
                mark[i - 1] = mark[i + 1] = 1;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (s[i] != '.') continue;
            if (i + 1 < n && s[i + 1] == 'H' && !mark[i + 1]) {
                mark[i + 1] = 1;
                ans++;
            }
            else if (i - 1>= 0 && s[i - 1] == 'H' && !mark[i - 1]) {
                mark[i - 1] = 1;
                ans++;
            }
        }
        for (int i = 0; i < n; ++i) if (s[i] == 'H' && !mark[i]) return -1;
        return ans;
    }
};

网格图中机器人回家的最小代价

给定

m\times n

的网格，机器人位于

(x,\ y)

，目标前往

(a,\ b)

机器人可以上下左右移动，给定 row, col 数组，每移动到 i 行，消耗 row[i] 体力，每移动到 j 列，消耗 col[j] 体力

计算机器人到达目标的最小消耗体力

数据规定

1\leq m,\ n\leq 10^5

题解

这个数据范围，不可能搜索；上下左右行动，不可能动态规划

非常容易证明，最小消耗一定是曼哈顿路径上的消耗，那么直接按照曼哈顿路径计算就行，时间复杂度

\mathcal{O}(m + n)

// cpp
class Solution {
public:
    int minCost(vector<int>& startPos, vector<int>& homePos, vector<int>& rowCosts, vector<int>& colCosts) {
        int ans = 0;
        int x = startPos[0], y = startPos[1];
        int a = homePos[0], b = homePos[1];
        for (int i = min(x, a); i <= max(x, a); ++i) ans += rowCosts[i];
        for (int i = min(y, b); i <= max(y, b); ++i) ans += colCosts[i];
        ans -= rowCosts[x], ans -= colCosts[y];
        return ans;
    }
};

统计农场中肥沃金字塔的数目

给定

m\times n

的

0,\ 1

网格，统计其中由全

组成的正金字塔和倒金字塔的数量

数据规定

1\leq m,\ n\leq 10^3,\ m\cdot n\leq 10^5

题解

先维护一下每一行的前缀和

然后暴力遍历每个位置，再枚举行，依据行的子段和是否满足要求，以此判断是否构成正金字塔

倒金字塔同理，时间复杂度为

\mathcal{O}(m^2\cdot n)

看了看题解区，也可以用动态规划优化到

\mathcal{O}(m\cdot n)

// cpp
class Solution {
public:
    int countPyramids(vector<vector<int>>& g) {
        int m = g.size(), n = g[0].size();
        vector<vector<int>> sum(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                sum[i][j] = sum[i][j - 1] + g[i - 1][j - 1];
            }
        }
        int ans = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (g[i - 1][j - 1] == 0) continue;
                for (int k = i + 1; k <= m; ++k) {
                    int val = k - i;
                    if (j + val > n || j - val < 1) break;
                    if (sum[k][j + val] - sum[k][j - val - 1] != 2 * val + 1) break;
                    ans++;
                }
                for (int k = i - 1; k >= 1; --k) {
                    int val = i - k;
                    if (j + val > n || j - val < 1) break;
                    if (sum[k][j + val] - sum[k][j - val - 1] != 2 * val + 1) break;
                    ans++;
                }
            }
        }
        return ans;
    }
};

单周赛 269

找出数组排序后的目标下标

给定无序数组 a 和一个目标值 tar，返回 a 排序后所有等于 tar 的下标

题解

排序后遍历

// cpp
class Solution {
public:
    vector<int> targetIndices(vector<int>& nums, int tar) {
        sort(nums.begin(), nums.end());
        vector<int> vec;
        for (int i = 0; i < nums.size(); ++i) if (nums[i] == tar) vec.push_back(i);
        return vec;
    }
};

半径为 k 的子数组平均值

给定数组 a，给定半径 k，对于一个位置 i，计算 [i - k, i + k] 里面元素的平均值，向下取整，如果边界溢出，返回 -1

题解

预处理前缀和之后扫描即可，时间复杂度

\mathcal{O}(n)

// cpp
class Solution {
public:
    vector<int> getAverages(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long long int> sum(n + 1);
        vector<int> ans(n);
        for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + nums[i - 1];
        for (int i = 1; i <= n; ++i) {
            if (i - k < 1 || i + k > n) ans[i - 1] = -1;
            else ans[i - 1] = (sum[i + k] - sum[i - k - 1]) / (2 * k + 1);
        }
        return ans;
    }
};

从数组中移除最大值和最小值

给定数组 a，每次操作只能移除头或尾一个元素，请你返回将最大值和最小值都移除的最小操作数

题解

先找到最大值和最小值的位置，不妨记为 p1, p2, p1 <= p2

考虑最后数组的状态，一定是一个子数组，因此我们有三种方式移除

从左往右移除，直到 p2 被移调
从右往左移除，直到 p1 被移调
移除 p1 左边的，移除 p2 右边的

三种操作取最小值即可，时间复杂度为

\mathcal{O}(n)

// cpp
class Solution {
public:
    int minimumDeletions(vector<int>& nums) {
        int maxx = INT_MIN, mini = INT_MAX, n = nums.size();
        int p_1 = -1, p_2 = -1;
        for (int i = 0; i < n; ++i) {
            if (nums[i] > maxx) maxx = nums[i], p_1 = i + 1;
            if (nums[i] < mini) mini = nums[i], p_2 = i + 1;
        }
        int ans = 0;
        int p1 = min(p_1, p_2), p2 = max(p_1, p_2);
        ans = min(p1 + n - p2 + 1, min(p2, n - p1 + 1));
        return ans;
    }
};

找出知晓秘密的所有专家

给定 n 个专家，给定 m 个关系

对于每一个关系 [a, b, c]，表示 a, b 专家在 c 时间交谈

现在有一个秘密，如果专家 i 在 x 时间听到这个秘密，他就可以瞬间告诉其他与他正在交谈的专家

现在专家 0 告诉了专家 f，请你计算最终有多少个专家知道了秘密

数据规定

2\leq n,\ m,\ c\leq 10^5

题解

考虑先把关系按照时间戳从小到大排序，之后可以按照时间戳进行一个分组

对于同一时间段，我们可以根据关系建图并做图搜索，起点是已经知道秘密且在图上的专家

本质上是一个分层图搜索问题，时间复杂度为

\mathcal{O}(n\log n + m + n)

，前一部分是排序的复杂度，后一部分是图搜索的复杂度

// cpp 17
class Solution {
    set<int> group;
    map<int, unordered_map<int, vector<int>>> mp;
public:
    void dfs(int u, int tm) {
        for (auto& i: mp[tm][u]) {
            if (group.find(i) == group.end()) {
                group.insert(i);
                dfs(i, tm);
            }
        }
    }
    vector<int> findAllPeople(int n, vector<vector<int>>& m, int f) {
        group.insert(0), group.insert(f);
        for (auto& i: m) { // 根据时间戳构建分层图，用 map<int, vector<int>> 存图
            mp[i[2]][i[0]].push_back(i[1]);
            mp[i[2]][i[1]].push_back(i[0]);
        }
        for (auto& [x, y]: mp) { // 根据时间戳遍历分层图
            for (auto& [a, b]: y) { // 如果起点已经被感染，就 dfs
                if (group.find(a) != group.end()) {
                    dfs(a, x);
                }
            }
        }
        vector<int> ans(group.begin(), group.end());
        return ans;
    }
};

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

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

机器人

编程算法

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

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

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

机器人

编程算法

登录后参与评论

0 条评论

热度