Leetcode - 周赛402

目录

一，3185. 构成整天的下标对数目 II

二，3186. 施咒的最大总伤害

三，3187. 数组中的峰值

一，3185. 构成整天的下标对数目 II

这里的T1，T2是一个题，这里直接一起讲了， 当我们已知 x%24 的值时，另一个数 y%24 的值一定等于（24 - x%24）%24（正整数时成立），得到这个性质之后，我们可以使用一个数组统计 %24 出现的次数，一边遍历一边统计。

代码如下：

class Solution {
    public long countCompleteDayPairs(int[] hours) {
        long ans = 0;
        int[] cnt = new int[24];
        for(int x : hours){
            ans += cnt[(24-x%24)%24];
            cnt[x%24]++;
        }
        return ans;
    }
}

二，3186. 施咒的最大总伤害

dfs记忆化——选或不选

本题重复的伤害值可以重复选，为了得到最大值，如果已经选择了某个值，那么与它相同的值也一定要选，所以可以先去重，统计所有元素的出现次数。题目还要求与他相邻为2的值不能选，所以可以将去重得到的数组排序，这样如果从前往后考虑，就可以只考虑power[i] + 1，power[i] + 2的情况；反之，亦然。

定义dfs(i)：[0，i]可以达到的伤害值之和的最大值，考虑最后一个数选或不选：

• 不选 i ，下一个状态是 dfs(i-1)
• 选 i，下一个状态是 dfs(j-1)，前提是满足 a[j-1] < a[i] - 2（a是去重后的数组）
• i < 0，返回 0

代码如下：

class Solution {
    public long maximumTotalDamage(int[] power) {
        //去重 + 统计每个数出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        for(int x : power) map.merge(x, 1, Integer::sum);
        int n = map.size(), k = 0;
        int[] a = new int[n];
        for(int x : map.keySet()){
            a[k++] = x;
        }
        Arrays.sort(a);
 
        memo = new long[n];
        Arrays.fill(memo, -1);
        return dfs(n-1, a, map);
    }
    long[] memo;
    long dfs(int i, int[] a, Map<Integer, Integer> map){
        if(i < 0) return 0;
        if(memo[i] != -1) return memo[i];
        int x = a[i];
        int j = i;
        while(j > 0 && a[j-1] >= x - 2){
            j--;
        }
        return memo[i] = Math.max(dfs(i-1, a, map), dfs(j-1, a, map)+(long)a[i]*map.get(a[i]));
    }
}

递推

定义 f[i]:前 i 个数可以达到的伤害值之和的最大值，由上述dfs可以得到递推公式：

• f[i] = Math.max(f[i-1]，f[j-1]+a[i]*map.get(a[i])）

代码如下：

class Solution {
    public long maximumTotalDamage(int[] power) {
        //去重 + 统计每个数出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        for(int x : power) map.merge(x, 1, Integer::sum);
        int n = map.size(), k = 0;
        int[] a = new int[n];
        for(int x : map.keySet()){
            a[k++] = x;
        }
        Arrays.sort(a);
 
        long[] f = new long[n+1];
 
        //这是记忆化 1:1 复刻
        //for(int i=0; i<n; i++){
        //    int j = i;
        //    while(j>0 && a[j-1] >= a[i] - 2){
        //        j--;
        //    }
        //    f[i+1] = Math.max(f[j]+(long)a[i]*map.get(a[i]), f[i]);
        //}
 
        //可以发现当 i 越大的时候，j也只会变的越来越大
        int j = 0;
        for(int i=0; i<n; i++){
            while(a[j] < a[i] - 2){
                j++;
            }
            f[i+1] = Math.max(f[j]+(long)a[i]*map.get(a[i]), f[i]);
        }
        return f[n];
    }
}

三，3187. 数组中的峰值

本题需要维护的是前 i 个数中有几个峰值，可以将原数组转换一下，如果nums[i]是峰值元素，我们就将其视为 1，否则视为 0。接下来求 [l，r]的峰值个数就可以使用前缀和来计算。

本题需要动态修改nums数组，所以可以使用树状数组/线段树来实现，这里使用树状数组。比如要修改nums[i]的值：

• 先把区间 [max⁡(i−1，1)，min⁡(i+1，n−2)] 中的峰值元素从树状数组中去掉

• 修改nums[i] = val

• 再把区间 [max⁡(i−1，1)，min⁡(i+1，n−2)] 中的峰值元素加入到树状数组中

代码如下：

class Fenwick{
    int[] tree;
    public Fenwick(int n){
        tree = new int[n];
    }
    //初始化和更改操作
    public void add(int i, int val){
        while(i < tree.length){
            tree[i] += val;
            i += (i & -i);
        }
    }
    //求前缀和
    public int pre(int i){
        int res = 0;
        while(i > 0){
            res += tree[i];
            i -= (i & -i);
        }
        return res;
    }
    //查询[l,r]区间的sum值
    public int query(int l, int r){
        if(l > r) return 0;
        return pre(r) - pre(l-1);
    }
}
 
class Solution {
    public List<Integer> countOfPeaks(int[] nums, int[][] queries) {
        List<Integer> ans = new ArrayList<>();
        int n = nums.length;
        Fenwick f = new Fenwick(n-1);//[1, n-2],必须从下标1开始
        for(int i=1; i<n-1; i++){
            update(i, f, nums, 1);
        }
        for(int[] q : queries){
            if(q[0] == 1){
                ans.add(f.query(q[1]+1, q[2]-1));
            }else{
                int j = q[1];
                for(int i=Math.max(1, j-1); i<=Math.min(j+1,n-2); i++){
                    update(i, f, nums, -1);
                }
                nums[j] = q[2];
                for(int i=Math.max(1, j-1); i<=Math.min(j+1,n-2); i++){
                    update(i, f, nums, 1);
                }
            }
        }
        return ans;
    }
    public void update(int i, Fenwick f, int[] nums, int val){
        if(nums[i] > nums[i-1] && nums[i] > nums[i+1]){
            f.add(i, val);
        }
    }
}

 再贴一个线段树的做法：

class Solution {
    int[] cnt, a;
    void build(int l, int r, int i) {
		if (l == r) {
			cnt[i] = 0;
		} else {
			int mid = (l + r) >> 1;
			build(l, mid, i << 1);
			build(mid + 1, r, i << 1 | 1);
			cnt[i] = cnt[i<<1] + cnt[i<<1|1] +
                ((l<mid && mid<r && a[mid]>a[mid-1]&&a[mid]>a[mid+1])||(l<mid+1 && mid+1<r && a[mid+1]>a[mid]&&a[mid+1]>a[mid+2]) ? 1 : 0);
		}
	}
    int query(int jobl, int jobr, int l, int r, int i) {
        if(jobr - jobl < 2) return 0;
		if (jobl <= l && r <= jobr) {
			return cnt[i];
		}
		int mid = (l + r) >> 1;
		int ans = 0, c = 0, b = 0;
		if (jobl <= mid) {
			c = query(jobl, jobr, l, mid, i << 1);
		}
		if (jobr > mid) {
			b = query(jobl, jobr, mid + 1, r, i << 1 | 1);
		}
		return c+b+(Math.max(l,jobl)<mid && mid<Math.min(r,jobr) && a[mid]>a[mid-1]&&a[mid]>a[mid+1]||(Math.max(l,jobl)<mid+1 && mid+1<Math.min(r,jobr) && a[mid+1]>a[mid]&&a[mid+1]>a[mid+2]) ? 1 : 0);
	}
    
    void update(int l, int r, int i, int jobr){
        if(l == r){
            return;
        } 
        int mid = (l + r) / 2;
        if(jobr <= mid){
            update(l, mid, i<<1, jobr);
        }else{
            update(mid+1, r, i<<1|1, jobr);
        }
        cnt[i] = cnt[i<<1]+cnt[i<<1|1]+((l<mid && mid<r && a[mid]>a[mid-1]&&a[mid]>a[mid+1])||(l<mid+1 && mid+1<r && a[mid+1]>a[mid]&&a[mid+1]>a[mid+2]) ? 1 : 0);
    }
    public List<Integer> countOfPeaks(int[] nums, int[][] queries) {
        List<Integer> ans = new ArrayList<>();
        int n = nums.length;
        a = nums;
        cnt = new int[n<<2];
        build(0, n-1, 1);
        for(int[] q : queries){
            if(q[0]==1){
                ans.add(query(q[1], q[2], 0, n-1, 1));
            }else{
                a[q[1]] = q[2];
                update(0, n-1, 1, q[1]);
            }
        }
        return ans;
    }
}