三角：確定是否陣列包括三角形三重峯（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）

回答

相關問題