scala的搜索樹

Question

我試圖把我的第一步放入Scala，並且練習我看了一下the google code jam storecredit excersize。我先用java試了一下，這足夠好了，現在我試圖將它移植到Scala。現在使用java集合框架，我可以嘗試進行直接的語法轉換，但最終我會在scala中編寫java，而這種做法會使目標失敗。在我的Java實現中，我有一個PriorityQueue，我將其清空爲Deque，然後彈出結尾，直到我們有賓果。這一切都使用可變的集合，這給我的感覺是非常'不可思議的'。我認爲更有效的方法是構建一個可以從最高到最低，從最低到最高遍歷的數據結構。我在正確的道路上嗎？ Scala庫中是否有適合的數據結構，或者我應該在這裏推出自己的數據結構？

編輯：在Java中簡單得多的版本的完整代碼。它應該在O(max(credit,inputchars))運行，並已成爲：

import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.util.Arrays; 

public class StoreCredit { 
    private static BufferedReader in; 

    public static void main(String[] args) { 
     in = new BufferedReader(new InputStreamReader(System.in)); 
     try { 
      int numCases = Integer.parseInt(in.readLine()); 
      for (int i = 0; i < numCases; i++) { 
       solveCase(i); 
      } 
     } catch (IOException e) { 
      e.printStackTrace(); 
     } 

    } 

    private static void solveCase(int casenum) throws NumberFormatException, 
      IOException { 
     int credit = Integer.parseInt(in.readLine()); 
     int numItems = Integer.parseInt(in.readLine()); 
     int itemnumber = 0; 
     int[] item_numbers_by_price = new int[credit]; 
     Arrays.fill(item_numbers_by_price, -1); // makes this O(max(credit, 
               // items)) instead of O(items) 
     int[] read_prices = readItems(); 
     while (itemnumber < numItems) { 
      int next_price = read_prices[itemnumber]; 
      if (next_price <= credit) { 
       if (item_numbers_by_price[credit - next_price] >= 0) { 
        // Bingo! DinoDNA! 
        printResult(new int[] { 
          item_numbers_by_price[credit - next_price], 
          itemnumber }, casenum); 
        break; 
       } 
       item_numbers_by_price[next_price] = itemnumber; 
      } 
      itemnumber++; 
     } 
    } 

    private static int[] readItems() throws IOException { 
     String line = in.readLine(); 
     String[] items = line.split(" "); // uh-oh, now it's O(max(credit, 
              // inputchars)) 
     int[] result = new int[items.length]; 
     for (int i = 0; i < items.length; i++) { 
      result[i] = Integer.parseInt(items[i]); 
     } 
     return result; 
    } 

    private static void printResult(int[] result, int casenum) { 
     int one; 
     int two; 
     if (result[0] > result[1]) { 
      one = result[1]; 
      two = result[0]; 
     } else { 
      one = result[0]; 
      two = result[1]; 
     } 
     one++; 
     two++; 
     System.out.println(String.format("Case #%d: %d %d", casenum + 1, one, 
       two)); 
    } 

} 

Answer 1

我想知道您嘗試使用複雜的數據結構，如PriorityQueue和Deque的問題，像這樣完成的任務。它可以用一對嵌套循環來解決：

for { 
    i <- 2 to I 
    j <- 1 until i 
    if i != j && P(i-1) + P(j - 1) == C 
} println("Case #%d: %d %d" format (n, j, i)) 

比線性更差，比二次方好。由於這些項目沒有排序，並且對它們進行排序需要O(nlogn)，所以你不能做得比這更好 - 就我所見。其實，說了這麼多，我現在已經想通過線性時間來做到這一點。訣竅是，對於每個編號p，你會發現它的補充是：C - p。我期望有幾種方法可以探索這一點 - 我至今已經想到了兩種。

一種方法是構建具有O(n)特性的地圖，如位圖或散列圖。對於每個元素，使其指向它的索引。然後只需要找到一個元素，其補碼在地圖中也有一個條目。簡而言之，這可以像這樣簡單：

val PM = P.zipWithIndex.toMap 
val (p, i) = PM find { case (p, i) => PM isDefinedAt C - p } 
val j = PM(C - p) 

但是，如果數字等於它的補數，那將不起作用。換句話說，如果有兩個p這樣的p + p == C。例子中有很多這樣的情況。然後可以測試這種情況，然後使用indexOf和lastIndexOf - 除了有可能只有一個p這樣p + p == C，在這種情況下，這也不是答案。

所以我結束了一些更復雜的事情，那就是在構建地圖的同時測試補碼的存在。這是完整的解決方案：

import scala.io.Source 

object StoreCredit3 extends App { 
    val source = if (args.size > 0) Source fromFile args(0) else Source.stdin 
    val input = source getLines() 
    val N = input.next.toInt 
    1 to N foreach { n => 
    val C = input.next.toInt 
    val I = input.next.toInt 
    val Ps = input.next split ' ' map (_.toInt) 
    val (_, Some((p1, p2))) = Ps.zipWithIndex.foldLeft((Map[Int, Int](), None: Option[(Int, Int)])) { 
     case ((map, None), (p, i)) => 
     if (map isDefinedAt C - p) map -> Some(map(C - p) -> (i + 1)) 
     else (map updated (p, i + 1), None) 
     case (answer, _) => answer 
    } 

    println("Case #%d: %d %d" format (n, p1, p2)) 
    } 
}