这是Codility的三角问题：
给出了由N个整数组成的零索引数组A. 如果0≤P<Q <R <N，则三重态（P，Q，R）为三角形，并且：
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。
例如，给定数组A，使得： A [0] = 10，A [1] = 2，A [2] = 5，A [3] = 1，A [4] = 8，A [5] = 20三元组（0,2,4）是三角形，函数应返回1。
给定数组A，使得： A [0] = 10，A [1] = 50，A [2] = 5，A [3] = 1 函数应该返回0。
假使，假设：
N是[0..100,000]范围内的整数; 数组A的每个元素是[-2,147,483,648..2,147,483,647]范围内的整数。
这是我在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％的分数。 我得到的所有测试案例都正确除了一个：
非常低 溢出测试，MACHINTS
我假设这个案例有一些像这样的输入： [2147483647,2147483647,2147483647]
所以我将它添加到自定义测试用例中，当它显然应为1时，答案结果为0。 我也试过[1900000000,1900000000,1900000000]，答案仍然是0。 但是，[1000000000,1000000000,1000000000]是正确的，答案为1。
任何人都可以告诉我为什么会出现这个结果？ 非常感激。
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;
}
Ruby 100％解决方案
def solution(a)
arr = a.select{|x| x >=0 }.sort
arr.each_with_index do |p, pi|
arr[(pi+1)..-1].each_with_index do |q, qi|
arr[(qi+pi+2)..-1].each do |r|
break if p+q <=r
break if p+r <=q
break if r+q <=p
return 1
end
end
end
0
end
这是因为integer overflow。
试试这个：
int a1 = 1900000000;
int a2 = 1900000000;
int sum = a1+a2; // sum will be -494967296
编辑：使用long long int。
long long int sum01 = A[i] + A[i+1];
long long int sum12 = A[i+1] + A[i+2];
long lont int sum02 = A[i] + A[i+2];
if (sum01 > A[i+2] && sum12 > A[i] && sum02 > A[i+1])
return 1;
我的Java解决方案，100/100，时间复杂度为O（N * log（N））
用评论解释逻辑
// 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");
import java.util.Arrays;
class Solution {
public int solution(int[] A) {
int N = A.length;
if (N < 3) return 0;
Arrays.sort(A);
for (int i = 0; i < N - 2; i++) {
/**
* Since the array is sorted A[i + 2] is always greater or equal to previous values
* So A[i + 2] + A[i] > A[i + 1] ALWAYS
* As well ass A[i + 2] + A[i + 1] > A[i] ALWAYS
* Therefore no need to check those. We only need to check if A[i] + A[i + 1] > A[i + 2]?
* Since in case of A[i] + A[i + 1] > MAXINT the code would strike an overflow (ie the result will be greater than allowed integer limit)
* We'll modify the formula to an equivalent A[i] > A[i + 2] - A[i + 1]
* And inspect it there
*/
if (A[i] >= 0 && A[i] > A[i + 2] - A[i + 1]) {
return 1;
}
}
return 0;
}
基本上当你检查整数的X + Y值时，大于整数限制，代码将在溢出时失败。因此，如果X + Y > Z（简单数学不是吗？），我们可以简单地检查等效语句，而不是检查X > Z - Y。或者你总是可以使用long，但它将是一个更糟糕的解决方案记忆。
另外，请确保跳过底片，因为三角形不能有负面值。
干杯
这是我在Python中的干净解决方案。我得到了100％的Codility。该逻辑可以适用于任何其他编程语言。
注意：如果数组已排序，您只需要检查两个连续元素的总和是否大于下一个元素（A [i] + A [i + 1]> A [i + 2]），因为在那里例如，其他两个条件（A [i + 1] + A [i + 2]> A [i]，A [i] + A [i + 2]> A [i + 1]）将始终为真。
我希望它有所帮助。
def solution(A):
#edge case check
if len(A) < 3:
return 0
A.sort()
for i in range(len(A)-2):
if A[i]+A[i+1] > A[i+2]:
return 1
return 0
这里有几个问题
A[P] + A[Q] > A[R]。您已经检查了A.size（）<3，这样就可以了。我在https://github.com/naveedrasheed/Codility-Solutions/blob/master/Lesson6_Sorting/triangle.c添加了一个C实现。您可以将其与解决方案进行比较
我用Swift编写的这个问题的解决方案。
public func Triangle(_ A : inout [Int]) -> Int {
A.sort()
for i in 1..<A.count-1 {
if(A[i] + A[i-1] > A[i+1]) {
print("Triangle has edges: \(A[i-1]), \(A[i]), \(A[i+1])")
return 1
}
}
return 0
}
A = [10,2,5,1,8,20]
print("Triangle: ", Triangle(&A))
或者您可以更改if子句，如下所示
if(A[i]>A[i+2]-A[i+1] && A[i+1]>A[i]-A[i+2] && A[i+2]>A[i+1]-A[i])
使用减法代替加法。
我在这里使用3 for循环（没有排序数组）来解决这个问题。
public static int solution(int[] A) {
for (int p = 0; p < A.length; p++) {
for (int q = p + 1; q < A.length; q++) {
for (int r = q + 1; r < A.length; r++) {
if ((A[p] + A[q] > A[r]) && (A[q] + A[r] > A[p]) && (A[r] + A[p] > A[q])) {
System.out.println(A[p] + " " + A[q] + " " + A[r]);
return 1;
}
}
}
}
return 0;
}
100％工作，使用不同的方案进行测试。
我认为所有的可能性都不包括在上面的解决方案中与P，Q，R组合
A [0] = 10，A [1] = 2，A [2] = 5，A [3] = 1，A [4] = 8，A [5] = 20
指数组合
0+1>2, 1+2>0, 2+0>1
1+2>3, 2+3>1, 3+1>2
....
这些是实现此问题所需的组合。
//Triangle
/**
* A[P] + A[Q] > A[R],
A[Q] + A[R] > A[P],
A[R] + A[P] > A[Q]
*/
public int triangleSolution(int[] A) {
int status = 0;
for(int i=0; i<A.length; i++) {
int[] B = removeTheElement(A, i);
for(int j=0; j<B.length; j++) {
int[] C = removeTheElement(B, j);
for(int k=0; k<C.length; k++) {
if((A[i] + B[j] > C[k]) &&
(B[j] + C[k] > A[i]) &&
(C[k] + A[i] > B[j])) {
return 1;
}
}
}
}
return status;
}
// Function to remove the element
public int[] removeTheElement(int[] arr, int index)
{
// Create another array of size one less
int[] anotherArray = new int[arr.length - 1];
// Copy the elements except the index
// from original array to the other array
for (int i = 0, k = 0; i < arr.length; i++) {
// if the index is
// the removal element index
if (i == index) {
continue;
}
// if the index is not
// the removal element index
anotherArray[k++] = arr[i];
}
//Java >8
//IntStream.range(0, arr.length).filter(i -> i != index).map(i -> arr[i]).toArray();
return anotherArray;
}
//My solution in C++ it avoid overflow
inline int Triangle(vector<int> &A) {
if(A.size() < 3) return 0;
sort(A.begin(), A.end());
for(int i = 0; i < (int)A.size() - 2; ++i){
int P = A[i], Q = A[i + 1], R =A[i + 2];
if(( R - P - Q < 0) && ( P - Q - R < 0) && (Q - R - P < 0))
return 1;
}
return 0;
}