曼哈頓天際線覆蓋失敗一些測試案例

我正在做關於編碼的練習。我在這個問題上花了兩天的時間，而且我的分數沒有提高。我的正確性得分爲100％，但因爲它返回了錯誤的答案（不是因爲時間或空間的複雜性）而失敗了一些性能測試。我的錯誤結果總是比預期的答案少。任何人都可以想到我需要添加一塊我缺少的石頭的情況嗎？曼哈頓天際線覆蓋失敗一些測試案例

這是提示：

你要建立一個石牆。牆壁應該是直的，長度爲N米，並且其厚度應該是恆定的;但是，它應該在不同的地方有不同的高度。牆的高度由零指數陣列H的N正整數指定。

H[I]是牆壁從I到I+1到其左端右側的高度。特別是，H[0]是牆壁左端的高度，H[N−1]是牆壁右端的高度。

牆體應該由立方體石塊（即這些塊的所有邊都是矩形）構成。您的任務是計算構建牆的最小塊數。

編寫一個函數，給定一個零索引的數組HN指定牆的高度的正整數返回構建它所需的最小塊數。
class Solution { public int solution(int[] H); } 
例如，給定陣列H含有N = 9整數：
H[0] = 8 H[1] = 8 H[2] = 5  
    H[3] = 7 H[4] = 9 H[5] = 8  
    H[6] = 7 H[7] = 4 H[8] = 8  
該函數應返回7.該圖顯示了七個塊一種可能的佈置。

假設：

N在該範圍內[1..100,000]的整數;

數組H的每個元素是[1..1,000,000,000]範圍內的整數。

複雜性：

預期最壞情況下的時間複雜度是\ $ O（N）\ $;

預期最壞情況下的空間複雜度爲\ $ O（N）\ $，超出輸入存儲空間（不包括輸入參數所需的存儲空間）。

輸入數組的元素可以修改。

這是我的解決方案：

import java.util.*; 

class Solution { 
    public int solution(int[] H) { 
     // write your code in Java SE 8 

     LinkedList<Integer> stack = new LinkedList<Integer>(); 
     int count = 1; 
     int lowest = H[0]; 
     stack.push(H[0]); 

     if(H.length == 1){ 
      return 1; 
     } 
     else{ 
     for(int i = 1; i<H.length; i++){ 
      if(H[i] > H[i-1]){ 
       stack.push(H[i]); 
       count++; 
      } 
      if(H[i] < lowest){ 
       while(stack.size() > 0){ 
        stack.pop(); 
       } 
       stack.push(H[i]); 
       lowest = H[i]; 
       count++; 
      } 
      if(H[i] < H[i-1] && H[i] > lowest){ 
       while(stack.size() > 0 && stack.peek() > H[i]){ 
        stack.pop(); 
       } 
       if(stack.size() > 0 && stack.peek() < H[i]){ 
        stack.push(H[i]); 
        count++; 
       } 
      } 
     } 
     } 

     return count; 
    } 
}

來源

2014-10-07 user137717

我沒有打擾閱讀的問題，而是這部分看起來令人擔憂，以我爲'（INT I = 1 ; i gerrytan 2014-10-07 04:16:10

我確定。 H [i]與H [i-1]進行比較。 H [0]用於初始化上面的一些事情。 – user137717 2014-10-07 04:18:12

，可以發現一個可能的問題是LinkedList的管理不當時H[i]==lowest。當H[i]==lowest時，程序應該只用一個最低的塊來重置鏈表。簡單地將第二個if塊更正爲：

if(H[i] <= lowest){ 
    while(stack.size() > 0){ 
     stack.pop(); 
    } 
    stack.push(H[i]);     
    if (H[i]!=lowest) 
    { 
     lowest = H[i]; 
     count++; 
    } 
}

考慮案例H = {1,4,3,4,1,4,3,4,1}。正確的輸出是7，而您的代碼返回6.

當i is 6出現問題。第三個if塊的while循環將stack重置爲{3,1}，這導致stack.peek() < H[i]即將發生if-block失敗（stack.peek（）= H [6] = 3）。

此外，三個if塊可以重寫爲if-else-if-else-if block，因爲H [i]的值只能滿足任何i的三個條件之一。

來源

2014-10-07 07:58:00 hk6279

import java.util.*; 

class Solution { 
    public int solution(int[] H) { 
     Stack<Integer> stack = new Stack<Integer>(); 
     int count = 1; 

     stack.push(H[0]); 

     for (int i = 1; i < H.length; i++) { 
      if (stack.empty()) { 
       stack.push(H[i]); 
       count++; 
      } 
      if (H[i] > stack.peek()) { 
       stack.push(H[i]); 
       count++; 
      } 
      while (H[i] < stack.peek()) { 
       stack.pop(); 
       if (stack.empty()) { 
        stack.push(H[i]); 
        count++; 
       } else if (H[i] > stack.peek()) { 
        stack.push(H[i]); 
        count++; 
       } 
      } 
     } 
     return count;  
    } 
}

來源

2014-12-03 17:05:33 dorado

我打算添加另一個Java解決方案100/100，我添加了自己的Stack類。

https://codility.com/demo/results/demoX7Z9X3-HSB/

下面的代碼：

import java.util.ArrayList; 
import java.util.List; 

public class StoneWall { 

     public int solution(int[] H) { 
      int len = H.length; 
      Stack<Integer> stack = new Stack<>(len); 
      int blockCounter = 0; 

      for (int i = 0; i < len; ++i) { 
       int element = H[i]; 
       if (stack.isEmpty()) { 
        stack.push(element); 
        ++blockCounter; 
       } else { 
        while (!stack.isEmpty() && stack.peek() > element) { 
         stack.pop(); 
        } 
        if (!stack.isEmpty() && stack.peek() == element) { 
        continue; 
        } else { 
         stack.push(element); 
         ++blockCounter; 
        } 
       } 
      } 

      return blockCounter; 
     } 

     public static class Stack<T> { 
      public List<T> stack; 

      public Stack(int capacity) { 
       stack = new ArrayList<>(capacity); 
      } 

      public void push(T item) { 
       stack.add(item); 
      } 

      public T pop() { 
       T item = peek(); 
       stack.remove(stack.size() - 1); 
       return item; 
      } 

      public T peek() { 
       int position = stack.size(); 
       T item = stack.get(position - 1); 
       return item; 
      } 

      public boolean isEmpty() { 
       return stack.isEmpty(); 
      } 
     } 
    }

任何反饋將不勝感激。

來源

2015-08-14 06:25:57 moxi

最後，我有足夠的觀點能夠留下我的反饋：我在代碼中將更改的是for循環中的初始if塊。這是爲什麼：你在for循環結束時檢查堆棧是否爲空，然後在循環開始時執行相同的檢查;所以如果在循環結束時堆棧是空的，你會將一個元素放在堆棧頂部，如果不是，你會繼續下一個迭代並直接進入測試。無論哪種方式，這意味着該堆棧在該點上至少有一個元素，從而不需要初始測試。 – 2016-04-20 05:20:11

這個測試只有在你的棧最初是空的時候纔有意義，但是如果你看一下編碼測試的要求，它說數組肯定至少有一個元素，因此你可以安全地將它推到棧頂for循環的開始。值得注意的是：我沒有被允許將所有內容放在一個註釋中 – 2016-04-20 05:20:47

這裏是@moxi代碼的Scala版本：

import scala.collection.mutable 


object Solution { 
    def solution(H: Array[Int]): Int = { 

    val stack = new mutable.Stack[Int]() 

    var blockCounter :Int = 0 

    for (i <- 0 to (H.length-1)) { 

     var element = H(i) 

     if (stack.isEmpty) { 
     stack.push(element) 
     blockCounter = blockCounter+1 
     } else { 
     while (!stack.isEmpty && stack.top > element) { 
      stack.pop() 
     } 
     if (!stack.isEmpty && stack.top == element) { 

     } else { 
      stack.push(element) 
      blockCounter = blockCounter+1 
     } 
     } 
    } 

    return blockCounter 

    } 
}

https://codility.com/demo/results/trainingM3BDSK-3YV/

來源

2015-10-18 16:13:57 grubjesic

這是我的100/100 Java解決方案。

public static int solution(int[] H) { 
    // write your code in Java SE 8 
    Stack<Integer> s = new Stack<Integer>(); 
    int count = 1; 

    for (int i = 0; i < H.length-1; i++) { 
     if (H[i + 1] > H[i]) { 
      s.push(H[i]); 
      count++; 
     } else if (H[i + 1] < H[i]) { 
      if (s.empty()) { 
       s.push(H[i]); 
       count++; 
      } else if (H[i+1] > s.peek()) { 
       count++; 
      } else if (H[i+1] < s.peek()) { 
       while (!s.empty() && H[i+1] < s.peek()) { 
        s.pop(); 
       } 
       if (s.empty()) { 
        count++; 
       } else if (H[i+1] > s.peek()) { 
        count++; 
       } 
      } else { 
       s.pop(); 
      } 
     } 
    } 
    return count; 
}

來源

2016-01-25 04:27:11 Janath

老問題;希望它仍然有用。在FOR循環中的第三條IF語句中，您並未考慮H [i] ==最低的情況。

試試這個：

if(H[i] < H[i-1] && H[i] >= lowest){ 
    while(stack.size() > 0 && stack.peek() > H[i]){ 
     stack.pop(); 
    } 
    if(stack.size() > 0 && stack.peek() < H[i]){ 
     stack.push(H[i]); 
     count++; 
    } 
}

而且（但是這僅僅是一個次要的事情）使用一個變量來存儲最低是沒有必要的。通過相應地瀏覽和彈出，您可以輕鬆地從堆棧中檢索最低值。此外，您可以使代碼更清晰，避免與堆棧頭部進行一次比較，一次最低。希望這是有道理的。這是我的解決方案。

import java.util.Stack; 
class Solution { 
    public int solution(int[] H) { 
     // write your code in Java SE 8 
     Stack<Integer> sittingOn = new Stack<Integer>(); 
     sittingOn.push(H[0]); 
     int counter = 1; 
     for(int i = 1; i < H.length; i++){ 
      if(sittingOn.peek() < H[i]){ 
       counter++; 
       sittingOn.push(H[i]); 
      } 
      else{ 
       while (!sittingOn.isEmpty() && sittingOn.peek() > H[i]){ 
        sittingOn.pop(); 
       } 
       if (sittingOn.isEmpty() || sittingOn.peek() != H[i]){ 
        sittingOn.push(H[i]); 
        counter++; 
       } 
      } 
     } 
    }   
    return counter; 
}

這裏是它的精簡版本我在評論中提到：

import java.util.Stack; 
class Solution { 
    public int solution(int[] H) { 
     // write your code in Java SE 8 
     Stack<Integer> sittingOn = new Stack<Integer>(); 
     sittingOn.push(H[0]); 
     int counter = 1; 
     for(int i = 1; i < H.length; i++){ 
      while (!sittingOn.isEmpty() && sittingOn.peek() > H[i]){ 
       sittingOn.pop(); 
      } 
      if (sittingOn.isEmpty() || sittingOn.peek() != H[i]){ 
       sittingOn.push(H[i]); 
       counter++; 
      } 
     } 
    }   
    return counter; 
}

來源

2016-03-09 11:25:50

值得注意的是，即使刪除了第一個IF語句塊（第二個IF也會覆蓋該情況），該解決方案仍然可以工作，但它隨着更多（不必要的）測試的進行會變慢。而且，使用LinkedList而不是Stack來實現堆棧會使其效率更高。 – 2016-03-09 23:00:01

曼哈頓天際線覆蓋失敗一些測試案例

回答

相關問題