題目列表

3184. 構(gòu)成整天的下標(biāo)對數(shù)目 I

3185. 構(gòu)成整天的下標(biāo)對數(shù)目 II

3186. 施咒的最大總傷害

3187. 數(shù)組中的峰值

一、構(gòu)成整天的下標(biāo)對數(shù)目 I & II

可以直接二重for循環(huán)暴力遍歷出所有的下標(biāo)對，然后統(tǒng)計(jì)符合條件的下標(biāo)對數(shù)目返回。代碼如下

class Solution {
public:int countCompleteDayPairs(vector<int>& 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])%24==0)ans++;}}return ans;}
};

能不能優(yōu)化呢？或者說能否去掉一層循環(huán)，用一次遍歷計(jì)算出答案？

我們來思考一下內(nèi)層循環(huán)的作用是什么，就是看前面的數(shù)字能否和當(dāng)前數(shù)字能否組成能被24整除的數(shù)，也就是說只要我們在遍歷的同時，統(tǒng)計(jì)滿足加起來能被24的整除的數(shù)的出現(xiàn)次數(shù)，就能在O(1)的時間內(nèi)得到與當(dāng)前數(shù)字匹配的數(shù)字個數(shù)，從而降低時間復(fù)雜度。

如何得知兩個數(shù)加起來能被24整除？只要知道它們的%24的值即可，比如一個數(shù)%24=20，那么我們只要找%24=4的數(shù)字即可，故代碼如下

class Solution {
public:int countCompleteDayPairs(vector<int>& hours) {int cnt[24]{};int ans = 0;for(auto x:hours) {ans += cnt[(24-x%24)%24]; // (24-x%24)%24 用來計(jì)算另一個數(shù)%24的余數(shù)，為了防止出現(xiàn)24-0 = 24 的情況，故需要(...)%24cnt[x%24]++;}return ans;}
};

二、施咒的最大總傷害

先將數(shù)組排序，這樣我們從前往后選咒語只要考慮當(dāng)前咒語傷害是否大于前一個選擇的咒語+2即可，當(dāng)然咒語傷害相同可以同時被選中，所以我們還可以統(tǒng)計(jì)傷害相同的咒語的出現(xiàn)次數(shù)，然后將數(shù)組去重。最終，我們只要考慮當(dāng)前咒語傷害是否大于前一個選擇的咒語+2即可。

狀態(tài)定義：f[i]表示前i個咒語中能得到的最大傷害

狀態(tài)轉(zhuǎn)移方程：

• 選當(dāng)前咒語，f[i] = f[j] + cnt[x]*x，x = power[i]，f[j]為滿足power[j] + 2 < power[i]的最接近當(dāng)前位置的值
• 不選當(dāng)前咒語，f[i] = f[i-1]

故 f[i] = max( f[i-1]，f[j] + cnt[x]*x)，在遍歷 j 的時候，我們不用每次都從頭開始，j 只會變大，有點(diǎn)類似滑動窗口

代碼如下

class Solution {using LL = long long;
public:long long maximumTotalDamage(vector<int>& power) {// 統(tǒng)計(jì)相同的咒語的出現(xiàn)次數(shù)unordered_map<int,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]vector<LL> f(n+1); for(int i = 0; i < n; i++) {while(power[j] + 2 < power[i])j++;f[i+1] = max(f[i], f[j] + (LL)mp[power[i]]*power[i]);ans = max(f[i+1], ans);}return ans;}
};

三、數(shù)組中的峰值

這題一看題目要求，單點(diǎn)修改 + 區(qū)間查詢，可以用樹狀數(shù)組，也可以用線段樹，代碼如下

// 樹狀數(shù)組
struct BIT
{vector<int> t;BIT(int n):t(n+1){}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:vector<int> countOfPeaks(vector<int>& nums, vector<vector<int>>& q) {int n = nums.size();BIT t(n);auto update = [&](int i, int val) {if(nums[i] > nums[i-1] && nums[i] > nums[i+1])t.update(i+1,val);};for(int i = 1; i < n-1; i++) {update(i,1);}vector<int> ans;for(auto v:q) {if(v[0]==1) { // 區(qū)間查詢ans.push_back(t.query(v[1]+1,v[2])); // 注意查詢的區(qū)間，由于查詢的子數(shù)組的左右端點(diǎn)不能算作峰值，并且樹狀數(shù)組的下標(biāo)是從1開始的，并且使用前綴和相減得到區(qū)間內(nèi)的峰值}else{ // 單點(diǎn)修改int x = v[1];// 先將可能會發(fā)生改變的點(diǎn)復(fù)原for(int i = max(x-1,1); i <= min(x+1,n-2); i++) {update(i,-1);}nums[x] = v[2];// 再重新更新可能會發(fā)生變化的點(diǎn)for(int i = max(x-1,1); i <= min(x+1,n-2); i++) {update(i,1);}}}return ans;}
};// 線段樹
struct SegTree
{vector<int> t;SegTree(int n): t(n<<2){}void up(int o) {t[o] = t[o*2+1] + t[o*2+2];}void build(const vector<int>&a,int o,int l,int r) {if(l == r) {t[o] = 1;return;}int mid = (l + r) >> 1;build(a, o*2+1, l, mid);build(a, o*2+2, mid+1, r);up(o);}void update(int o,int l, int r, int i, int val) {if(l==r){t[o] = val;return;}int mid = (l + r) >> 1;if(i <= mid) update(o*2+1, l, mid, i, val);else update(o*2+2, mid+1, 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*2+1, l, mid, ql, qr);if(mid < qr) res += query(o*2+2, mid+1, r, ql, qr);return res;}
};
class Solution {
public:vector<int> countOfPeaks(vector<int>& nums, vector<vector<int>>& q) {int n = nums.size();SegTree st(n);auto update = [&](int i, int val) {if(nums[i] > nums[i-1] && nums[i] > nums[i+1]) {st.update(0,0,n-1,i,val);}};for(int i = 1; i < n-1; i++) {update(i,1);}vector<int> ans;for(auto v:q) {if(v[0]==1) { // 區(qū)間查詢ans.push_back(st.query(0,0,n-1,v[1]+1,v[2]-1));}else{ // 單點(diǎn)修改int x = v[1];for(int i = max(x-1,1); i <= min(x+1,n-2); i++) {update(i,0);}nums[x] = v[2];for(int i = max(x-1,1); i <= min(x+1,n-2); i++) {update(i,1);}}}return ans;}
};