三角形:确定数组是否包含三角形三元组(Codility) [英] Triangle: Determine if an array includes a triangular triplet (Codility)
问题描述
这是Codility中的Triangle问题:
This is the Triangle problem from Codility:
给出了一个由N个整数组成的零索引数组A.
如果0≤P<3,则三元组(P,Q,R)为三角形.Q <&N和:
A zero-indexed array A consisting of N integers is given.
A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:
A [P] + A [Q]> A [R],
A [Q] + A [R]> A [P],
A [R] + A [P]> A [Q].
A[P] + A[Q] > A[R],
A[Q] + A[R] > A[P],
A[R] + A[P] > A[Q].
编写函数:
int solution(vector<int> &A);
,给定一个包含N个整数的零索引数组A,则返回1如果此数组存在一个三角形三元组并返回0否则.
that, given a zero-indexed array A consisting of N integers, returns 1 if there exists a triangular triplet for this array and returns 0 otherwise.
例如,给定数组A使得:
A [0] = 10,A [1] = 2,A [2] = 5,A [3] = 1,A [4] = 8,A [5] = 20三元组(0、2、4)是三角形,该函数应返回1.
For example, given array A such that:
A[0] = 10, A[1] = 2, A[2] = 5, A[3] = 1, A[4] = 8, A[5] = 20
Triplet (0, 2, 4) is triangular, the function should return 1.
给出数组A使得:
A [0] = 10,A [1] = 50,A [2] = 5,A [3] = 1
函数应返回0.
Given array A such that:
A[0] = 10, A[1] = 50, A[2] = 5, A[3] = 1
function should return 0.
假设:
N是[0..100,000]范围内的整数;
数组A的每个元素都是范围内的整数[−2,147,483,648..2,147,483,647].
N is an integer within the range [0..100,000];
each element of array A is an integer within the range
[−2,147,483,648..2,147,483,647].
这是我在C ++中的解决方案:
And here is my solution in C++:
int solution(vector<int> &A) {
if(A.size()<3) return 0;
sort(A.begin(), A.end());
for(int i=0; i<A.size()-2; i++){
//if(A[i] = A[i+1] = A[i+2]) return 1;
if(A[i]+A[i+1]>A[i+2] && A[i+1]+A[i+2]>A[i] && A[i+2]+A[i]>A[i+1]){
return 1;
}
}
return 0;
}
我已经检查了那里的评论,所有解决方案似乎都与我的类似.
但是,尽管其他人声称获得了100%的评分,但我只得到93%的评分.
我得到了所有正确的测试用例,其中之一:
I've checked the comments there and all the solutions seems similar to mine.
However, while others claimed to have gotten 100%, I only got a 93% score.
I got all the tests cases correct EXCEPT for one:
extreme_arith_overflow1
溢出测试,最多3个
extreme_arith_overflow1
overflow test, 3 MAXINTs
我认为这种情况有这样的输入:
[2147483647、2147483647、2147483647]
I assume this case has some input like this:
[2147483647, 2147483647, 2147483647]
因此,我将其添加到自定义测试用例中,当答案显然应该为1时,答案为0.
我还尝试了[1900000000、1900000000、1900000000],答案仍然为0.
但是,[1000000000、1000000000、1000000000]的答案为1是正确的.
So I add this to the custom test case, and the answer turns out to be 0 when it clearly should be 1.
I also tried [1900000000, 1900000000, 1900000000], and the answer is still 0.
However, [1000000000, 1000000000, 1000000000] is correct with answer of 1.
有人能提示我为什么会出现这种结果吗?
非常感谢.
Can anyone clue me in on why this result occured?
Greatly appreciated.
推荐答案
Java 100%:
Java 100 %:
public int solution(int[] A){
Arrays.sort(A);
for(int i=0;i<A.length-2;i++){
if(
((long)A[i] + (long)A[i+1] > A[i+2]) &&
((long)A[i+1] + (long)A[i+2] > A[i]) &&
((long)A[i] + (long)A[i+2] > A[i+1])
)
return 1;
}
return 0;
}
这篇关于三角形:确定数组是否包含三角形三元组(Codility)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!