Redian新闻
>
[求解]codility online test的cannon打炮问题
avatar
[求解]codility online test的cannon打炮问题# JobHunting - 待字闺中
g*e
1
给定时间内只完成对O(MN)的优化,没能想出O(M+N)。感觉这题目挺有意思的现在
继续想,欢迎bs,欢迎版友讨论 =)
A new kind of cannon is being tested. The cannon shoots cannonballs in a
fixed direction. Each cannonball flies horizontally until it hits the ground
, and then it rests there. Cannonballs are shot from different heights, so
they hit the ground at different points.
You are given two zero-indexed arrays, A and B, containing M and N integers
respectively. Array A describes the landscape in the direction along which
the cannon is shooting. Elements of array A represent the height of the
ground, going from the cannon outwards. Array B contains levels from which
consecutive cannonballs are shot.
Assume that a cannonball is shot at level H.
Let I be the smallest index, such that 0 < I < M and A[I] ≥ H. The
cannonball falls at position I − 1 and increases the ground level A[I&
#8722;1] by 1.
If there is no such I, and H > A[I] for all 0 ≤ I < M, then the cannonball
flies beyond the horizon and has no effect on the result.
If H ≤ A[0], then the cannonball ricochets away and has no effect on the
result either.
Write a function:
class Solution { int[] cannonballs(int[] A,int[] B); }
that, given arrays A and B, simulates the flight of the cannonballs and
returns the final contents of array A (denoted by A1) representing the final
shape of the ground along the line of fire.
For example, given the following arrays A and B, of size M = 9 and N = 11
respectively:
A[0] = 1 A[1] = 2 A[2] = 0
A[3] = 4 A[4] = 3 A[5] = 2
A[6] = 1 A[7] = 5 A[8] = 7

B[0] = 2 B[1] = 8 B[2] = 0
B[3] = 7 B[4] = 6 B[5] = 5
B[6] = 3 B[7] = 4 B[8] = 5
B[9] = 6 B[10]= 5
the function should return the following zero-indexed array A1 of M = 9
integers:
A1[0] = 2 A1[1] = 2 A1[2] = 2
A1[3] = 4 A1[4] = 3 A1[5] = 3
A1[6] = 5 A1[7] = 6 A1[8] = 7
Assume that:
M and N are integers within the range [0..30,000];
each element of array A is an integer within the range [0..1,000,000];
each element of array B is an integer within the range [0..1,000,000].
Complexity:
expected worst-case time complexity is O(H+M+N);
expected worst-case space complexity is O(M), beyond input storage (not
counting the storage required for input arguments).
Notation used:
H − max level of a cannonball.
Elements of input arrays can be modified.
avatar
l*m
2
这是公司给的code test题吗?

ground
integers

【在 g*****e 的大作中提到】
: 给定时间内只完成对O(MN)的优化,没能想出O(M+N)。感觉这题目挺有意思的现在
: 继续想,欢迎bs,欢迎版友讨论 =)
: A new kind of cannon is being tested. The cannon shoots cannonballs in a
: fixed direction. Each cannonball flies horizontally until it hits the ground
: , and then it rests there. Cannonballs are shot from different heights, so
: they hit the ground at different points.
: You are given two zero-indexed arrays, A and B, containing M and N integers
: respectively. Array A describes the landscape in the direction along which
: the cannon is shooting. Elements of array A represent the height of the
: ground, going from the cannon outwards. Array B contains levels from which

avatar
p*9
3
这题在算法群里讨论过,O(M+N+H)时间 O(H)空间可以做出来,只要开一个O(H)的数组
预处理,记录每一个高度炮弹落下的位置,预处理复杂度是ON + H),然后每来一个炮
弹,更新这个数组,因为每发炮弹只会有一个高度变化,所以更新时间是O(1)的。但是
目前没有找到把空间复杂度也降为O(N)的解法。
avatar
g*e
4
方便展开讲讲么?我想过分别对炮弹高度和地形高度分别预处理,但是分别会丢掉先后
炮弹顺序信息和地形相对位置信息。时间复杂度还是降不到O(M+N)。多谢了

【在 p******9 的大作中提到】
: 这题在算法群里讨论过,O(M+N+H)时间 O(H)空间可以做出来,只要开一个O(H)的数组
: 预处理,记录每一个高度炮弹落下的位置,预处理复杂度是ON + H),然后每来一个炮
: 弹,更新这个数组,因为每发炮弹只会有一个高度变化,所以更新时间是O(1)的。但是
: 目前没有找到把空间复杂度也降为O(N)的解法。

avatar
p*9
5
对地形数组做预处理,比如地形是A=[2 1 5 4 6 7],开一个O[H]的数组记录每个高度
的炮弹会落下的位置,预处理之后变成T = [-1 , -1 , -1 , 1 , 1, 1, 3, 4],意思
就是说高度<=2的点都落不进去,高度为3的点落到A[1],高度为4的点也落点A[1] ...
高度7的点落到A[4]. 来了一个炮弹,假设其高度是7,那么落到A[4],A[4]+1变成7,
因为A[4]=7,更新T[7] = T[6]=3,就是这样一个思路.可能还会有更好的办法
avatar
g*e
6
很赞的思路,我写了一个,过了自己写的test case。不知道有没有bug,或者能不能
code更加简洁。这题能在一小时内无bug写出来很不容易。欢迎继续讨论 =)

public int[] cannonballs(int[] A, int[] B)
{
if (A == null || A.Length == 0)
{
return null;
}
if (B == null || B.Length == 0)
{
return null;
}
int H = 1000000;
int[] locations = new int[H + 1];
int i = 0, j = 0;
while ((i < A.Length) && (j <= H))
{
if (A[i] >= j)
{
if (j - 1 >= 0)
{
locations[j] = locations[j - 1];
}
else
{
locations[j] = -1;
}
}
else
{
bool flag = true;
while (A[i] < j)
{
i++;
if (i >= A.Length)
{
flag = false;
break;
}
}
if (flag)
{
locations[j] = i - 1;
}
else
{
break;
}
}
j++;
}
while (j <= H)
{
locations[j] = -1;
j++;
}
for (int k = 0; k < B.Length; k++)
{
int offset = locations[B[k]];
if (offset >= 0)
{
//处理凹的情况,处理多个同高度峰谷的情况
if ((offset - 1 >= 0) && (A[offset - 1] < A[offset] + 1))
{
if (offset <= locations[A[offset] + 1])
{
locations[A[offset] + 1] = offset - 1;
}
}
else
{
locations[A[offset] + 1] = locations[A[offset]];
}
A[offset]++;
}
}
return A;
}

【在 p******9 的大作中提到】
: 对地形数组做预处理,比如地形是A=[2 1 5 4 6 7],开一个O[H]的数组记录每个高度
: 的炮弹会落下的位置,预处理之后变成T = [-1 , -1 , -1 , 1 , 1, 1, 3, 4],意思
: 就是说高度<=2的点都落不进去,高度为3的点落到A[1],高度为4的点也落点A[1] ...
: 高度7的点落到A[4]. 来了一个炮弹,假设其高度是7,那么落到A[4],A[4]+1变成7,
: 因为A[4]=7,更新T[7] = T[6]=3,就是这样一个思路.可能还会有更好的办法

avatar
b*k
7
我觉得这道题的难点在于 worst-case space complexity is O(M)
题目里边说了,H可能比M,N要大得多
M and N are integers within the range [0..30,000];
each element of array A is an integer within the range [0..1,000,000];
each element of array B is an integer within the range [0..1,000,000].
btw,你的代码在codility提交后是什么结果?

【在 g*****e 的大作中提到】
: 很赞的思路,我写了一个,过了自己写的test case。不知道有没有bug,或者能不能
: code更加简洁。这题能在一小时内无bug写出来很不容易。欢迎继续讨论 =)
:
: public int[] cannonballs(int[] A, int[] B)
: {
: if (A == null || A.Length == 0)
: {
: return null;
: }
: if (B == null || B.Length == 0)

avatar
g*e
8
过了。开的辅助数组1000001就可以了,不是很大。再高的炮弹无视

【在 b********k 的大作中提到】
: 我觉得这道题的难点在于 worst-case space complexity is O(M)
: 题目里边说了,H可能比M,N要大得多
: M and N are integers within the range [0..30,000];
: each element of array A is an integer within the range [0..1,000,000];
: each element of array B is an integer within the range [0..1,000,000].
: btw,你的代码在codility提交后是什么结果?

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。