LeetCode：第 402 场周赛

总结

成功AK了，最后一题是一道数据结构板子题，但是没参赛有点可惜。

Q1：3184. 构成整天的下标对数目 I

题目传送门：3184. 构成整天的下标对数目 I - 力扣（LeetCode）

签个到

最后实现代码如下：

class Solution {
public:
    int countCompleteDayPairs(vector<int>& hours) {
        int n = hours.size(), ans=0;
        for(int i=0;i<n;++i){
            for(int j=i+1;j<n;++j){
                if((hours[i]+hours[j])%24==0) ans++;
            }
        }
        return ans;
    }
};

Q2：3185. 构成整天的下标对数目 II

题目传送门：3185. 构成整天的下标对数目 II - 力扣（LeetCode）

哈希一下，签到×2

最后实现代码如下：

class Solution {
public:
    long long countCompleteDayPairs(vector<int>& hours) {
        int n = hours.size();
        for(int i=0;i<n;++i) hours[i] = hours[i] % 24;
        long long ans = 0;
        vector<long long> dp(24,0);
        for(int i=0;i<n;++i){
            ans += dp[(24-hours[i])%24];
            dp[hours[i]]++;
        }
        return ans;
    }
};

Q3：3186. 施咒的最大总伤害

题目传送门：3186. 施咒的最大总伤害 - 力扣（LeetCode）

打家劫舍超级加强版，使用一个数组预处理一下就好（排序后，相同的合并），详细实现见代码。

最后实现代码如下：

class Solution {
public:
    long long maximumTotalDamage(vector<int>& power) {
        int n = power.size();
        sort(power.begin(), power.end());
        vector<pair<long long,long long>> nw_power;
        int prev = -1,m=0;
        for(int i=0;i<n;++i){
            if (power[i]==prev) nw_power[m-1].second += power[i];
            else nw_power.emplace_back(power[i], power[i]), prev = power[i], m++;
        }
        vector<long long> dp(m+3,0);
        dp[1] = nw_power[0].second;
        for(int i=2;i<=m;++i){
            long long nw_pw = nw_power[i-1].first;
            long long val = nw_power[i-1].second;
            int j = i-2;
            while(j>=0&&(nw_power[j].first==nw_pw-1||nw_power[j].first==nw_pw-2)) j--;
            dp[i] = max(dp[i-1], dp[j+1]+val);
        }
        return dp[m];
    }
};

Q4：3187. 数组中的峰值

题目传送门：3187. 数组中的峰值 - 力扣（LeetCode）

线段树大法好！这里看着就非常像线段树板题，但是还是有区别，需要注意的是合并区间的时候（左侧区间右端点或者右侧区间左端点）可能会产生新的峰值，需要写一个函数进行判定。这个函数的写法也有讲究，因为在最后合并小区间的时候，不同区间的长度可能决定了两个端点能否当端点，举个例子：

左 3，右 2 进行合并和左1 3 右2进行合并，产生的峰值数是不同的。

因此该函数需要传入合并时总区间的左侧和右侧边界位置：

int judge(int k,int l,int r,vector<int>& arr){
	int loc = node[k*2].right;
	if (loc-1>=l&&arr[loc]>arr[loc-1]&&arr[loc]>arr[loc+1]) return 1;
	if (loc+2<=r&&arr[loc+1]>arr[loc]&&arr[loc+1]>arr[loc+2]) return 1;
	return 0;
}

查询的时候也和传统的线段树不太相同，需要特别注意查询传入的区间左右位置：

int queryAns(int k, int l,int r,vector<int>& arr){
	if (l==node[k].left&&node[k].right==r) return node[k].val;
	int mid = node[k].left + (node[k].right-node[k].left)/2;
	int ans = 0;
	if (r<=mid) ans = queryAns(k*2,l,r,arr);
	else if (l>mid) ans = queryAns(k*2+1,l,r,arr);
	else ans = queryAns(k*2,l,mid,arr)+queryAns(k*2+1,mid+1,r,arr)+judge(k,l,r,arr);
	return ans;
}

最后实现代码如下：

class Solution {
private:
    struct TreeNode{
        int val, left, right;
        TreeNode() : val(0), left(-1), right(-1) {}
    };
    vector<TreeNode> node;
    int judge(int k,int l,int r,vector<int>& arr){
        int loc = node[k*2].right;
        if (loc-1>=l&&arr[loc]>arr[loc-1]&&arr[loc]>arr[loc+1]) return 1;
        if (loc+2<=r&&arr[loc+1]>arr[loc]&&arr[loc+1]>arr[loc+2]) return 1;
        return 0;
    }
    void update(int k,vector<int>& arr){
        node[k].val = node[k*2].val + node[k*2+1].val + judge(k,node[k].left,node[k].right,arr);
    }
    void buildTree(int k,int l,int r,vector<int>& arr){
        node[k].left = l; node[k].right = r;
        if(l==r) return;
        int mid = l + (r-l)/2;
        buildTree(k*2,l,mid,arr);
        buildTree(k*2+1,mid+1,r,arr);
        update(k, arr);
    }
    int queryAns(int k, int l,int r,vector<int>& arr){
        if (l==node[k].left&&node[k].right==r) return node[k].val;
        int mid = node[k].left + (node[k].right-node[k].left)/2;
        int ans = 0;
        if (r<=mid) ans = queryAns(k*2,l,r,arr);
        else if (l>mid) ans = queryAns(k*2+1,l,r,arr);
        else ans = queryAns(k*2,l,mid,arr)+queryAns(k*2+1,mid+1,r,arr)+judge(k,l,r,arr);
        return ans;
    }
    void modify(int k,int index,int val,vector<int>& arr){
        if(node[k].left == node[k].right && node[k].left == index) { arr[index] = val; return;}
        int mid = node[k].left + (node[k].right-node[k].left)/2;
        if(index<=mid) modify(k*2,index,val,arr);
        else modify(k*2+1,index,val,arr);
        update(k, arr);
    }
public:
    Solution() : node(300005) {}
    vector<int> countOfPeaks(vector<int>& nums, vector<vector<int>>& queries) {

        int root = 1, n = nums.size();
        buildTree(root, 0, n-1, nums);
        vector<int> ans;
        for(auto query : queries){
            if(query[0]==1) ans.push_back(queryAns(root, query[1], query[2], nums));
            else modify(root, query[1], query[2], nums);
        }
        return ans;
    }
};

这也是第一次个人在类里实现平级函数（之前都是使用的函数嵌套）