蜜桃视频www网站在线观看,免费高潮视频95在线观看网站,欧美美女在线

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) 評(píng)論(9) 編輯收藏所屬分類: google編程大賽模擬題及入圍賽真題

評(píng)論

# emu的答案 2005-08-23 11:48 emu

這也太容易了吧？

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;
    }
}

  回復(fù)  更多評(píng)論

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

我用正則表達(dá)式做的：

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]);

}
} 回復(fù) 更多評(píng)論

# 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]);
　}
} 回復(fù) 更多評(píng)論

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

不錯(cuò)。開(kāi)始編譯通不過(guò)嚇了我一跳，原來(lái)你用中文空格替換掉制表符了。

用正則做要比我的做法好一點(diǎn)，需要匹配復(fù)雜一點(diǎn)的規(guī)則的時(shí)候很容易改。

我不用正則是因?yàn)橹皬膩?lái)沒(méi)有在java里面用過(guò)正則，當(dāng)時(shí)趕時(shí)間什么熟悉用什么，不可能臨時(shí)抱佛腳去查手冊(cè)。

此外題目中沒(méi)有明確，filter的條件能否重復(fù)定義，如果重復(fù)了是按照“與”邏輯還是“或”邏輯處理。（“For a file to pass through the filter, it must satisfy every equality check in filterInfo”暗示了這種情況下也應(yīng)該按照與邏輯）所以在這組數(shù)據(jù)下：
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"};

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

想想，用正則的話這個(gè)與或邏輯如何寫(xiě)？

回復(fù) 更多評(píng)論

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

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

我確實(shí)沒(méi)想到filter出現(xiàn)重復(fù)定義的情況，下面是修改后的代碼。

（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;
　} 回復(fù) 更多評(píng)論

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

進(jìn)一步，在上面的"與"邏輯代碼里，如果正則表達(dá)式里出現(xiàn)了"_"字符，說(shuō)明無(wú)需進(jìn)行后面的匹配，直接返回結(jié)果即可。

下面是修改的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;
　} 回復(fù) 更多評(píng)論

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

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

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

你的與邏輯居然返回空！你寫(xiě)完程序不測(cè)功能的嗎？
回復(fù) 更多評(píng)論

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

見(jiàn)教的是。慚愧啊。
又改了一下“與邏輯”:

　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;
　} 回復(fù) 更多評(píng)論

# 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];

同出一轍呵呵回復(fù) 更多評(píng)論

新用戶注冊(cè) 刷新評(píng)論列表


只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。




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

emu in blogjava

公告

常用鏈接

留言簿(92)

隨筆分類(20)

隨筆檔案(171)

文章分類(89)

文章檔案(103)

相冊(cè)

收藏夾(46)

友情連接

收藏

搜索

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

評(píng)論