emu in blogjava
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  171 随笔 :: 103 文章 :: 1052 评论 :: 2 Trackbacks
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" }

4)

????
{"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 阅读(1297) 评论(9)  编辑  收藏 所属分类: google编程大赛模拟题及入围赛真题

评论

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

  回复  更多评论
  

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

同出一辙呵呵  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: