网站前台开发由什么做的,邢台核酸检测点,如何把自己电脑做网站服务器吗,如何制作一部动漫文章目录 复盘与一周总结2967. 使数组成为等数数组的最小代价#xff08;中位数贪心 回文数判断#xff09;2968. 执行操作使频率分数最大#xff08;中位数贪心 前缀和 滑窗#xff09; 复盘与一周总结
wa穿了第3题#xff0c;赛时其实想到了思路#xff1a;中位数贪心… 文章目录 复盘与一周总结2967. 使数组成为等数数组的最小代价中位数贪心 回文数判断2968. 执行操作使频率分数最大中位数贪心 前缀和 滑窗 复盘与一周总结
wa穿了第3题赛时其实想到了思路中位数贪心从中位数开始用左右指针找到第一个回文数与该回文数的代价就是答案。但是没有考虑到左右指针同时找到回文数的情况wa了一发之后开始改。用一个vector保存代价只要数组长度大于2就返回其中的较小值。但是没有注意到自己的算法是左右指针同时找可能出现同一个指针找到两次回文数的情况此时就不是左右指针分别找到一次回文数。后面改成数组长度大于5就返回最小值才ac赛后重写用第一次的思路写了一遍很快就ac了 现在想想自己能很快想到正解但是算法实现的却不是正解而且赛时还没发现甚至以为是思路错了还往平均数那块想了会。只能说自己在算法实现这块考虑得不仔细吧下次别着急想慢点 至于说第4题赛时完全没有想到中位数贪心想到哪了呢我在考虑数组中数的出现次数出现次数更多的数最后的代价是否会小于出现次数更小的数。甚至想到若一个数出现次数超过一半那么把所有数变为这个数此时的频率是否最大接着就对着这个贪心结论证啊证最后不了了之。但题目的关键点是操作次数有限那么就要考虑如何操作能尽可能少的使用操作次数这样就能想到中位数了
周末这几场打下来发现自己最大的问题就是题意的理解。一是读假题连题目在说什么都没搞清楚甚至是自以为搞清楚然后自欺欺人地想算法去了如abc的E题小白赛的E题。二是没有抓住题意的重点只要是稍有难度的题都需要抓住关键点不断地分析如这次的第4题小白赛的F题
问题反而是出现在阅读理解上
2967. 使数组成为等数数组的最小代价中位数贪心 回文数判断
2967. 使数组成为等数数组的最小代价 - 力扣LeetCode 根据中位数贪心将数组排序后从中位数开始分别向左和向右找到第一个回文数并计算代价数组两个代价中较小的即可
class Solution {
public:bool f(string s){int l 0, r s.size() - 1;while (l r){if (s[l] ! s[r]) return false;l , r -- ;}return true;}long long minimumCost(vectorint nums) {sort(nums.begin(), nums.end());int mid;if (nums.size() 1) mid nums[nums.size() / 2];else mid (nums[nums.size() / 2] nums[nums.size() / 2 - 1]) / 2;long long ans1 4e18, ans2 4e18;int l mid, r mid;while (l 0){if (f(to_string(l))){long long t 0;for (int i 0; i nums.size(); i) t abs(nums[i] - l);ans1 t;break;}l -- ;}while (r 2e9){if (f(to_string(r))){long long t 0;for (int i 0; i nums.size(); i) t abs(nums[i] - r);ans2 t;break;}r ;}return min(ans1, ans2);}
};2968. 执行操作使频率分数最大中位数贪心 前缀和 滑窗
2968. 执行操作使频率分数最大 - 力扣LeetCode 要使将数组中的某些数变成同一个数的代价最小依然是中位数贪心 同时这个序列必须是原序列的一段连续区间。比如原数组为1234将123变为2的代价一定比124变为2的代价小 题目要返回代价小于等于k的情况下最长的连续区间对于连续区间问题自然想到滑动窗口 那么接下来要考虑的是窗口滑动时的代价变化除了 O ( n ) O(n) O(n)暴力求代价还能使用前缀和进行预处理 O ( 1 ) O(1) O(1)地求代价
class Solution {
public:int maxFrequencyScore(vectorint nums, long long k) {sort(nums.begin(), nums.end());int n nums.size();vectorlong long a(n 1), s(n 1);for (int i 0; i n; i) a[i 1] nums[i], s[i 1] s[i] a[i 1];auto f [](int l, int mid, int r) - long long{long long left (mid - l) * a[mid] - (s[mid - 1] - s[l - 1]);long long right (s[r] - s[mid - 1]) - (r - mid 1) * a[mid];return left right;};int l 1, r 1;int ans 0;while (r n){while (f(l, (l r) / 2, r) k) l ;ans max(ans, r - l 1);r ;}return ans;}
};
