поиск дерева в скале - PullRequest
Новая
       16

поиск дерева в скале

0 голосов
/ 02 июня 2011

Я пытаюсь сделать свои первые шаги в Scala, и на практике я взглянул на google code jam storecredit excersize .Сначала я попробовал это в java, что прошло достаточно хорошо, и теперь я пытаюсь перенести его в Scala.Теперь с фреймворком java collection я мог бы попытаться выполнить прямое преобразование синтаксиса, но в итоге я написал бы java на scala, и это побеждает цель.В моей реализации Java у меня есть PriorityQueue, который я опустошаю в Deque, и выталкиваю концы до тех пор, пока у нас не будет бинго.Все это использует изменчивые коллекции, которые дают мне ощущение «un-scala».То, что я считаю более функциональным подходом, - это построение структуры данных, которая может проходить как от самой высокой к самой низкой, так и от самой низкой к самой высокой.Я на правильном пути?Есть ли подходящие структуры данных, поставляемые в библиотеках 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));
    }

}

1 Ответ

1 голос
/ 02 июня 2011

Мне интересно, чего вы пытаетесь достичь, используя сложные структуры данных, такие как 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))
  }
}
...