在线开发网站建设,网站干什么的,网站设计与优化,响应式网站模板免费文章目录 1. 题目来源2. 题目解析 1. 题目来源
链接#xff1a;3096. 得到更多分数的最少关卡数目
2. 题目解析
比较有意思的题目#xff0c;仔细读题后发现解题没啥难度#xff0c;但是如何写好、写的更简洁需要注意下#xff1a;
思路#xff1a;
数据量 1e5#… 文章目录 1. 题目来源2. 题目解析 1. 题目来源
链接3096. 得到更多分数的最少关卡数目
2. 题目解析
比较有意思的题目仔细读题后发现解题没啥难度但是如何写好、写的更简洁需要注意下
思路
数据量 1e5肯定不能两层循环了。那就需要在每个数组下标查询时都需要知道 A、B 的得分。得分0 扣分1 加分。当查询下标 i 时i 下标从 0 开始先暂定 i1 这段都能得分那么现在只需要得到我的扣分项即可算出最终得分。即只需要统计下标 i 位置之前的所有的 0 的个数作为扣分项i 1 这个数组长度就是我的得分但这里是包含了 0 的这些扣分的这些位置的得分是无效的所以需要减去 2 倍的 0 的个数即减去无效得分、减去真是扣分即算出来最终的得分情况。前后缀均可这样计算。
坑点
bob 必须要操作所以 i n-1。这里还 WA 一次… 没看到题目说明… 时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) O(1) O(1) class Solution {
public:int minimumLevels(vectorint possible) {int n possible.size();possible[0] possible[0] 0;for (int i 1; i n; i ) {if (possible[i] 0) possible[i] 1;else possible[i] 0;possible[i] possible[i - 1];}for (int i 0; i n - 1; i ) {if (i 1 - 2 * possible[i] n - i - 1 - 2 * (possible[n - 1] - possible[i])) {return i 1;}}return -1;}
};
