不是很糊涂

Google中国编程挑战赛

                                      

    上个月在网上看到了Google编程挑战赛的广告，于是就报名想去看看，虽然水平应该达不到那种程度，但还是想看看到底是什么题目，于是就注册了个用户，下载软件，进入测试环境，一共三道练习题目，都比较简单，一会就做完了，不过后来实际比赛的时候的题目是要更难一些的。昨天12点开始的比赛，因为在上班，所以准备回去在做，结果晚上回去怎么也进不去，只好今天上午来到公司做了，进入的倒是很顺利，打开250分的第一题，题目比较简单，想了一下就开始写代码，保存，编译，测试，结果网络不稳定，保存需要等好久，编译又是等，测试还是等，结果就一遍一遍的修改、编译、测试，把时间都耗费在这个上面了，当时也没想到去外边开个IDE测试好了再弄进来，后悔啊！不过在剩下10多分钟的时候终于提交了代码，一看得分，95.5分，好低啊.....排名在这个房间就排到了83名去了....看来水平还是有限，得多加学习了！

第一题250分，题目：

Problem Statement

You are given a String disk representing the clusters on a disk. An 'X' represents a used cluster, and a '.' represents an available cluster. You are also given an int size representing the size, in clusters, of a file waiting to be written to disk. A file can only be stored in clusters not already being used.
Return the minimum number of groups of consecutive clusters needed to store the file on the disk. (The disk does not wrap around at the end.) Return -1 if the disk does not have enough space available to store the file.
Definition

Class:
DiskClusters
Method:
minimumFragmentation
Parameters:
String, int
Returns:
int
Method signature:
int minimumFragmentation(String disk, int size)
(be sure your method is public)

Constraints
-
disk will contain between 1 and 50 characters, inclusive.
-
Each character of disk will be 'X' or '.'.
-
size will be between 1 and 50, inclusive.
Examples
0)

"."
2
Returns: -1
We can't fit the file on the disk.
1)

".XXXXXXXX.XXXXXX.XX.X.X."
6
Returns: 6
There is only ever one cluster together, so all six clusters are separated.
2)

"XX..XX....X.XX........X...X.XX...XXXX..XX...XXXXX."
12
Returns: 2
We fit eight clusters together, and four clusters together.
3)

".X.XXXX.......XX....X.....X............XX.X.....X."
20
Returns: 3

4)
"....X...X..X"
11
Returns: -1

我的程序：

public class DiskClusters
{
    public int minimumFragmentation(String disk,int size)
    {
     int ret = -1;
     int total = 0;
     int[] value = new int[50];
     int index = 0;
     int count = 0;
     for(int i=0;i<50;i++)
         value[i] = -1;
     for(int i=0;i     {
         if(disk.charAt(i) == '.')
         {
             index++;
         }
         else
         {
             value[count]=index;
             count++;
             index = 0;
         }
     }
     
     value[count++]=index;
     int resultCount = 0;
     while(true)
     {
         if(total == size)
             break;
         int max = -1;
         int i;
         int maxIndex = 0;
         for(i=0;i         {
             if(max < value[i]){
                 max = value[i];
                 maxIndex = i;
             }
         }
         if(max == -1)
             return -1;
        if(total + max >= size)
        {
            resultCount++;
            break;
        }
        else
        {
            value[maxIndex] = -1;
            resultCount++;
            total+=max;
        }
     }     
     return resultCount;
     
    }
}

第二题750分题目：

Problem Statement
    
You are playing a card game, and in your hand, you are holding several cards. Each card has a suit, 'S', 'H', 'D', or 'C', and a value between 1 and 10, inclusive. You may play cards as part of a set, which is three or more cards of the same value, or as part of a run, which is three or more cards of the same suit, in sequential order. (Runs may not wrap, thus, 9-10-1 is not a valid run.) Each card may be played only once.
For example, "1 S", "1 H" and "1 D" would be a valid set. "2 S", "3 S", and "4 S" would be a valid run.
You want to play as many cards as possible, maybe in several plays (see example 4). Given a String[] cards representing the cards held in your hand, you are to return an int indicating the maximum number of cards you can play. Each card will be given in the form "value suit" (quotes added for clarity).
Definition
    
Class:
PlayCards
Method:
maxCards
Parameters:
String[]
Returns:
int
Method signature:
int maxCards(String[] cards)
(be sure your method is public)
    

Constraints
-
cards will contain between 0 and 20 elements, inclusive.
-
No two elements of cards will be the same.
-
Each element of cards will be of the form "value suit" (quotes added for clarity).
-
Each number represented will be between 1 and 10, inclusive, with no leading zeroes.
-
Each suit represented will be 'S', 'H', 'D', or 'C'.
Examples
0)

    
{"1 S", "2 S", "3 S"}
Returns: 3
We have a run of three cards, which we can play.
1)

    
{"4 C", "4 D", "4 S", "3 S", "2 S"}
Returns: 3
We can take the 4's as a set, or we can take the 2-3-4 run. Either way, we play 3 cards.
2)

    
{"1 S", "2 S", "2 H", "3 H", "3 D", "4 D", "4 C", "5 C", "5 S"}
Returns: 0
We've got lots of cards, but no way to put three together.
3)

    
{"1 S", "2 S"}
Returns: 0
Since we have to play at least three cards at a time, there's nothing to do here.
4)

    
{"1 S", "2 S", "10 S", "5 S", "8 S",
 "3 H", "9 H", "6 H", "5 H", "4 H",
 "10 D", "5 D", "7 D", "4 D", "1 D",
 "2 C", "4 C", "5 C", "6 C", "7 C"}
Returns: 9
The best we can do is to take the set of 4s, the 5-6-7 C, and the remaining three 5s. We could have taken the 4-5-6-7 of C, or all four 5s, but we would not end up playing as many cards.

 

第二题还没来得及做时间就到了，等有时间再研究研究，再做出来练习下。

【作者: CnXiaowei】【访问统计:】【2005年12月13日 星期二 11:18】【 加入博采】【打印】