arrays - 计数不同子数组的数量
问题描述
我最近在一次编码面试中遇到了这个问题。问题如下:
给定一个包含 n 个数字和一个数字 k 的数组 A[],计算不同子数组的总数,使得每个子数组最多包含 k 个奇数元素。
1 <= n <= 1000
1 <= A[i] <= 250
1 <= k <= n
我使用了 DP 方法来解决问题,但我的解决方案并没有解决这个问题distinct
。
public int distinctSubArraysWithAtmostKOddElements(int[] a, int k) {
int l = a.length;
int[][] dp = new int[k + 1][l];
for (int j = 0; j < l; j++) {
dp[0][j] = a[j] % 2 == 0 ? 1 : 0;
}
for (int i = 1; i <= k; i++) {
dp[i][0] = 1;
}
for (int j = 1; j <= k; j++) {
for (int i = 1; i < l; i++) {
if (a[i] % 2 == 0) {
dp[j][i] = Math.max(dp[j - 1][i], 1 + Math.max(dp[j - 1][i - 1], dp[j][i - 1]));
} else {
dp[j][i] = Math.max(dp[j - 1][i], 1 + dp[j - 1][i - 1]);
}
}
}
int tot = 0;
for (int i = 0; i < l; i++) {
tot += dp[k][i];
}
return tot;
}
我的解决方案适用于O(nk)时间和空间。
我该如何照顾这种独特性?有解决这个问题的数学公式吗?
编辑:
例如1:
A[] = {2,1,2,3} and k = 1
Distinct Subarrays are: {2}, {2,1}, {1}, {1,2}, {2,1,2}, {3}, {2,3}
So answer is 7.
例如 2:
A[] = {1,1,1} and k = 2
Distinct Subarrays are: {1}, {1,1}
So answer is 2.
例如 3:
A[] = {1,2,3} and k = 1
Distinct Subarrays are: {1}, {2}, {3}, {1,2}, {2,3}
So answer is 5.
解决方案
我们可以遍历所有子数组并存储有效子数组的哈希值。时间复杂度是O((n^2)*log(n))
和内存复杂度O(n^2)
。
int distinctSubArraysWithAtmostKOddElements(vector<int> a, int k)
{
set<unsigned long long int> hashes;
int prime = 163;
for(int i = 0 ; i < a.size() ; i++)
{
int oddNow = 0;
unsigned long long int hashNow = 0;
for(int j = i ; j < a.size() ; j++)
{
hashNow = hashNow * prime + a[j];
if( a[j] % 2) oddNow++;
if(oddNow <= k)
hashes.insert(hashNow);
else
break;
}
}
return hashes.size();
}
推荐阅读
- swift - 如何在 UITabelViewCell 类中访问正确的单元格宽度?
- c# - 在发布时设置/获取 DeliveryTag RabbitMQ
- apache-kafka - 具有 Kafka 流的自定义状态存储 (RocksDb) 是否有保留策略?
- powershell - Get-Package 命令包含 xml 字符串 - 需要转换为 PSObject
- python - 应用函数将数组除以向量
- javascript - 如何判断一个特定模块是 CommonJS 模块还是 ES6 模块?
- c++ - 如何将 int** 转换为 void**?
- java - 当我使用搜索编辑文本和过滤方法时,为什么我的应用程序会崩溃
- makefile - LDFLAGS 和 ldflags-y 的区别
- python - 我们是否有用于板球比赛得分的良好 API?