g*****e
发帖数: 282 | 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. | l***m
发帖数: 339 | 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
| p******9
发帖数: 47 | 3 这题在算法群里讨论过，O(M+N+H)时间 O(H)空间可以做出来，只要开一个O(H)的数组
预处理，记录每一个高度炮弹落下的位置，预处理复杂度是ON + H)，然后每来一个炮
弹，更新这个数组，因为每发炮弹只会有一个高度变化，所以更新时间是O(1)的。但是
目前没有找到把空间复杂度也降为O(N)的解法。 | g*****e
发帖数: 282 | 4 方便展开讲讲么？我想过分别对炮弹高度和地形高度分别预处理，但是分别会丢掉先后
炮弹顺序信息和地形相对位置信息。时间复杂度还是降不到O(M+N)。多谢了
【在 p******9 的大作中提到】
: 这题在算法群里讨论过，O(M+N+H)时间 O(H)空间可以做出来，只要开一个O(H)的数组
: 预处理，记录每一个高度炮弹落下的位置，预处理复杂度是ON + H)，然后每来一个炮
: 弹，更新这个数组，因为每发炮弹只会有一个高度变化，所以更新时间是O(1)的。但是
: 目前没有找到把空间复杂度也降为O(N)的解法。
| p******9
发帖数: 47 | 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，就是这样一个思路.可能还会有更好的办法 | g*****e
发帖数: 282 | 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，就是这样一个思路.可能还会有更好的办法
| b********k
发帖数: 427 | 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)
| g*****e
发帖数: 282 | 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提交后是什么结果？
|
|
