力扣381周赛

本文主要是介绍力扣381周赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

力扣第381场周赛

输入单词需要的最少按键次数 I

贪心模拟

class Solution {
public:int minimumPushes(string word) {int n = word.size() , ans = 0;for(int i = 0 ; i < n ; i ++){if(i >= 0 && i <= 7)ans += 1;else if(i >= 8 && i < 16)ans += 2;else if(i >= 16 && i < 24)ans += 3;else ans += 4;}return ans;}
};

按距离统计房屋对数目 I

跑一边floyd然后对每两个点统计

class Solution {
public:vector<int> countOfPairs(int n, int x, int y) {vector<vector<int> >d(n + 1 , vector<int>(n + 1));vector<int> ans(n);for(int i = 1 ; i <= n  ; i ++){for(int j = 1 ; j <= n ; j ++){if(i == j)d[i][j] = 0;else d[i][j] = 1e9;}}for(int i = 1 ; i < n ; i ++){d[i][i + 1] = d[i + 1][i] = 1;}if(x != y) d[x][y] = d[y][x] = 1;for (int k = 1; k <= n; k ++ )for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )d[i][j] = min(d[i][j], d[i][k] + d[k][j]);for(int i = 1 ; i <= n ; i ++){for(int j = 1 ; j <= n ; j ++){if(d[i][j] - 1 >= 0)ans[d[i][j] - 1]++;}}return ans;}
};

输入单词需要的最少按键次数 II

在I的基础上价格哈希表即可

class Solution {
public:int minimumPushes(string word) {map<char,int> m;int n = word.size() , ans = 0;vector<int> v(30);for(auto x: word){m[x] ++;}int i = 1;for(auto [x , y] : m){v.push_back(y);}sort(v.begin() , v.end());reverse(v.begin() , v.end());for(auto y : v){if(i >= 1 && i <= 8)ans += y;else if(i >= 9 && i <= 16)ans += (2 * y);else if(i > 16 && i <= 24)ans += (3 * y);else ans += (4 * y);i ++;}return ans;}
};

按距离统计房屋对数目 II

分类讨论

class Solution {
public:vector<long long> countOfPairs(int n, int X, int Y) {if (X > Y) swap(X, Y);vector<long long> ans(n + 1);// 情况三：计算长度为 len 的链内部的贡献auto inner = [&](int len) {for (int i = 1; i <= len; i++) ans[i] += (len - i) * 2;};if (X == Y) {// 没有环的特殊情况inner(n);ans.erase(ans.begin());return ans;}// 情况二：计算元素值为 2，第一个窗口的开头为 L，最后一个窗口的开头为 R 的滑动窗口的贡献auto gao = [&](int L, int R, int len) {// 用差分数组维护滑动窗口经过的值long long delta[n + 2];memset(delta, 0, sizeof(delta));for (int i = L; i <= R; i++) delta[i] += 4, delta[i + len] -= 4;long long now = 0;// 求差分数组前缀和，即可得到对每个距离的贡献for (int i = L; i < R + len; i++) {now += delta[i];ans[i] += now;}};int len = Y - X + 1;vector<int> chains;//链的长度if (n - Y > 0) chains.push_back(n - Y);if (X > 1) chains.push_back(X - 1);if (len & 1) {// 环长为奇数// 情况一：计算环内部的贡献for (int i = 1; i <= len / 2; i++) ans[i] += len * 2;// 情况二：计算一个点在环，一个点在链的贡献for (int c : chains) gao(2, c + 1, len / 2);} else {// 环长为偶数// 情况一：计算环内部的贡献for (int i = 1; i < len / 2; i++) ans[i] += len * 2;ans[len / 2] += len;// 情况二：计算一个点在环，一个点在链的贡献for (int c : chains) {gao(2, c + 1, len / 2 - 1);for (int i = 1; i <= c; i++) ans[i + len / 2] += 2;}}// 情况三：计算链内部的贡献int sm = 2;for (int c : chains) sm += c;inner(sm);// 扣除重复计算的贡献ans[1] -= 2;for (int i = Y + 1; i <= n; i++) ans[i - Y + 1] -= 2;for (int i = X - 1; i > 0; i--) ans[X - i + 1] -= 2;ans.erase(ans.begin());return ans;}
};

–

这篇关于力扣381周赛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---