LeetCode第 70 场双周赛
2022/1/23 6:06:38
本文主要是介绍LeetCode第 70 场双周赛,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
5971. 打折购买糖果的最小开销
题目描述:给你\(n\)个糖果的价格,每买两种价格的糖果,可以获得一种不超过买的两种价格的糖果,问最少需要花费多少钱才能获得所有种类的糖果。
思路:贪心,将糖果价格从小到大排序,即所有糖果的价格和为\(sum\),然后倒着每三个就从\(sum\)中减去当前糖果的价格。
时间复杂度:\(O(nlogn)\)
参考代码:
class Solution { public: int minimumCost(vector<int>& cost) { sort(cost.begin() , cost.end()); int n = cost.size() , res = 0; for(int c : cost) res += c; for(int i = n - 3 ; i >= 0 ; i -= 3){ res -= cost[i]; } return res; } };
5972. 统计隐藏数组数目
题目描述:有一个数组\(arr\),其长度为\(n + 1\),现在告诉你其每相邻元素的差值组成的数组differences
,其中\(differences_i = arr_i - arr_{i - 1} \;2 \leq i \leq n + 1\)。并告诉你数组\(arr\)的元素的范围,即\(lower \leq arr_i \leq upper , 1 \leq i \leq n + 1\)。让你计算符合要求的数组arr
的数量。
思路:显然对于第一个元素,其范围为\([lower , upper]\),令lr = lower , rs = upper
我们遍历differences
数组,每次根据差值更新当前元素的值的范围,若当前范围超过了给定范围就返回0
,否则一直模拟下去,最终答案为rs - lr + 1
。
时间复杂度:\(O(n)\)
参考代码:
class Solution { public: int numberOfArrays(vector<int>& differences, int lower, int upper) { int lr = lower , rs = upper; for(auto diff : differences){ int newlr = lr + diff, newrs = rs + diff; if(newlr > upper || newrs < lower) return 0; lr = max(newlr , lower); rs = min(newrs , upper); } return rs - lr + 1; } };
5973. 价格范围内最高排名的 K 样物品
题目描述:自己看题目吧。
思路:根据题意BFS
即可,然后将存储的答案按照题目给定的优先级排序,最终得到前k
个的答案并返回即可。
时间复杂度:\(O(n\times m + (n \times m) log(n\times m))\) 前者是BFS
的复杂度,后者是排序的最坏复杂度。
参考代码:
class Solution { private: struct Node{ int x , y , step; Node(int _x = 0, int _y = 0, int _step = 0):x(_x) , y(_y) , step(_step){} }; public: vector<vector<int>> highestRankedKItems(vector<vector<int>>& grid, vector<int>& pricing, vector<int>& start, int k) { vector<vector<int>>res; int n = grid.size() , m = grid[0].size(); const int xd[4] = {0 , 0 , 1 , -1}; const int yd[4] = {1 , -1 , 0 , 0}; int low = pricing[0] , up = pricing[1]; queue<Node> q; q.push({start[0] , start[1] , 0}); vector<vector<bool>>vis(n , vector<bool>(m , false)); vis[start[0]][start[1]] = true; while(!q.empty()){ auto [x , y , step] = q.front(); q.pop(); if(grid[x][y] != 1 && grid[x][y] >= low && grid[x][y] <= up) res.push_back({step , grid[x][y] , x , y}); for(int i = 0 ; i < 4 ; ++i){ int dx = x + xd[i] , dy = y + yd[i]; if(dx < 0 || dx >= n || dy < 0 || dy >= m || grid[dx][dy] == 0 || vis[dx][dy]) continue; vis[dx][dy] = true; q.push({dx , dy , step + 1}); } } sort(res.begin(),res.end() , [&](const vector<int>& a , const vector<int>& b){ if(a[0] != b[0]) return a[0] < b[0]; if(a[1] != b[1]) return a[1] < b[1]; if(a[2] != b[2]) return a[2] < b[2]; return a[3] < b[3]; }); vector<vector<int>>ans; int len = res.size(); for(int i = 0 ; i < min(k , len) ; ++i) ans.push_back({res[i][2] , res[i][3]}); return ans; } };
5974. 分隔长廊的方案数
题目描述:有一个字符串\(s\),只含有s , p
两种字符,让你将字符串分割成非空子串,使得每一个子串都含有恰好两个s
字符,问分割方案数。
思路:我们只需要统计每两组s
字符中间的p
字符个数,然后根据乘法原理将其加一再全部乘起来即可。例如sspppssppss
,对于前面两组s
中间有3个p
字符,对于后面两组s
之间有2个p
字符,故最终的分割方案数为(3 + 1) * (2 + 1) = 12
种。
注意特判s
为奇数和不足两个的情况。
时间复杂度:\(O(n)\),\(n\)为字符串长度
参考代码:
class Solution { public: int numberOfWays(string s) { int cnt = 0; for(auto c : s) cnt += c == 'S'; if((cnt & 1) || cnt < 2) return 0; int res = 1, ct = 1; cnt = 0; const int mod = 1e9 + 7; for(auto c : s){ if(c == 'S'){ if(cnt < 2) ++cnt; else{ res = 1ll * res * ct % mod; ct = 1; cnt = 1; } } else{ if(cnt < 2) continue; else ++ct; } } return res; } };
这篇关于LeetCode第 70 场双周赛的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望
- 2024-05-29五款扩展组件齐发 —— Volcano、Keda、Crane-scheduler 等,邀你体验
- 2024-05-29AutoMQ 对象存储数据高效组织的秘密: Compaction
- 2024-05-29活动预告|来 GIAC 大会听大数据降本利器:AutoMQ 基于云原生重新设计的 Kafka