英文:
Need explanation for one test case failed in Codility Peaks problem
问题
Here is the translated content you provided:
一个由N个整数组成的非空数组A被给出。
峰值是指大于其相邻元素的数组元素。更准确地说,峰值是指索引P满足0 < P < N − 1,使得A[P − 1] < A[P]且A[P] > A[P + 1]。
例如,以下数组A:
A[0] = 1
A[1] = 2
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2
恰好有三个峰值:3、5和10。
我们希望将该数组分成包含相同数量元素的块。更准确地说,我们要选择一个数字K,以产生以下块:
A[0]、A1、...、A[K − 1],
A[K]、A[K + 1]、...、A[2K − 1],
...
A[N − K]、A[N − K + 1]、...、A[N − 1]。
此外,每个块应至少包含一个峰值。请注意,块的极端元素(例如A[K − 1]或A[K])也可以是峰值,但前提是它们都有邻居(包括相邻块中的邻居)。
目标是找到数组A可以分成的最大块数。
数组A可以按以下方式分成块:
一个块(1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2)。该块包含三个峰值。
两个块(1, 2, 3, 4, 3, 4)和(1, 2, 3, 4, 6, 2)。每个块都有一个峰值。
三个块(1, 2, 3, 4)、(3, 4, 1, 2)、(3, 4, 6, 2)。每个块都有一个峰值。特别要注意,第一个块(1, 2, 3, 4)在A[3]处有一个峰值,因为A[2] < A[3] > A[4],尽管A[4]在相邻块中。
然而,数组A无法分成四个块,即(1, 2, 3)、(4, 3, 4)、(1, 2, 3)和(4, 6, 2),因为(1, 2, 3)块不包含峰值。特别要注意,(4, 3, 4)块包含两个峰值:A[3]和A[5]。
数组A可以分成的最大块数为三。
编写一个函数:
class Solution { public int solution(int[] A); }
该函数接收一个由N个整数组成的非空数组A,并返回数组A可以分成的最大块数。
如果无法将数组A分成一些块,函数应返回0。
例如,给定:
A[0] = 1
A[1] = 2
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2
该函数应返回3,如上所述。
为以下假设编写一个高效的算法:
N是位于[1..100,000]范围内的整数;
数组A的每个元素是位于[0..1,000,000,000]范围内的整数。
关于问题的我的理解:
- 每个子数组应包含至少一个峰值
- 形成峰值的元素可以位于相邻子数组中。
- 返回最大可能的子数组数
我的问题:
考虑主数组:[0,1,0,1,0]
根据理解可能的子数组:[0,1] [0,1,0]
每个子数组都有一个峰值。
子数组1 [0,1] 具有与相邻数组共享的峰值元素 [0,1,0]。
子数组2 [0,1,0] 包含峰值 0<1>0。
因此,最大可能的子数组数为2,但Codility中的一个测试案例将最大可能的子数组数返回为1。
下面是我的代码:
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
int count=0,size=A.length;
if(size<2)
return 0;
System.out.println(Arrays.toString(A));
for(int i=1;i<size-1;i++){
if(A[i-1]<A[i] && A[i]>A[i+1]){
count++;
i++;
}
}
return count;
}
}
在Codility中失败的测试用例 点击此处
我相信我对问题的理解存在问题。任何帮助都将是有益的
英文:
A non-empty array A consisting of N integers is given.
A peak is an array element which is larger than its neighbors. More precisely, it is an index P such that 0 < P < N − 1, A[P − 1] < A[P] and A[P] > A[P + 1].
For example, the following array A:
A[0] = 1
A[1] = 2
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2
has exactly three peaks: 3, 5, 10.
We want to divide this array into blocks containing the same number of elements. More precisely, we want to choose a number K that will yield the following blocks:
A[0], A1, ..., A[K − 1],
A[K], A[K + 1], ..., A[2K − 1],
...
A[N − K], A[N − K + 1], ..., A[N − 1].
What's more, every block should contain at least one peak. Notice that extreme elements of the blocks (for example A[K − 1] or A[K]) can also be peaks, but only if they have both neighbors (including one in an adjacent blocks).
The goal is to find the maximum number of blocks into which the array A can be divided.
Array A can be divided into blocks as follows:
one block (1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2). This block contains three peaks.
two blocks (1, 2, 3, 4, 3, 4) and (1, 2, 3, 4, 6, 2). Every block has a peak.
three blocks (1, 2, 3, 4), (3, 4, 1, 2), (3, 4, 6, 2). Every block has a peak. Notice in particular that the first block (1, 2, 3, 4) has a peak at A[3], because A[2] < A[3] > A[4], even though A[4] is in the adjacent block.
However, array A cannot be divided into four blocks, (1, 2, 3), (4, 3, 4), (1, 2, 3) and (4, 6, 2), because the (1, 2, 3) blocks do not contain a peak. Notice in particular that the (4, 3, 4) block contains two peaks: A[3] and A[5].
The maximum number of blocks that array A can be divided into is three.
Write a function:
class Solution { public int solution(int[] A); }
that, given a non-empty array A consisting of N integers, returns the maximum number of blocks into which A can be divided.
If A cannot be divided into some number of blocks, the function should return 0.
For example, given:
A[0] = 1
A[1] = 2
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2
the function should return 3, as explained above.
Write an efficient algorithm for the following assumptions:
N is an integer within the range [1..100,000];
each element of array A is an integer within the range [0..1,000,000,000].
My Understanding of the problem :
- Each sub array should contain at least one peak
- An element which forms a peak can be in an Adjacent sub array.
- Return max possible sub arrays
My Question
Consider Main Array : [0,1,0,1,0]
Possible sub arrays as per understanding : [0,1] [0,1,0]
Each subarray has a peak.
Subarray 1 [0,1] has peak element shared with adjacent array [0,1,0].
Subarray 2 [0,1,0] contains peak 0<1>0.
So max possible sub arrays are 2 but a test case in Codility returns max possible sub arrays as 1.
Below is my code
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
int count=0,size=A.length;
if(size<2)
return 0;
System.out.println(Arrays.toString(A));
for(int i=1;i<size-1;i++){
if(A[i-1]<A[i] && A[i]>A[i+1]){
count++;
i++;
}
}
return count;
}
}
Test case which failed in Codility click here
I believe there is a gap in my understanding. Any help would be helpful
答案1
得分: 1
https://app.codility.com/demo/results/training5KP2PK-P4M/
https://github.com/niall-oc/things/blob/master/codility/peaks.py
将数组分成均等部分是将数组长度进行因式分解的另一种方式。
长度为12的数组
[0,1,0,1,0,0,0,1,0,0,1,0,]
12的因数。
12的平方根是3.464…,所以从3开始向下迭代到1,并将每个数字除以12。这给出一组数字{1, 2, 3, 4, 6, 12}。
过程
由于峰值的定义方式,这个数组中不能有12个峰值,因此从集合中删除12。将 d 作为最大的数来将数组分成 d 部分。并检查每个部分是否有峰值,如果有,则 d 是使得所有部分都至少包含一个峰值的最大均等部分数。如果没有,那么迭代到下一个最大的除数,并尝试直到找到解决方案。
英文:
https://app.codility.com/demo/results/training5KP2PK-P4M/
https://github.com/niall-oc/things/blob/master/codility/peaks.py
Breaking an array into even parts is another way of factorizing the length of the array.
Array of length 12
[0,1,0,1,0,0,0,1,0,0,1,0,]
Factors of 12.
The square root of 12 is 3.464... so start with 3 and irterate down to 1 and divide each number into 12. This gives you a set of numbers {1, 2, 3, 4, 6, 12}.
Process
Because of how a peak is defined you cannot have 12 peaks in this array so remove 12 from the set. Starting d as the largest number divide the array int d parts. And check each part has a peak, if so then d is the maximum number of equal parts to all contain at least one peak. If not so then iterate to the next largest divisor and try that until you find a solution.
答案2
得分: 0
首先,你需要被祝贺能够编写出一个简洁的程序来计算峰值的数量。但问题不在于计算峰值的数量。
问题是要找到具有相等大小的子数组,每个子数组至少有一个峰值。并且根据问题的陈述,峰值不能是第一个或最后一个元素,即 0 < P < N − 1。
现在引用你的问题:
考虑主数组:[0,1,0,1,0]
根据理解可能的子数组:[0,1] [0,1,0] 每个子数组都有一个峰值。子数组1 [0,1] 具有与相邻数组 [0,1,0] 共享的峰值元素。子数组2 [0,1,0] 包含峰值 0<1>0。
因此,最大可能的子数组为2,但是在Codility的一个测试案例中,最大可能的子数组为1。
我看到以下问题:
- 你的子数组大小不相等
- 数组 [0,1] 没有峰值
因此,无法将数组分成具有峰值的相等部分,因此只剩下一个数组 [0,1,0,1,0]。
英文:
First of all you need to be congratulated to write a concise program to calculate the number of peaks. But the question is not to count the peaks.
It is to find the number of equal sized array and each having at least one peak. And a peak cannot be the first or last element as stated in the problem 0 < P < N − 1
Now quoting your question:
Consider Main Array : [0,1,0,1,0]
Possible sub arrays as per understanding : [0,1] [0,1,0] Each subarray has a peak. Subarray 1 [0,1] has peak element shared with adjacent array [0,1,0]. Subarray 2 [0,1,0] contains peak 0<1>0.
So max possible sub arrays are 2 but a test case in Codility returns max possible sub arrays as 1.
I see below issues:
- your sub array sizes are not equal
- array [0,1] does not have a peak
So, the array cannot be divided in equal parts each having a peak and hence only one array remains [0,1,0,1,0].
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论