leetcode biweekly contes 116
双周赛的 T4 果然是个好题目，难度还是有的，需要用到线段树加数学技巧。
100094. 子数组不同元素数目的平方和 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] |
示例 2：
输入：nums = [2,2] |
提示：
1 <= nums.length <= 1001 <= nums[i] <= 100
地址
题意
枚举
思路
- 直接枚举并统计所有的连续子数组中的元素的值即可，直接模拟。
- 复杂度分析：
- 时间复杂度：$O(n^2)$，其中 $n$ 表示给定的数组的长度。
- 空间复杂度：$O(n)$，其中 $n$ 表示给定的数组的长度。
代码
class Solution: |
100104. 使二进制字符串变美丽的最少修改次数
给你一个长度为偶数下标从 0 开始的二进制字符串 s 。
如果可以将一个字符串分割成一个或者更多满足以下条件的子字符串，那么我们称这个字符串是 美丽的 ：
- 每个子字符串的长度都是 偶数 。
- 每个子字符串都 只 包含
1或 只 包含0。
你可以将 s 中任一字符改成 0 或者 1 。
请你返回让字符串 s 美丽的 最少 字符修改次数。
示例 1：
输入：s = "1001" |
示例 2：
输入：s = "10" |
示例 3：
输入：s = "0000" |
提示：
2 <= s.length <= 105s的长度为偶数。s[i]要么是'0'，要么是'1'。
地址
题意
枚举
思路
- 题目想复杂了，实际只需要保证所有连续偶数的字符串的字符相等，其实我们只需要保证所有以偶数间隔的字符的相等即可。最小分割即为 $2$，因此我们只需要保证相邻间隔的两个字符相等即可，我们只需要检测 $s[i] = s[i+1]$ 即可。
- 复杂度分析：
- 时间复杂度：$O(n)$，其中 $n$ 表示给定的数组的长度。
- 空间复杂度：$O(1)$，其中 $n$ 表示给定的数组的长度。
代码
class Solution: |
100042. 和为目标值的最长子序列的长度
给你一个下标从 0 开始的整数数组 nums 和一个整数 target 。
返回和为 target 的 nums 子序列中，子序列 长度的最大值 。如果不存在和为 target 的子序列，返回 -1 。
子序列 指的是从原数组中删除一些或者不删除任何元素后，剩余元素保持原来的顺序构成的数组。
示例 1：
输入：nums = [1,2,3,4,5], target = 9 |
示例 2：
输入：nums = [4,1,3,2,1,5], target = 7 |
示例 3：
输入：nums = [1,1,5,4,5], target = 3 |
提示：
1 <= nums.length <= 10001 <= nums[i] <= 10001 <= target <= 1000
地址
题意
0,1背包问题，动态规划
思路
典型的动态规划问题，设 $dp[i]$ 表示使得目标和为 $i$ 的最长子序列数目，则此时我们可以知道遍历当前的 $x$ 时，可以有
$$dp[t] = max(dp[t], dp[t-x] + 1)$$ ，我们从大到小遍历所有的元素即可得到使得当前元素为 $target$ 的最长子序列的数目。
复杂度分析：
- 时间复杂度：$O(n \times target)$，其中$n$ 表示数组的长度, $target$ 表示给定的元素；
- 空间复杂度：$O(target)$， $target$ 表示给定的元素；
代码
class Solution: |
100074. 子数组不同元素数目的平方和 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] |
示例 2：
输入：nums = [2,2] |
提示：
1 <= nums.length <= 1051 <= nums[i] <= 105
地址
题意
线段树 ，数学公式展开
思路
题目刚开始拿到确实不太好做，但是需要仔细思考一下，昨天想到了公式展开，但是想错了一个问题。比较难的是还需要用到懒标记的线段树，我们首先思考一个问题，假设以 $nums[i]$ 为结尾的子数组一共有 $i+1$ 个，长度分别为 $[l_0,l_1,l_3,\cdots,l_{i-1}, 1]$ 个，则此时以 $nums[i]$ 为结尾的子数组的长度的平方和则为:
$$
sum_i = l_0^2 + l_1^2 + \cdots + l_{i-1}^2 + l_i^2 = \sum_{j=0}^{i}l_j^2
$$
其中 $l_j$ 表示以 $nums[j]$ 为起点，以 $nums[i]$ 为终点的子数组中不同元素的数目，此时我们当我们加入新的元素 $nums[i+1]$ 时会有什么表现？我们仔细分析一下，有两种情况需要讨论：如果 $nums[i+1]$ 在 $[0,i]$ 中从未出现过，则可以知道以 $nums[i+1]$ 为结尾的子数组的元素数目分别为 $[l_0 + 1，l_1+1,\cdots,l_{i-1}+1,l_i+1,1]$，则可以有以下递推：
$$
sum_{i+1} = (l_0+1)^2 + (l_1+1)^2 + (l_2+1)^2 + \cdots + (l_{i-1}+1)^2 + (l_i + 1)^2 + 1 = \
l_0^2 + l_1^2 + \cdots + l_{i-1}^2 + l_i^2 + 2(l_0 + l_1 +\cdots + l_{i-1} + l_i) + i + 1 = \
sum_i + 2\sum_{j=0}^{i}l_j + 1
$$
这意味着只要我们能够计算出 $\sum_{j=0}^il_j$ 的和，上述的递推关系就可以计算出来，我们再来分析另外一种情况：如果 $nums[i+1]$ 在 $[0,i]$ 中出现过不止一次，且最后出现的位置为 $j$，则可以知道以 $nums[i+1]$ 为结尾的子数组的元素数目分别为 $[l_0，l_1,\cdots,l_{j},l_{j+1} + 1,l_{j+2} + 1, \cdots, l_{i-1} + 1, l_{i} + 1,1]$，则可以有以下递推：
$$
sum_{i+1} = l_0^2 + l_1^2 + l_2^2 + \cdots + l_j^2 + (l_{j}+1)^2 + (l_{j+2} + 1)^2 + \cdots + l_i^2 + 1 = \
l_0^2 + l_1^2 + \cdots + l_{i-1}^2 + l_i^2 + 2(l_{j+1} + l_{j+2} +\cdots + l_{i-1} + l_i) + (i - j) + 1 = \
sum_i + 2\sum_{k=j+1}^{i}l_k + 1
$$
这意味着只要我们能够计算出 $\sum_{k=j}^il_k$ 的和，上述的递推关系就可以计算出来。此时我们可以利用线段树的懒更新来标记当前索引 $i$ 时的所有以 $j \in [0,i]$ 开头的子数组的元素数目，当我们遍历到 $i+1$ 时，我们看到此时区间 $[j+1, i + 1]$ 中的元素全部加 $1$ 即为 当前 $i+1$ 为结尾的子数组中的元素数目分布，我们利用线段树的懒更新和范围查找即可快速的实现上述的递推关系，整个题目的关系在如何将公式展开和推导；每次查询时，首先找到当前元素 $nums[i]$ 最近出现为位置 $j$，然后就是当前的值即为 $pre + 2 * sum(j + 1, i) + 1$, 更新当前的计算，然后更新当前的位置，在此对当前元素的子数组数目分布进行更新。
复杂度分析：
- 时间复杂度：$O(n \log n)$，其中 $n$ 表示数组的长度；
- 空间复杂度：$O(n)$，其中 $n$ 表示数组的长度；
代码
mod = 10**9 + 7 |
欢迎关注和打赏，感谢支持！
- 关注我的博客: http://whistle-wind.com/
- 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
- 关注我的微信公众号: 公务程序猿
扫描二维码，分享此文章