• 双周赛116（模拟、贪心、记忆化搜索==＞ 动态规划、线段树）

    文章目录

    双周赛116

    2913. 子数组不同元素数目的平方和 I

    简单

    给你一个下标从 0 开始的整数数组 nums 。

    定义 nums 一个子数组的 不同计数 值如下：

    • 令 nums[i..j] 表示 nums 中所有下标在 i 到 j 范围内的元素构成的子数组（满足 0 <= i <= j < nums.length ），那么我们称子数组 nums[i..j] 中不同值的数目为 nums[i..j] 的不同计数。

    请你返回 nums 中所有子数组的 不同计数 的 平方 和。

    由于答案可能会很大，请你将它对 109 + 7 取余 后返回。

    子数组指的是一个数组里面一段连续 非空 的元素序列。

    示例 1：

    输入：nums = [1,2,1]
输出：15
解释：六个子数组分别为：
[1]: 1 个互不相同的元素。
[2]: 1 个互不相同的元素。
[1]: 1 个互不相同的元素。
[1,2]: 2 个互不相同的元素。
[2,1]: 2 个互不相同的元素。
[1,2,1]: 2 个互不相同的元素。
所有不同计数的平方和为 12 + 12 + 12 + 22 + 22 + 22 = 15 。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    示例 2：

    输入：nums = [2,2]
输出：3
解释：三个子数组分别为：
[2]: 1 个互不相同的元素。
[2]: 1 个互不相同的元素。
[2,2]: 1 个互不相同的元素。
所有不同计数的平方和为 12 + 12 + 12 = 3 。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    提示：

    • 1 <= nums.length <= 100
    • 1 <= nums[i] <= 100

    模拟 O(n^2)

    class Solution {
    public int sumCounts(List<Integer> nums) {
        int res = 0;
        int n = nums.size();
        for(int i = 0; i < n; i++){
            Set<Integer> set = new HashSet<>();
            for(int j = i; j < n; j++){
                set.add(nums.get(j));
                res += set.size() * set.size();
            }
        }
        return res;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    2914. 使二进制字符串变美丽的最少修改次数

    中等

    给你一个长度为偶数下标从 0 开始的二进制字符串 s 。

    如果可以将一个字符串分割成一个或者更多满足以下条件的子字符串，那么我们称这个字符串是 美丽的 ：

    • 每个子字符串的长度都是 偶数 。
    • 每个子字符串都 只 包含 1 或 只 包含 0 。

    你可以将 s 中任一字符改成 0 或者 1 。

    请你返回让字符串 s 美丽的 最少 字符修改次数。

    示例 1：

    输入：s = "1001"
输出：2
解释：我们将 s[1] 改为 1 ，且将 s[3] 改为 0 ，得到字符串 "1100" 。
字符串 "1100" 是美丽的，因为我们可以将它分割成 "11|00" 。
将字符串变美丽最少需要 2 次修改。

    • 1
    • 2
    • 3
    • 4
    • 5

    示例 2：

    输入：s = "10"
输出：1
解释：我们将 s[1] 改为 1 ，得到字符串 "11" 。
字符串 "11" 是美丽的，因为它已经是美丽的。
将字符串变美丽最少需要 1 次修改。

    • 1
    • 2
    • 3
    • 4
    • 5

    示例 3：

    输入：s = "0000"
输出：0
解释：不需要进行任何修改，字符串 "0000" 已经是美丽字符串。

    • 1
    • 2
    • 3

    提示：

    • 2 <= s.length <= 105
    • s 的长度为偶数。
    • s[i] 要么是 '0' ，要么是 '1' 。

    贪心

    class Solution {
    public int minChanges(String s) {
        int res = 0;
        for(int i = 1; i < s.length(); i += 2){
            if(s.charAt(i) != s.charAt(i-1))
                res += 1;
        }
        return res;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    2915. 和为目标值的最长子序列的长度

    中等

    给你一个下标从 0 开始的整数数组 nums 和一个整数 target 。

    返回和为 target 的 nums 子序列中，子序列 长度的最大值 。如果不存在和为 target 的子序列，返回 -1 。

    子序列 指的是从原数组中删除一些或者不删除任何元素后，剩余元素保持原来的顺序构成的数组。

    示例 1：

    输入：nums = [1,2,3,4,5], target = 9
输出：3
解释：总共有 3 个子序列的和为 9 ：[4,5] ，[1,3,5] 和 [2,3,4] 。最长的子序列是 [1,3,5] 和 [2,3,4] 。所以答案为 3 。

    • 1
    • 2
    • 3

    示例 2：

    输入：nums = [4,1,3,2,1,5], target = 7
输出：4
解释：总共有 5 个子序列的和为 7 ：[4,3] ，[4,1,2] ，[4,2,1] ，[1,1,5] 和 [1,3,2,1] 。最长子序列为 [1,3,2,1] 。所以答案为 4 。

    • 1
    • 2
    • 3

    示例 3：

    输入：nums = [1,1,5,4,5], target = 3
输出：-1
解释：无法得到和为 3 的子序列。

    • 1
    • 2
    • 3

    提示：

    • 1 <= nums.length <= 1000
    • 1 <= nums[i] <= 1000
    • 1 <= target <= 1000

    记忆化搜索 ==> 动态规划

    class Solution {
    int[] nums;
    int[][] cache;
    public int lengthOfLongestSubsequence(List<Integer> Nums, int target) {
        nums = Nums.stream().mapToInt(i -> i).toArray();
        int res = -1;
        int n = nums.length;
        cache = new int[n][target+1];
        for(int i = 0; i < n; i++)
            Arrays.fill(cache[i], -2);
        return dfs(n-1, target);
    }
    
    public int dfs(int i, int tot){
        if(i < 0)
            return tot == 0 ? 0 : Integer.MIN_VALUE;
        if(cache[i][tot] >= -1) return cache[i][tot];
        int res = -1;
        res = Math.max(res, dfs(i-1, tot));
        if(tot - nums[i] >= 0){
            int tmp = dfs(i-1, tot-nums[i]);
            if(tmp != -1){
                res = Math.max(res, tmp + 1);
            }
        }
        return cache[i][tot] = res;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    转为递推

    class Solution {
    public int lengthOfLongestSubsequence(List<Integer> NUMS, int target) {
        int[] nums = NUMS.stream().mapToInt(i -> i).toArray();
        int n = nums.length;
        int[][] f = new int[n+1][target+1];
        Arrays.fill(f[0], Integer.MIN_VALUE);
        f[0][0] = 0;
        for(int i = 0; i < n; i++){
            Arrays.fill(f[i+1], Integer.MIN_VALUE);
            for(int tot = 0; tot <= target; tot++){
                f[i+1][tot] = Math.max(f[i+1][tot], f[i][tot]);
                if(tot - nums[i] >= 0)
                    f[i+1][tot] = Math.max(f[i+1][tot], f[i][tot-nums[i]] + 1);
            }
        }
        return f[n][target] < -1 ? -1 : f[n][target];
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    空间优化

    class Solution {
    public int lengthOfLongestSubsequence(List<Integer> NUMS, int target) {
        int[] nums = NUMS.stream().mapToInt(i -> i).toArray();
        int n = nums.length;
        int[] f = new int[target+1];
        Arrays.fill(f, Integer.MIN_VALUE);
        f[0] = 0;
        for(int i = 0; i < n; i++){
            int[] tmp = Arrays.copyOf(f, f.length);
            Arrays.fill(f, Integer.MIN_VALUE);
            for(int tot = 0; tot <= target; tot++){
                f[tot] = Math.max(f[tot], tmp[tot]);
                if(tot - nums[i] >= 0)
                    f[tot] = Math.max(f[tot], tmp[tot-nums[i]] + 1);
            }
        }
        return f[target] < -1 ? -1 : f[target];
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    2916. 子数组不同元素数目的平方和 II

    困难

    给你一个下标从 0 开始的整数数组 nums 。

    定义 nums 一个子数组的 不同计数 值如下：

    • 令 nums[i..j] 表示 nums 中所有下标在 i 到 j 范围内的元素构成的子数组（满足 0 <= i <= j < nums.length ），那么我们称子数组 nums[i..j] 中不同值的数目为 nums[i..j] 的不同计数。

    请你返回 nums 中所有子数组的 不同计数 的 平方 和。

    由于答案可能会很大，请你将它对 109 + 7 取余 后返回。

    子数组指的是一个数组里面一段连续 非空 的元素序列。

    示例 1：

    输入：nums = [1,2,1]
输出：15
解释：六个子数组分别为：
[1]: 1 个互不相同的元素。
[2]: 1 个互不相同的元素。
[1]: 1 个互不相同的元素。
[1,2]: 2 个互不相同的元素。
[2,1]: 2 个互不相同的元素。
[1,2,1]: 2 个互不相同的元素。
所有不同计数的平方和为 12 + 12 + 12 + 22 + 22 + 22 = 15 。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    示例 2：

    输入：nums = [2,2]
输出：3
解释：三个子数组分别为：
[2]: 1 个互不相同的元素。
[2]: 1 个互不相同的元素。
[2,2]: 1 个互不相同的元素。
所有不同计数的平方和为 12 + 12 + 12 = 3 。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    提示：

    • 1 <= nums.length <= 105
    • 1 <= nums[i] <= 105

    线段树

    https://leetcode.cn/problems/subarrays-distinct-element-sum-of-squares-ii/solutions/2502897/yi-bu-bu-ti-shi-ni-si-kao-ben-ti-pythonj-zhhs/

    class Solution {
    /**
    提示1： 把右端点相同的子数组，分为同一组
        右端点为 i 的子数组，可以看成是右端点为 i-1 的子数组，在末尾加上a[i]
        添加后，右端点为 i-1 的这些子数组「不同计数的平方」之和增加了多少？
    提示2： 假设一个子数组不同计数 为 x，那么它的「不同计数的平方」为x^2
            如果这个子数组的不同计数增加了1，那么它的不同计数增加量： (x+1)^2-x^2 = 2x+1
     */
     private long[] sum;
    private int[] todo;

    public int sumCounts(int[] nums) {
        int n = nums.length;
        sum = new long[n * 4];
        todo = new int[n * 4];

        long ans = 0, s = 0;
        var last = new HashMap<Integer, Integer>();
        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            int j = last.getOrDefault(x, 0);
            s += queryAndAdd1(1, 1, n, j + 1, i) * 2 + i - j;
            ans = (ans + s) % 1_000_000_007;
            last.put(x, i);
        }
        return (int) ans;
    }

    private void do_(int o, int l, int r, int add) {
        sum[o] += (long) add * (r - l + 1);
        todo[o] += add;
    }

    // o=1  [l,r] 1<=l<=r<=n
    // 把 [L,R] 加一，同时返回加一之前的区间和
    private long queryAndAdd1(int o, int l, int r, int L, int R) {
        if (L <= l && r <= R) {
            long res = sum[o];
            do_(o, l, r, 1);
            return res;
        }

        int m = (l + r) / 2;
        int add = todo[o];
        if (add != 0) {
            do_(o * 2, l, m, add);
            do_(o * 2 + 1, m + 1, r, add);
            todo[o] = 0;
        }

        long res = 0;
        if (L <= m) res += queryAndAdd1(o * 2, l, m, L, R);
        if (m < R)  res += queryAndAdd1(o * 2 + 1, m + 1, r, L, R);
        sum[o] = sum[o * 2] + sum[o * 2 + 1];
        return res;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
  • 相关阅读:
    jdk和cglib动态代理
    iNFTnews | Web3正在推动一个41万亿元的市场？
    解决Redis分布式锁主从架构锁失效问题的终极方案 含面试题
    演讲比赛流程管理系统(看看你的星座会赢吗)
    c++ 对象和类
    底层驱动day8作业
    python实现ssl通信
    如何发送 WhatsApp Business 广播消息？
    Spring集成MyBatis（自定义类和xml配置文件两种形式）
    SpringCloud引入SpringBoot Admin
  • 原文地址：https://blog.csdn.net/qq_42958831/article/details/134438136