三角：确定是否阵列包括三角形三重峰（Codility）

这是从Codility三角问题：三角：确定是否阵列包括三角形三重峰（Codility）

一个零索引的数组A由N个整数的中给出。
甲三重峰（P，Q，R）是三角形的，如果0≤P < Q <ř< N和：

A [P] + A [Q]> A [R]，
A [Q] + A [P]，A [P]，
A [R] + A [P]> A [Q]。

写功能：
int solution(vector<int> &A); 
如果存在用于此阵列的三角形三元组，并返回0，否则，给定的零索引的数组A由N个整数的，返回1 。例如，给定数组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是RA内的整数nge [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％的分数。
我得到了所有的测试情况下，正确，除了一个：

extreme_arith_overflow1
溢出测试，3个MAXINTs

我认为这种情况有一些像这样的输入：
[2147483647，2147483647， 2147483647]

所以我把这个添加到自定义测试用例中，当它显然应该是1时，答案变成了0.
我也试过[19亿，19亿，19亿]，得到的答复仍然是0。
然而，[10亿，10亿，10亿]是我在为什么这个结果1.

任何人都可以线索的正确答案发生？
非常感谢。

来源

2017-07-04 toshism

听起来像正常的整数溢出。 https://en.wikipedia.org/wiki/Integer_overflow – Welbog

使长向量的int int –

向量只是查了一下：在这个例子中int是32位，long int保证32位，在Unix上可以是64，而long long int保证是64，所以这就是在这种情况下使用long long long的原因。谢谢你的帮助！ – toshism

-1

这是因为integer overflow。

试试这个：

int a1 = 1900000000; 
int a2 = 1900000000; 
int sum = a1+a2; // sum will be -494967296

编辑：使用长长整型。

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;

来源

2017-07-04 19:01:40

我不相信使用减法改变任何东西，因为它可以溢出（像'INT_MIN - INT_MAX'） –

是的，你是对的。在这种情况下，使用long long int。 –

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; 
    }

来源

2017-12-18 18:11:23

有几个问题在这里

边三角形不能为0，因为它是一个长度。您必须添加该支票，否则您将失败该角落案例。即不会获得100％。
由于您可以有一个包含所有INT_MAX或LONG_MAX的输入数组（请参见http://www.cplusplus.com/reference/climits/），因此您需要将总和存储为双长或长整数。
你不必在这里也就是检查所有三个条件

A [P] + A [Q]> A [R]， A [Q] + A [R]>一个[P ]， A [R] + A [P]> A [Q]。

如果已排序的数组比

A [Q] + A [R]> A [P] & &
A [R] + A [P]> A [Q]

始终为真，因为0≤P < Q < R即R大于P和Q. 因此，您应该只检查A[P] + A[Q] > A[R]。

您已经对A.size（）< 3进行了检查，因此很好。我在https://github.com/naveedrasheed/Codility-Solutions/blob/master/Lesson6_Sorting/triangle.c上添加了C实现。您可以将其与解决方案进行比较。

来源

2017-12-31 23:21:55

我对这个问题的解决方案，写在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))

来源

2018-01-31 09:02:11

三角：确定是否阵列包括三角形三重峰（Codility）

回答

相关问题