前言
DPDPDP
本周主题:二分查找、动态规划、记忆化搜索
题目:
- 240827每日一题—Find the Median of the Uniqueness Array
- 240828每日一题—Minimum Substring Partition of Equal Character Frequency
Find the Median of the Uniqueness Array
Find the Median of the Uniqueness Array
You are given an integer array nums. The uniqueness array of nums is the sorted array that contains the number of distinct elements of all the subarrays of nums. In other words, it is a sorted array consisting of distinct(nums[i..j]), for all 0 <= i <= j < nums.length.
Here, distinct(nums[i..j]) denotes the number of distinct elements in the subarray that starts at index i and ends at index j.
Return the median of the uniqueness array of nums.
Note that the median of an array is defined as the middle element of the array when it is sorted in non-decreasing order. If there are two choices for a median, the smaller of the two values is taken.
容易分析出以下解题步骤:
- find out a way to express all the subarrays
- which means 0,0\1,1...\n-1,n-1; 0,1\1,2...\n-2,n-1; … 0,n-2\1,n-1; 0,n-1
- we can find out there were n+n-1+…+2+1 subarrays in total.
- which means there were (n*(n+1))/2 elements in uniqueness array.
- find out how many “distinctors” in there
- the max value of them should be 1,2,…,n
- we can find a way to calculate them from the base subarrs, like from 1 number
总结一下:
- uniqueness array中一共有(n(n+1))/2个元素,中位数位置在(n(n+1))/4向下取整。
- 这些元素可以被分类,其中n个的范围为[1, 1],n-1个的范围为[1, 2],…,1个的范围为[1, n]。
基于以上分析,可以写出暴力法,显然超时:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21// author: SilenceZheng66
class Solution {
public int medianOfUniquenessArray(int[] nums) {
int n = nums.length;
Set<Integer>[] sets = new HashSet[n];
for(int i=0;i<n;i++){
sets[i] = new HashSet<Integer>();
sets[i].add(nums[i]);
}
List<Integer> list = new ArrayList<>();
for(int i=0;i<n;i++) list.add(sets[i].size());
for(int i=1;i<n;i++){
for(int j=0;j<n-i;j++){
sets[j].add(nums[i+j]);
list.add(sets[j].size());
}
}
Collections.sort(list);
return list.size()%2==0?list.get(list.size()/2-1):list.get(list.size()/2);
}
}
发现上述总结2中存在单调性,考虑使用二分查找。
二分查找
设数组 nums 的长度为 $n$, 我们令 $c_t$ 表示数组 nums 中至多含有 $t$ 个不同元素的子数组数目,实际 $t$ 的取值范围为: $t \in[1, \operatorname{distinct}[0 \cdots n-1]]$ 。此时可以发现 $t$ 越大,则 $c_t$ 也越大, 且满足 $c_n=\frac{n \times(n+1)}{2}$ 。我们可以观察到 $c_t$ 呈现单调性, 因此可以考虑使用二分查找, 如果 $c_t<$ median 则 $t$ 一定不是中位数, 因此利用二分查找找到 $t$ 的上限, 此时找到满足 $c_t \geq$ median 时最小的 $t$, 即为唯一性数组的中位数。
因此需要寻找一种方法计算$c_t$,注意到若数组$nums[i, j]$中至多含有 $t$ 个不同元素,则该数组的所有子数组也至多含有 $t$ 个不同元素。这里$nums[i, j]$可以用一个窗口表示,即双指针。$c_t$随$t$单调不减,可以用二分查找找到合适的t,判定是否合适的条件是是否$c_t \geq$ median,如果是的话则缩小$t$,否则增加$t$。
子数组越长, 则不同元素个数只会变大或不变,满足单调性。我们用哈希表 cnt 统计窗口子数组 $n u m s[i \cdots j]$ 中不同元素出现的次数。枚举窗口右端点 $i$ ,把 $n u m s[i]$ 加入到哈希表 cnt 中, 即此时 $n u m s[i]$ 出现次数加 1 。如果哈希表 cnt 中元素的数目超过 $t$ ,就不断移出窗口左端点元素 $n u m s[j]$ ,即此时 $n u m s[j]$ 出现的次数减去 1 ,如果 nums $[j]$ 出现次数等于 0 , 则将其从哈希表 cnt 中移除, 直到 cnt 中元素的数目等于 $t$ 为止。此时窗口的右端点为 $i$, 则此时子数组 nums $[j \cdots i]$, nums $[j+1 \cdots i]$, nums $[j+$ $2 \cdots i], \cdots$, nums $[i \cdots i]$ 都满足不同元素数目小于等于 $t$, 一共有 $i-j+1$ 个, 加到总数 tot 中, 最终的总数 $c_t=t o t$ 。我们每次检测是否满足 $c_t \geq$ median, 如果满足则缩小 $t$, 直到找到最小的 $t$ 返回即可。
实际二分查找时, $t$ 的下限取 1 , 此时一定不存在 0 个元素的子数组, $t$ 的上限为 $n$, 所有子数组的不同元素数目不超过 $n$ 。设 $m=\operatorname{distinct}[0 \cdots n-1]$ ,实际 $t$ 的取值范围为 $[1, m]$ ,且在该区间 $[1, m]$ 上的取值连续,因此一定可以找到属于某个子数组的 distinct 值。
1 | class Solution { |
Minimum Substring Partition of Equal Character Frequency
Minimum Substring Partition of Equal Character Frequency
Given a string s, you need to partition it into one or more balanced
substrings. For example, if s == “ababcc” then (“abab”, “c”, “c”), (“ab”, “abc”, “c”), and (“ababcc”) are all valid partitions, but (“a”, “bab”, “cc”), (“aba”, “bc”, “c”), and (“ab”, “abcc”) are not. The unbalanced substrings are bolded.Return the minimum number of substrings that you can partition s into.Note: A balanced string is a string where each character in the string occurs the same number of times.
以后看到这种最值选元素的…直接开DP就完了,最差也是等同暴力吧。
记忆化搜索
首先可以确定一定存在分割方案(都分成单字母)。
对于一个字符串s
,从末尾分割出长度为x
的平衡子串,则问题变成剩余字符串最少能分割出多少个平衡子串。这将原问题分解为相似且规模更小的子问题,可以递归求解。
注 1:从右往左思考,主要是为了方便把递归翻译成递推。从左往右思考也是可以的。
注 2:动态规划有「选或不选」和「枚举选哪个」两种基本思考方式。在做题时,可根据题目要求,选择适合题目的一种来思考。本题用到的是「枚举选哪个」。
注 3:这里的思考可以理解成从“最后一步”出发,划分子问题,即最后一步一定是划分出一个平衡子串,则考虑剩余部分的子问题即可,此时划分出最后一步不影响剩余部分的正确求解。反观贪心,如果尝试一次找到一个最长的平衡子串,则可能影响整体最优,因此这类问题最好通过DP+枚举解决。
下面考虑状态定义与转移,假设剩余前缀字符串为s[0...i]
,定义状态f(i)
为剩余s[0...i]
时最少能分割出多少平衡子串,则可以通过枚举j=0,1,..,i
,找到平衡子串s[j...i]
,则问题转化为求解状态 f(j-1)
,实现递归求解f(i)
。可以枚举所有j
,找到最小的f(j-1)
。
有一种方法可以快速判断子串平衡,即在倒序枚举j
的同时,用一个哈希表(或者数组)统计子串s[j...i]
每个字符的出现次数。如果子串中每个字母的出现次数都相等,那么子串是平衡的。进一步优化,设子串s[j...i]
中有k
种字母,字母出现次数的最大值为maxCnt
。子串是平衡的,当且仅当子串长度i−j+1
等于k⋅maxCnt
。
原问题表示为f(n-1)
,则可递归计算:f(n-1) = 1+f(x) = ... = m + f(-1) = m
。其中x
表示第一次求得的最小f(j-1)
对应的j
,m
表示最终划分出的平衡子串数量。分析至此可以写出暴力递归解法一。
1 | // author: SilenceZheng66 |
暴力递归在数据范围大的情况下依然会TTL,注意到枚举j
的过程中存在大量重复计算,考虑使用记忆化减少计算。由于递归函数幂等,可以对入参+返回
的组合进行记忆化。使用一个数组memo
来记录:
- 如果一个状态(递归入参)是第一次遇到,那么可以在返回前,把状态及其结果记到一个 memo 数组中。
- 如果一个状态不是第一次遇到(memo 中保存的结果不等于 memo 的初始值),那么可以直接返回 memo 中保存的结果。
注意memo
数组的初始值一定不能等于要记忆化的值,否则会跳过首次计算。因为递归求解等同于递归搜索,此类算法亦可称为记忆化搜索。
1 | class Solution { |
动态规划
记忆化搜索为自顶向下计算,即从f(n-1)
开始递归搜索。动态规划则是考虑自底向上的计算,即从f(0)
开始计算。
定义状态dp[i]
表示剩余字符串为s[0...i]
时最少能分割出多少平衡子串,则有状态转移方程:
另外由于递归边界为f(-1)
,则用dp[0]
存放初始状态dp[0] = 0
,剩余状态右移一位(递归边界对应DP初状态)。最终返回结果为dp[n]
。
1 | class Solution { |
参考文献
后记
首发于 silencezheng.top,转载请注明出处。