HackerRack上的道路和圖書館超時

我一直在研究這個HackerRank問題一段時間了，而且我似乎無法理解爲什麼我的代碼在超大輸入大小的情況下超時。我已經將鄰接列表實現爲一個哈希映射來減少時間，並且已經爲我的DFS使用了一個堆棧，按標準來優化它的運行時間。我的基本策略是使用DFS刪除一組連接的節點，並繼續這樣做直到沒有剩餘的節點（我的DFS會在節點到達時刪除節點），問題是在每個圖表後通常有80,000個斷開連接的部分我拿出沒有鄰居的單個節點（所以DFS被稱爲80,000次）。這裏有沒有特別好的策略？HackerRack上的道路和圖書館超時

static int numDisconnected(HashMap<Integer, List<Integer>> adj) { 
    int result = 0; 
    List<Integer> iter = new ArrayList<>(adj.keySet()); 
    for (int k : iter) { 
     if (adj.get(k).size() == 0) { 
     adj.remove(k); 
     result++; 
     } 
    } 
    HashMap<Integer,Boolean> explored = new HashMap<>(); 
    for (int i : adj.keySet()) { 
     explored.put(i,false); 
    } 
    while (!adj.keySet().isEmpty()) { 
     result++; 
     depthFirstSearch(adj,explored); 
    } 
    return result; 
    }

作爲一個參考點，我的代碼大約需要1.5秒鐘在我的機器上運行〜2MB文件輸入。

來源

2017-07-25 robcarney

我建議你做一些分析和縮小問題的代碼減少到10條線以下。如果你在這樣做後仍然陷入困境，你可以回來一個更具體的問題。 –

@JoeC我現在要做的就是 – robcarney

一個觀察：所有'HashMap'中的鍵都是連續的整數，所以數組可能更有效。（HackerRank挑戰使用基於1的城市指數，所以一定要減去一個。） – smarx

一般來說，你在做什麼接近，HashMap<Integer, List<Integer>>是完成這個任務，良好的數據結構。但是，通過保留explored列表並從numDisconnected和depthFirstSearch（在問題的早期版本中）的鄰接圖中刪除，您正在完成冗餘工作。其中任何一種都足以實現深度優先搜索。

我調整了你的算法，不用從adj中刪除，將explored更改爲boolean []，並使用它來瀏覽一個斷開的組件，並找到下一個節點以從組件完成時啓動DFS。

它通過了，不需要預處理步驟去除未連接的節點。

（對不起，意譯，而不是發佈代碼，但我寧願不破壞它）

來源

2017-07-25 23:56:54 Loonquawl

從原始代碼開始（在這個問題上的第一次修訂），我取代那些HashMap s的ArrayList S，使用HashSet爲explored，內聯depthFirstSearch（只是爲了簡單起見，不是性能），並擺脫了一些感覺像過早優化的步驟（刪除沒有鄰居的節點，儘早返回主循環）。

這通過在Roads and Libraries challenge on HackerRank所有測試：

import java.io.*; 
import java.util.*; 

public class Solution { 
    static long cost(long cLib, long cRoad, ArrayList<List<Integer>> g, int gSize) { 
     if (cLib <= cRoad) { 
      return cLib * (long)gSize; 
     } 
     int discon = numDisconnected(g); 
     return (cRoad * (gSize - discon)) + (cLib * discon); 
    } 

    static int numDisconnected(ArrayList<List<Integer>> adj) { 
     int result = 0; 
     HashSet<Integer> explored = new HashSet<>(); 
     int length = adj.size(); 
     for (int i = 0; i < length; i++) { 
      if (!explored.contains(i)) { 
       Stack<Integer> stack = new Stack<>(); 
       stack.push(i); 
       while (!stack.empty()) { 
        int curr = stack.pop(); 
        explored.add(curr); 
        for (int neighbor : adj.get(curr)) { 
         if (!explored.contains(neighbor)) { 
          stack.push(neighbor); 
         } 
        } 
       } 

       result += 1; 
      } 
     } 
     return result; 
    } 

    public static void main(String[] args) { 
     Scanner in = new Scanner(System.in); 
     int q = in.nextInt(); 
     for(int a0 = 0; a0 < q; a0++){ 
      int nCities = in.nextInt(); 
      ArrayList<List<Integer>> adj = new ArrayList<List<Integer>>(nCities); 
      for (int i = 0; i < nCities; i++) { 
       adj.add(new ArrayList<Integer>()); 
      } 
      int nRoads = in.nextInt(); 
      long cLib = in.nextLong(); 
      long cRoad = in.nextLong(); 
      for (int i = 0; i < nRoads; i++) { 
       int city_1 = in.nextInt() - 1; 
       int city_2 = in.nextInt() - 1; 
       adj.get(city_1).add(city_2); 
       adj.get(city_2).add(city_1); 
      } 
      System.out.println(cost(cLib, cRoad, adj, nCities)); 
     } 
    } 
}

來源

2017-07-25 23:49:17 smarx

HackerRack上的道路和圖書館超時

回答

相關問題