网站名词排名怎么做,初创企业网站建设流程,电子商务静态网页设计,模仿建设网站是侵权吗题目列表
3184. 构成整天的下标对数目 I
3185. 构成整天的下标对数目 II
3186. 施咒的最大总伤害
3187. 数组中的峰值
一、构成整天的下标对数目 I II 可以直接二重for循环暴力遍历出所有的下标对#xff0c;然后统计符合条件的下标对数目返回。代码如下
class So…题目列表
3184. 构成整天的下标对数目 I
3185. 构成整天的下标对数目 II
3186. 施咒的最大总伤害
3187. 数组中的峰值
一、构成整天的下标对数目 I II 可以直接二重for循环暴力遍历出所有的下标对然后统计符合条件的下标对数目返回。代码如下
class Solution {
public:int countCompleteDayPairs(vectorint hours) {int n hours.size(), ans 0;for(int i 0; i n; i) {for(int j 0; j i; j){if((hours[i]hours[j])%240)ans;}}return ans;}
};
能不能优化呢或者说能否去掉一层循环用一次遍历计算出答案
我们来思考一下内层循环的作用是什么就是看前面的数字能否和当前数字能否组成能被24整除的数也就是说只要我们在遍历的同时统计满足加起来能被24的整除的数的出现次数就能在O(1)的时间内得到与当前数字匹配的数字个数从而降低时间复杂度。
如何得知两个数加起来能被24整除只要知道它们的%24的值即可比如一个数%2420那么我们只要找%244的数字即可故代码如下
class Solution {
public:int countCompleteDayPairs(vectorint hours) {int cnt[24]{};int ans 0;for(auto x:hours) {ans cnt[(24-x%24)%24]; // (24-x%24)%24 用来计算另一个数%24的余数为了防止出现24-0 24 的情况故需要(...)%24cnt[x%24];}return ans;}
};
二、施咒的最大总伤害 先将数组排序这样我们从前往后选咒语只要考虑当前咒语伤害是否大于前一个选择的咒语2即可当然咒语伤害相同可以同时被选中所以我们还可以统计伤害相同的咒语的出现次数然后将数组去重。最终我们只要考虑当前咒语伤害是否大于前一个选择的咒语2即可。
状态定义f[i]表示前i个咒语中能得到的最大伤害
状态转移方程
选当前咒语f[i] f[j] cnt[x]*xx power[i]f[j]为满足power[j] 2 power[i]的最接近当前位置的值不选当前咒语f[i] f[i-1]
故 f[i] max( f[i-1]f[j] cnt[x]*x)在遍历 j 的时候我们不用每次都从头开始j 只会变大有点类似滑动窗口
代码如下
class Solution {using LL long long;
public:long long maximumTotalDamage(vectorint power) {// 统计相同的咒语的出现次数unordered_mapint,int mp;for(auto x:power) mp[x];// 排序 去重sort(power.begin(),power.end());power.erase(unique(power.begin(),power.end()),power.end());int n power.size();LL ans 0, j 0;// f[i] 表示前i个咒语中的施咒最大总伤害// f[i] max(f[i-1],f[j] mp[x]*x) x power[i]vectorLL f(n1); for(int i 0; i n; i) {while(power[j] 2 power[i])j;f[i1] max(f[i], f[j] (LL)mp[power[i]]*power[i]);ans max(f[i1], ans);}return ans;}
};
三、数组中的峰值 这题一看题目要求单点修改 区间查询可以用树状数组也可以用线段树代码如下
// 树状数组
struct BIT
{vectorint t;BIT(int n):t(n1){}void update(int i, int val){while(i t.size()) {t[i] val;i (i-i);}}int pre_sum(int i) {int res 0;while(i 0) {res t[i];i - (i-i);}return res;}int query(int l, int r){if(l r) return 0;return pre_sum(r) - pre_sum(l);}
};
class Solution {
public:vectorint countOfPeaks(vectorint nums, vectorvectorint q) {int n nums.size();BIT t(n);auto update [](int i, int val) {if(nums[i] nums[i-1] nums[i] nums[i1])t.update(i1,val);};for(int i 1; i n-1; i) {update(i,1);}vectorint ans;for(auto v:q) {if(v[0]1) { // 区间查询ans.push_back(t.query(v[1]1,v[2])); // 注意查询的区间由于查询的子数组的左右端点不能算作峰值并且树状数组的下标是从1开始的并且使用前缀和相减得到区间内的峰值}else{ // 单点修改int x v[1];// 先将可能会发生改变的点复原for(int i max(x-1,1); i min(x1,n-2); i) {update(i,-1);}nums[x] v[2];// 再重新更新可能会发生变化的点for(int i max(x-1,1); i min(x1,n-2); i) {update(i,1);}}}return ans;}
};// 线段树
struct SegTree
{vectorint t;SegTree(int n): t(n2){}void up(int o) {t[o] t[o*21] t[o*22];}void build(const vectorinta,int o,int l,int r) {if(l r) {t[o] 1;return;}int mid (l r) 1;build(a, o*21, l, mid);build(a, o*22, mid1, r);up(o);}void update(int o,int l, int r, int i, int val) {if(lr){t[o] val;return;}int mid (l r) 1;if(i mid) update(o*21, l, mid, i, val);else update(o*22, mid1, r, i, val);up(o);}int query(int o, int l, int r, int ql, int qr) {if(ql qr) return 0;if(ql l r qr)return t[o];int res 0;int mid (l r) 1;if(mid ql) res query(o*21, l, mid, ql, qr);if(mid qr) res query(o*22, mid1, r, ql, qr);return res;}
};
class Solution {
public:vectorint countOfPeaks(vectorint nums, vectorvectorint q) {int n nums.size();SegTree st(n);auto update [](int i, int val) {if(nums[i] nums[i-1] nums[i] nums[i1]) {st.update(0,0,n-1,i,val);}};for(int i 1; i n-1; i) {update(i,1);}vectorint ans;for(auto v:q) {if(v[0]1) { // 区间查询ans.push_back(st.query(0,0,n-1,v[1]1,v[2]-1));}else{ // 单点修改int x v[1];for(int i max(x-1,1); i min(x1,n-2); i) {update(i,0);}nums[x] v[2];for(int i max(x-1,1); i min(x1,n-2); i) {update(i,1);}}}return ans;}
};
