亚洲综合网中心,五月综合激情,亚洲黄色中文字幕

SongFilter (入圍賽250真題)

Problem Statement
????
You have a collection of music files with names formatted as "genre-artist-album-song" (quotes for clarity only), where genre, artist, album, and song each consist of only lowercase letters ('a'-'z') and spaces (but no leading/trailing spaces). The collection is given in the String[] collection. You would like to filter the songs according to a set of criteria given in the String[] filterInfo. Each element of filterInfo is an equality check formatted as "field=value" (quotes for clarity only), where field is "genre", "artist", "album", or "song", and value consists of only lowercase letters ('a'-'z') and spaces (but no leading/trailing spaces). For a file to pass through the filter, it must satisfy every equality check in filterInfo. For example, if filterInfo = {"genre=country", "album=greatest hits"}, only songs from country greatest hits albums should be returned. Return a String[] containing all the files that meet the given criteria in the same relative order as they appear in collection.
Definition
????
Class:
SongFilter
Method:
filter
Parameters:
String[], String[]
Returns:
String[]
Method signature:
String[] filter(String[] collection, String[] filterInfo)
(be sure your method is public)
????

Constraints
-
collection will contain between 1 and 50 elements, inclusive.
-
Each element of collection will be formatted as described in the problem statement.
-
Each element of collection will contain between 7 and 50 characters, inclusive.
-
Each genre, artist, album, and song in collection will contain between 1 and 20 characters, inclusive.
-
collection will contain no duplicate elements.
-
filterInfo will contain between 1 and 4 elements, inclusive.
-
Each element of filterInfo will be formatted as described in the problem statement.
-
Each value in filterInfo will contain between 1 and 20 characters, inclusive.
Examples
0)

????
{"jazz-joe pass-virtuoso-cherokee",
"rock-led zeppelin-ii-lemon song",
"country-dwight yoakam-long way home-things change",
"metal-iron maiden-powerslave-aces high",
"pop-supremes-more hits-ask any girl",
"rock-faith no more-angel dust-rv",
"jazz-chuck mangione-feels so good-feels so good",
"rock-van halen-ii-spanish fly"}
{"genre=rock", "album=ii"}
Returns: {"rock-led zeppelin-ii-lemon song", "rock-van halen-ii-spanish fly" }
This filter returns all the rock songs from albums with the title "ii".
1)

????
{"rock-jimi hendrix-axis bold as love-little wing",
"rock-cars-cars-moving in stereo",
"rock-jimi hendrix-electric ladyland-gypsy eyes",
"blues-albert collins-ice pickin-ice pick",
"rock-jimi hendrix-axis bold as love-bold as love",
"rock-jimi hendrix-axis bold as love-exp"}
{"artist=jimi hendrix", "album=axis bold as love"}
Returns:
{"rock-jimi hendrix-axis bold as love-little wing",
"rock-jimi hendrix-axis bold as love-bold as love" }
This filter returns all the songs that are from the album "axis bold as love" by the artist "jimi hendrix". The last element in the collection is not returned because there are two spaces between "jimi" and "hendrix".
2)

????
{"rock-ozzy osbourne-blizzard of ozz-dee",
"rock-marvelous three-hey album-let me go",
"rock-cheap trick-in color-downed"}
{"genre=soul"}
Returns: { }
There is no soul music in this collection, so an empty String[] is returned.
3)

????
{"country-topcoder-the country album-twangy",
"rock-topcoder-the rock album-rockin",
"jazz-topcoder-the jazz album-jazzy",
"soul-topcoder-the soul album-soulful",
"metal-topcoder-the metal album-thrash"}
{"artist=topcoder", "genre=jazz", "album=the jazz album", "song=jazzy"}
Returns: {"jazz-topcoder-the jazz album-jazzy" }

????
{"pop-jackson five-abc-the love you save",
"rock-ac dc-powerage-riff raff"}
{"genre=pop", "genre=rock"}
Returns: { }
No single element of collection can represent more than one genre, so this filter returns an empty String[].
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

posted on 2005-08-23 11:47 emu 閱讀(1324) 評論(9) 編輯收藏所屬分類: google編程大賽模擬題及入圍賽真題

這也太容易了吧？

import java.util.*;

public class SongFilter {
    public static void main(String[] args) {
        String[] collection, filterInfo, result;
        SongFilter sf = new SongFilter();
        collection = new String[] {"jazz-joe pass-virtuoso-cherokee",
                     "rock-led zeppelin-ii-lemon song",
                     "country-dwight yoakam-long way home-things change",
                     "metal-iron maiden-powerslave-aces high",
                     "pop-supremes-more hits-ask any girl",
                     "rock-faith no more-angel dust-rv",
                     "jazz-chuck mangione-feels so good-feels so good",
                     "rock-van halen-ii-spanish fly"};
        filterInfo = new String[] {"genre=rock", "album=ii"};
        result = sf.filter(collection, filterInfo);
        for (int i = 0; i < result.length; i++)
            System.out.println(result[i]);
    }

    String[] filterPrefix = new String[] {"genre=", "artist=", "album=",
                            "song="};
    int filterPrefixLength = filterPrefix.length;
    public String[] filter(String[] collection, String[] filterInfo) {
        String[] filter = new String[filterPrefixLength];
        for (int i = 0; i < filterInfo.length; i++)
            for (int j = 0; j < filterPrefixLength; j++)
                if (filterInfo[i].startsWith(filterPrefix[j]))
                    if (filter[j] == null)
                        filter[j] = filterInfo[i].substring(filterPrefix[j].
                                length());
                    else if (!filter[j].equals(filterInfo[i].substring(
                            filterPrefix[j].length())))
                        return new String[0];
        ArrayList tmpResult = new ArrayList();
        for (int i = 0; i < collection.length; i++) {
            String[] collectionDetail = collection[i].split("-"); //genre-artist-album-song
            boolean match = true;
            for (int j = 0; j < filterPrefixLength; j++)
                if (filter[j] != null &&
                    !collectionDetail[j].equals(filter[j]))
                    match = false;
            if (match)
                tmpResult.add(collection[i]);
        }
        String[] result = new String[tmpResult.size()];
        tmpResult.toArray(result);
        return result;
    }
}

  回復   更多評論

# re: SongFilter (入圍賽250真題) 2005-12-08 17:37 drekar

我用正則表達式做的：

import java.util.ArrayList;
import java.util.regex.Pattern;

public class SongFilter {

public String[] filter(String[] collection, String[] filterInfo) {
if (null == collection || null == filterInfo || filterInfo.length > 4)
return null;

// build filter pattern
String [] filters = {"([a-z\\s]+)", "([a-z\\s]+)", "([a-z\\s]+)", "([a-z\\s]+)"};
for (int i=0; i<filterInfo.length; i++) {
String[] temp = filterInfo[i].split("=");

if (temp[0].equals("genre")) filters[0] = temp[1];
else if (temp[0].equals("artist")) filters[1] = temp[1];
else if (temp[0].equals("album")) filters[2] = temp[1];
else /* "song" */ filters[3] = temp[1];
}
String filterPattern = filters[0] + "-" + filters[1] + "-" + filters[2] + "-" + filters[3];

ArrayList tmpResult = new ArrayList();
Pattern p = Pattern.compile(filterPattern);
for (int i=0; i<collection.length; i++)
if (p.matcher(collection[i]).matches())
tmpResult.add(collection[i]);

String[] result = new String[tmpResult.size()];
tmpResult.toArray(result);
return result;
}

/**
* 程序主入口
*
* @param args
*/
public static void main(String[] args) {
SongFilter sf = new SongFilter();
String [] myCollection = {"jazz-joe pass-virtuoso-cherokee",
"rock-led zeppelin-ii-lemon song",
"country-dwight yoakam-long way home-things change",
"metal-iron maiden-powerslave-aces high",
"pop-supremes-more hits-ask any girl",
"rock-faith no more-angel dust-rv",
"jazz-chuck mangione-feels so good-feels so good",
"rock-van halen-ii-spanish fly"};
String [] myFilter = {"genre=rock", "album=ii"};

String [] result = sf.filter(myCollection, myFilter);
for (int i = 0; i < result.length; i++)
System.out.println(result[i]);

}
} 回復更多評論

# re: SongFilter (入圍賽250真題) 2005-12-08 17:47 drekar

重新排了一下版：

import java.util.ArrayList;
import java.util.regex.Pattern;

public class SongFilter {

　public String[] filter(String[] collection, String[] filterInfo) {
　　if (null == collection || null == filterInfo || filterInfo.length > 4)
　　　return null;
　　
　　// build filter pattern
　　String [] filters = {"([a-z\\s]+)", "([a-z\\s]+)", "([a-z\\s]+)", "([a-z\\s]+)"};
　　for (int i=0; i<filterInfo.length; i++) {
　　　String[] temp = filterInfo[i].split("=");

　　　if (temp[0].equals("genre"))　　　filters[0] = temp[1];
　　　else if (temp[0].equals("artist"))　filters[1] = temp[1];
　　　else if (temp[0].equals("album"))　filters[2] = temp[1];
　　　else　　　　　　　/* "song" */　 filters[3] = temp[1];
　　}
　　String filterPattern = filters[0] + "-" + filters[1] + "-" + filters[2] + "-" + filters[3];

　　ArrayList tmpResult = new ArrayList();
　　Pattern p = Pattern.compile(filterPattern);
　　for (int i=0; i<collection.length; i++)
　　　if (p.matcher(collection[i]).matches())
　　　　tmpResult.add(collection[i]);
　　
　　　　String[] result = new String[tmpResult.size()];
　　　　tmpResult.toArray(result);
　　　　return result;
　}

　/**
　 * 程序主入口
　 *
　 * @param args
　 */
　public static void main(String[] args) {
　　SongFilter sf = new SongFilter();
　　String [] myCollection = {"jazz-joe pass-virtuoso-cherokee",
　　　　 "rock-led zeppelin-ii-lemon song",
　　　　 "country-dwight yoakam-long way home-things change",
　　　　 "metal-iron maiden-powerslave-aces high",
　　　　 "pop-supremes-more hits-ask any girl",
　　　　 "rock-faith no more-angel dust-rv",
　　　　 "jazz-chuck mangione-feels so good-feels so good",
　　　　 "rock-van halen-ii-spanish fly"};
　　String [] myFilter = {"genre=rock", "album=ii"};
　　
　　String [] result = sf.filter(myCollection, myFilter);
　　　　for (int i = 0; i < result.length; i++)
　　　　　　System.out.println(result[i]);
　}
} 回復更多評論

# re: SongFilter (入圍賽250真題) 2005-12-08 20:55 emu

不錯。開始編譯通不過嚇了我一跳，原來你用中文空格替換掉制表符了。

用正則做要比我的做法好一點，需要匹配復雜一點的規則的時候很容易改。

我不用正則是因為之前從來沒有在java里面用過正則，當時趕時間什么熟悉用什么，不可能臨時抱佛腳去查手冊。

此外題目中沒有明確，filter的條件能否重復定義，如果重復了是按照“與”邏輯還是“或”邏輯處理。（“For a file to pass through the filter, it must satisfy every equality check in filterInfo”暗示了這種情況下也應該按照與邏輯）所以在這組數據下：
collection = new String[] {"jazz-joe pass-virtuoso-cherokee",
"rock-led zeppelin-ii-lemon song",
"country-dwight yoakam-long way home-things change",
"metal-iron maiden-powerslave-aces high",
"pop-supremes-more hits-ask any girl",
"rock-faith no more-angel dust-rv",
"jazz-chuck mangione-feels so good-feels so good",
"rock-van halen-ii-spanish fly"};

filterInfo = new String[] {"genre=rock", "album=ii", "album=angel dust"};

我的答案是空數組（按照與邏輯），而你的卻返回
rock-faith no more-angel dust-rv，匹配最后出現的相同條件。

想想，用正則的話這個與或邏輯如何寫？

回復更多評論

# re: SongFilter (入圍賽250真題) 2005-12-09 09:56 drekar

呵呵，不知道你是怎么排版的，只好用中文空格了。

我確實沒想到filter出現重復定義的情況，下面是修改后的代碼。

（1）如果是邏輯“或”的話filter改為

　public String[] filter(String[] collection, String[] filterInfo) {
　　if (null == collection || null == filterInfo)
　　　return new String[0];
　　
　　// build filter pattern
　　String[] filters = { "", "", "", "" };
　　for (int i = 0; i < filterInfo.length; i++) {
　　　String[] temp = filterInfo[i].split("=");

　　　if (temp[0].equals("genre"))　　　　filters[0] += "|(" + temp[1] + ")";
　　　else if (temp[0].equals("artist"))　　filters[1] += "|(" + temp[1] + ")";
　　　else if (temp[0].equals("album"))　 filters[2] += "|(" + temp[1] + ")";
　　　else　　　　　 /* "song" */　　　 filters[3] += "|(" + temp[1] + ")";
　　}
　　
　　for (int i = 0; i < 4; i++) {
　　　if (filters[i].equals(""))
　　　　filters[i] = "([a-z\\s]+)";
　　　else
　　　　filters[i] = "(" + filters[i].substring(1) + ")";
　　}

　　String filterPattern = filters[0] + "-" + filters[1] + "-" + filters[2] + "-" + filters[3];
　　
　　ArrayList tmpResult = new ArrayList();
　　Pattern p = Pattern.compile(filterPattern);
　　for (int i=0; i<collection.length; i++)
　　　if (p.matcher(collection[i]).matches())
　　　　tmpResult.add(collection[i]);
　　
　　　　String[] result = new String[tmpResult.size()];
　　　　tmpResult.toArray(result);
　　　　return result;
　}

（2）如果是邏輯“與”的話filter改為
　public String[] filter(String[] collection, String[] filterInfo) {
　　if (null == collection || null == filterInfo)
　　　return new String[0];
　　
　　// build filter pattern
　　String[] filters = { "", "", "", "" };
　　for (int i = 0; i < filterInfo.length; i++) {
　　　String[] temp = filterInfo[i].split("=");

　　　if (temp[0].equals("genre"))　　　　filters[0] += "_" + temp[1];
　　　else if (temp[0].equals("artist"))　　filters[1] += "_" + temp[1];
　　　else if (temp[0].equals("album"))　 filters[2] += "_" + temp[1];
　　　else　　　　　 /* "song" */　　　 filters[3] += "_" + temp[1];
　　}
　　
　　for (int i = 0; i < 4; i++) {
　　　if (filters[i].equals(""))
　　　　filters[i] = "([a-z\\s]+)";
　　　else
　　　　filters[i] = filters[i].substring(1);
　　}

　　String filterPattern = filters[0] + "-" + filters[1] + "-" + filters[2] + "-" + filters[3];
　　
　　ArrayList tmpResult = new ArrayList();
　　Pattern p = Pattern.compile(filterPattern);
　　for (int i=0; i<collection.length; i++)
　　　if (p.matcher(collection[i]).matches())
　　　　tmpResult.add(collection[i]);
　　
　　　　String[] result = new String[tmpResult.size()];
　　　　tmpResult.toArray(result);
　　　　return result;
　} 回復更多評論

# re: SongFilter (入圍賽250真題) 2005-12-09 10:05 drekar

進一步，在上面的"與"邏輯代碼里，如果正則表達式里出現了"_"字符，說明無需進行后面的匹配，直接返回結果即可。

下面是修改的filter代碼：
(3) 邏輯"與" （解二）

　final static char invalidChar = '_';
　
　public String[] filter(String[] collection, String[] filterInfo) {
　　if (null == collection || null == filterInfo)
　　　return new String[0];
　　
　　// build filter pattern
　　String[] filters = { "", "", "", "" };
　　for (int i = 0; i < filterInfo.length; i++) {
　　　String[] temp = filterInfo[i].split("=");

　　　if (temp[0].equals("genre"))　　　filters[0] += invalidChar + temp[1];
　　　else if (temp[0].equals("artist"))　filters[1] += invalidChar + temp[1];
　　　else if (temp[0].equals("album"))　filters[2] += invalidChar + temp[1];
　　　else　　　　　 /* "song" */　　　 filters[3] += invalidChar + temp[1];
　　}
　　
　　for (int i = 0; i < 4; i++) {
　　　if (filters[i].equals(""))
　　　　filters[i] = "([a-z\\s]+)";
　　　else
　　　　filters[i] = filters[i].substring(1);
　　}

　　String filterPattern = filters[0] + "-" + filters[1] + "-" + filters[2] + "-" + filters[3];
　　if (filterPattern.indexOf(invalidChar) >= 0)
　　　return new String[0];
　　
　　ArrayList tmpResult = new ArrayList();
　　Pattern p = Pattern.compile(filterPattern);
　　for (int i=0; i<collection.length; i++)
　　　if (p.matcher(collection[i]).matches())
　　　　tmpResult.add(collection[i]);
　　
　　　　String[] result = new String[tmpResult.size()];
　　　　tmpResult.toArray(result);
　　　　return result;
　} 回復更多評論

# re: SongFilter (入圍賽250真題) 2005-12-09 10:53 emu

呵呵，250分的小題目也要小心在意啊。上次我記得入圍的全部都是三道全對的。

測了一下，在這個條件下：
String [] myFilter = {"genre=rock", "album=ii", "album=ii"};

你的與邏輯居然返回空！你寫完程序不測功能的嗎？
回復更多評論

# re: SongFilter (入圍賽250真題) 2005-12-09 13:25 drekar

見教的是。慚愧啊。
又改了一下“與邏輯”:

　final static String WildCardString = "([a-z\\s]+)";
　
　public String[] filter(String[] collection, String[] filterInfo) {
　　if (null == collection || null == filterInfo)
　　　return new String[0];
　　
　　// build filter pattern
　　String[] filterNames = {"genre", "artist", "album", "song"};
　　String[] filters = { WildCardString, WildCardString, WildCardString, WildCardString };

　　for (int i = 0; i < filterInfo.length; i++) {
　　　String[] temp = filterInfo[i].split("=");

　　　for (int j = 0; j < 4; j++)
　　　　if (temp[0].equals(filterNames[j])) {
　　　　　if (filters[j].equals(WildCardString))
　　　　　　filters[j] = temp[1]; // set filter
　　　　　else if (!filters[j].equals(temp[1]))
　　　　　　return new String[0]; // conflicting filters
　　　　　break;
　　　　}
　　}
　　
　　String filterPattern = filters[0] + "-" + filters[1] + "-" + filters[2] + "-" + filters[3];
　　
　　ArrayList tmpResult = new ArrayList();
　　Pattern p = Pattern.compile(filterPattern);
　　for (int i=0; i<collection.length; i++)
　　　if (p.matcher(collection[i]).matches())
　　　　tmpResult.add(collection[i]);
　　
　　　　String[] result = new String[tmpResult.size()];
　　　　tmpResult.toArray(result);
　　　　return result;
　} 回復更多評論

# re: SongFilter (入圍賽250真題) 2005-12-09 14:47 emu

else if (!filters[j].equals(temp[1]))
return new String[0]; // conflicting filters

跟我的

else if (!filter[j].equals(filterInfo[i].substring(filterPrefix[j].length())))
return new String[0];

同出一轍呵呵回復更多評論

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: 沒忍住手癢做了一道題，結果還沒作對。差點被燕潘考倒了 1000分模擬題CraneWork 500分模擬題 MaximalPalindromeSubstrings 250分模擬題 SalesRouting SecretSum (code jam china round2 500分真題) FactorialSystem (code jam china round2 300分真題) RecurringNumbers (code jam china 1000分真題) google中國編程挑戰賽入圍賽真題 -- HardDuplicateRemover(1000分) google中國編程挑戰賽入圍賽真題 -- BlockStructure(500分)

emu in blogjava

公告

常用鏈接

留言簿(92)

隨筆分類(20)

隨筆檔案(171)

文章分類(89)

文章檔案(103)

相冊

收藏夾(46)

友情連接

收藏

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

評論