這是我幾天前嘗試過的在線編碼任務。我有一個大小為 N 的陣列。陣列中的專案一起表示一條鏈，現在每個專案表示鏈中每個連接的功率。任務是將鏈分成 3 個較小的鏈。
任務是在恰好兩個不相鄰的位置斷開鏈條。這意味著我們必須斷開連接 A,B (0<A<B<N-1,BA>1)，從而產生三個鏈 [0,A-1],[A 1,B-1],[B 1,N-1]。所以這個操作的總成本等于array[A] array[B]。
例如：
Array = {5, 2, 4, 6, 3, 7}
Array[0]=5
Array[1]=2
Array[2]=4
Array[3]=6
Array[4]=3
Array[5]=7
輸出：
5
解釋：
We can choose to break the following connections:
(1, 3): total cost is 2 6 = 8
(1, 4): total cost is 2 3 = 5
(2, 4): total cost is 4 3 = 7
Hence a minimum of (8, 5, 7) is 5.
約束： N 是 [5..100,000] 范圍內的陣列大小；每個 Array 專案范圍是 [1..1,000,000,000]。
我不確定我的理解是否正確。這是我的想法。基本上，在 Array 中找到位置 A 和 B，使得兩者都不相鄰，并獲取專案 Array[A] Array[B] 的總和并檢查最小總和。
這是我的代碼。
public int solution(int[] Array ) {
long output = 0;
int N = Array.length;
for(int i=0; i<N-1; i ) {
for(int j=i 2; j<N; j ) {
long sum = Array[i] Array[j];
if(output > sum) {
output = sum;
}
}
}
return (int) output;
}
此代碼為我提到的示例提供了正確的輸出。但是在線編碼任務有幾個隱藏的輸入，代碼完全失敗了。
uj5u.com熱心網友回復：
你的代碼是錯誤的：
- 而不是
i=0你應該從i=1. - 而不是
j<N你應該限制與j<N-1.
它也很慢，需要二次時間。應該在線性時間內解決。只需檢查所有可能的 B 值并將每個值與迄今為止允許的最小 A 值結合起來（在線嘗試！）：
public int solution(int[] Array ) {
int a = Array[1], output = a Array[3], N = Array.length;
for (int B=4; B<N-1; B ) {
a = Math.min(a, Array[B-2]);
output = Math.min(output, a Array[B]);
}
return output;
}
請注意，雖然我通常更喜歡索引變數iand j，但問題描述呼叫它們A和B. 所以我B在這里使用（我不需要A）。
或者在 Python 中（在線嘗試！）：
def solution(array):
return min(map(add, accumulate(array[1:], min), array[3:-1]))
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/313576.html