一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1273|回复: 4
收起左侧

[算法题] 请教一下我这个解法怎么不对了--UVa 11418 Clever Naming Patterns

[复制链接] |试试Instant~ |关注本帖
tommy410303 发表于 2015-9-22 14:41:56 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 tommy410303 于 2015-9-22 14:55 编辑

题是这里的:https://uva.onlinejudge.org/inde ... roblem&problem=2413问的是 给一系列词组,仅从每组中按字母表顺序取一个词,比如
有这三个组:
Dog Cat Big
Better
Answer Call


需要取3个词,A,B,C, 开头,每组取一词。第二组的B必须用上,第三组的A必须用上,剩余的第一组就必须取Cat了:
Answer
Better
Cat

很弱很渣所以直接写了一个算是暴力的解法,用linkedlist存所有词组的String[26] array,(不存超范围的词),linear search每次取出仅有一个元素的array entry, 然后删掉其他array的同字母entry...UVa online judge 说 "wrong answer", tim = 0.242 (上限是一秒). 大神们来看下 或者提示提示更好解...
  1. import java.util.Arrays;
  2. import java.util.Scanner;

  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner input = new Scanner(System.in);

  6.         int cases = Integer.parseInt(input.nextLine());

  7.         for (int c = 0; c < cases; c++) // for all cases
  8.         {
  9.             LinkedList listops = new LinkedList();
  10.             int num = input.nextInt();
  11.             input.nextLine();
  12.             // num problems and num lines of options
  13.             for (int n = 0; n < num; n++) {
  14.                 container perLine = new container();
  15.                 int numwords = input.nextInt(); // num options per line
  16.                 for (int word = 0; word < numwords; word++) {
  17.                     String entry = input.next();
  18.                     perLine.add(entry, num);
  19.                 }
  20.                 listops.insertAtHead(perLine);
  21.             }
  22.             // now we have a linked list of containers of words (sorted by
  23.             // container size)
  24.             // now "pop them"
  25.             System.out.println("Case #" + (c + 1));
  26.             listops.printResults(num);
  27.             input.nextLine(); // fire a blank nextLine call after
  28.             // nextInt to get rid of newline left in buffer
  29.         }
  30.         input.close();
  31.         System.exit(0);
  32.     }

  33. }

  34. class container { // custom container class (node)
  35.     private String[] ray;
  36.     public int count;
  37.     public container next;

  38.     container() {
  39.         ray = new String[26];
  40.         next = null;
  41.     }

  42.     container(container n) {
  43.         ray = new String[26];
  44.         next = n;
  45.     }

  46.     void add(String word, int size) {
  47.         String lower = word.toLowerCase();
  48.         int first = lower.charAt(0); // first letter
  49.         // e.g. if size=3, we want a (97), b(98), or c(99), that is >=97,
  50.         // <=99=(96+size)
  51.         if (first > (96 + size) || first < 97)
  52.             return; // simply skip;
  53.         ray[first - 97] = word;
  54.         count++;
  55.     }

  56.     void del(String word) {
  57.         int idx = word.toLowerCase().charAt(0) - 97;
  58.         if (ray[idx] != null) {
  59.             ray[idx] = null;
  60.             count--;
  61.         }

  62.     }

  63.     String get() { // return the only String entry

  64.         int k = 0;
  65.         while (ray[k] == null)
  66.             k++;
  67.         return ray[k];
  68.     }
  69. }

  70. class LinkedList {
  71.     public container head;

  72.     LinkedList() {
  73.         head = null;
  74.     }

  75.     void insertAtHead(container ct) {
  76.         ct.next = head;
  77.         head = ct;
  78.     }

  79.     String getSingleTon() {
  80.         container ptr = head;
  81.         while (ptr != null) {
  82.             if (ptr.count == 1)
  83.                 return ptr.get();
  84.             ptr = ptr.next;
  85.         }
  86.         return null;
  87.     }

  88.     void deleteEntryReorder(String entry) {
  89.         container ptr = head;
  90.         while (ptr != null) {
  91.             ptr.del(entry);
  92.             ptr = ptr.next;
  93.         }
  94.     }

  95.     void printResults(int size) {
  96.         String[] res = new String[size];
  97.         for (int i = 0; i < size; i++) {
  98.             res[i] = getSingleTon();
  99.             deleteEntryReorder(res[i]);
  100.         }
  101.         Arrays.sort(res);
  102.         for (int j = 0; j < res.length; j++)
  103.             System.out.println(res[j].substring(0, 1).toUpperCase()
  104.                     + res[j].substring(1).toLowerCase());
  105.     }

  106. }
复制代码
flexwang 发表于 2015-9-23 16:05:35 | 显示全部楼层
怎么保证会存在仅有一个元素的list呢?
回复 支持 1 反对 0

使用道具 举报

 楼主| tommy410303 发表于 2015-9-24 10:22:24 | 显示全部楼层
本帖最后由 tommy410303 于 2015-9-24 10:26 编辑
flexwang 发表于 2015-9-23 16:05
怎么保证会存在仅有一个元素的list呢?

举个例子:
假如我们需要3个词,这样就有三行input:
s1
s2
s3
根据题设,s1, s2, s3中有且仅有unique的三个词以A, B, C开头的
对于每一行input, 我仅读入以A, B, or C 开头的单词,其余的(D, E, F, etc.) 都扔掉
既然input行数跟需要的单词数相等,每一行只能提供A,B,C开头的一个词;既然这个题说每个case答案都是唯一的,那么必须有一行仅提供一个词,比如s2 提供A词;把s1, s3的可能存在的A词删掉后,这剩余的两行必须uniquely提供B和C开头词,那么必须s1或s3中有单独的B词或C词...

我自己的还有UVa给的那个test input都给出正确答案啊。。。UVa光说个"wrong answer"并无卵...

这个题可能还是要用bipartite matching 来做. 具体还没想好
回复 支持 反对

使用道具 举报

flexwang 发表于 2015-9-24 11:00:23 | 显示全部楼层
tommy410303 发表于 2015-9-24 10:22
举个例子:
假如我们需要3个词,这样就有三行input:
s1

我觉得你是对的 java的看不懂 之前理解错你的意思了
回复 支持 反对

使用道具 举报

 楼主| tommy410303 发表于 2015-9-25 02:54:15 | 显示全部楼层
Ok谢谢 我再研究研究
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 18:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表