emu in blogjava
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  171 随笔 :: 103 文章 :: 1052 评论 :: 2 Trackbacks
ImageLayers（入围赛750分真题）



Problem Statement
????
An image editing application allows users to construct images containing multiple layers. When dealing with large images, however, it is sometimes necessary to limit the number of layers due to memory constraints. If certain layers will not be altered during an editing session, they can be merged together to reduce the total number of layers in memory. You are given a macro containing commands to open files and merge layers. Each time a file is opened, it is loaded into a new layer of the current image. Layers are numbered starting at 0 for the bottommost layer, 1 for the layer directly on top of the bottommost layer, etc... Whenever a new layer is created, it is positioned on top of the previous topmost layer. An open command is formatted as "OPEN filename" where filename is the name of the file to open. Consecutive layers can be merged using the merge command, which is formatted as "MERGE layer1-layer2", where layer1 and layer2 specify an inclusive range of layer numbers that exist in the current image. After multiple layers are merged, all the layers are renumbered according to the original specification. For example, if an image contains four layers (0, 1, 2, 3), and layers 1 and 2 are merged into a single layer, the final image will contain three layers numbered 0, 1, 2 from bottom to top, where layer 0 is the same as before, layer 1 was previously layers 1 and 2, and layer 2 was previously layer 3.

Given the String[] macro, perform all the operations in the macro in order and return the final state of the image layers as a String[]. The String[] should contain exactly the same number of elements as there are layers in the final image, and each element i should correspond to the ith layer. Each element of the String[] should be a single space delimited list of the filenames contained in that layer. The filenames should be sorted in alphabetical order within each layer.
Definition
????
Class:
ImageLayers
Method:
contents
Parameters:
String[]
Returns:
String[]
Method signature:
String[] contents(String[] macro)
(be sure your method is public)
????

Constraints
-
macro will contain between 1 and 50 elements, inclusive.
-
Each element of macro will be formatted as either "OPEN filename" or "MERGE layer1-layer2".
-
Each filename in macro will contain between 1 and 15 lowercase letters ('a'-'z'), inclusive.
-
Each layer1 and layer2 in macro will be integers between 0 and n-1, inclusive, with no leading zeros, where n is the number of layers that exist in the image immediately before the command is executed.
-
Within each element of macro that represents a merge command, layer1 will be less than layer2.
-
The first element of macro will be an OPEN command.
Examples
0)

????
{"OPEN background",
 "OPEN aone",
 "OPEN atwo",
 "OPEN foreground",
 "MERGE 0-2",
 "OPEN border"}
Returns: {"aone atwo background", "foreground", "border" }
After the first four commands in macro are executed, the layers are (from bottom to top):

0. background 1. aone 2. atwo 3. foreground

The merge command combines the bottom three layers into a single layer. There are now only two layers (from bottom to top):

0. background aone atwo 1. foreground

Finally, one last file is opened and placed in a new layer on top. The final return value contains the filenames within each layer sorted alphabetically:

0. aone atwo background 1. foreground 2. border
1)

????
{"OPEN sky",
 "OPEN clouds",
 "OPEN ground",
 "MERGE 0-1",
 "OPEN grass",
 "MERGE 0-2",
 "OPEN trees",
 "OPEN leaves",
 "OPEN birds",
 "MERGE 1-2",
 "MERGE 0-1"}
Returns: {"clouds grass ground leaves sky trees", "birds" }

2)

????
{"OPEN a", "OPEN b", "OPEN a", "OPEN a", "MERGE 0-3"}
Returns: {"a a a b" }

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:44 emu 阅读(1633) 评论(12)  编辑  收藏 所属分类: google编程大赛模拟题及入围赛真题

评论

# emu的答案 2005-08-23 11:45 emu
import java.util.*;
public class ImageLayers {
    public static void main(String[] args) {
        String[] macro = new String[] {"OPEN sky",
                         "OPEN clouds",
                         "OPEN ground",
                         "MERGE 0-1",
                         "OPEN grass",
                         "MERGE 0-2",
                         "OPEN trees",
                         "OPEN leaves",
                         "OPEN birds",
                         "MERGE 1-2",
                         "MERGE 0-1"}
;
        ImageLayers il = new ImageLayers();
        String[] contents = il.contents(macro);
        for (int i=0;i<contents.length;i++)
            System.out.println(contents[i]);
                        

    }

    public String[] contents(String[] macro){
        ArrayList layers = new ArrayList();
        for (int i=0;i<macro.length;i++){
            String command = macro[i];
            if (command.startsWith("OPEN")){
                ArrayList layer = new ArrayList();
                layer.add(command.split(" ")[1]);
                layers.add(layer);
            }
            else if (command.startsWith("MERGE")){
                String[] l = command.split(" ")[1].split("-");
                int layer1 = Integer.parseInt(l[0],10);
                int layer2 = Integer.parseInt(l[1],10);
                ArrayList tmpLayers = (ArrayList)layers.get(layer1);                
                for (int j=layer2;j>layer1;j--)
                    tmpLayers.addAll((ArrayList)layers.remove(j));
            }
        }
        String[] result = new String[layers.size()];
        for (int i=0;i<result.length;i++){
            Object[] stAr = ((ArrayList)layers.get(i)).toArray();
            Arrays.sort(stAr);
            String s =  Arrays.toString(stAr).replace(',',' ');
            result[i] = s.substring(1,s.length()-1);
        }

        return result;
    }

}
  回复  更多评论
  

# re: ImageLayers（入围赛750分真题） 2005-08-25 11:01 emu
遗憾的很，我这个答案没有通过google的系统测试。  回复  更多评论
  

# re: ImageLayers（入围赛750分真题） 2005-12-09 09:55 chenrenbo
你好像没有对结果排序  回复  更多评论
  

# re: ImageLayers（入围赛750分真题） 2005-12-09 10:54 emu
Arrays.sort(stAr); 不是排序是什么？  回复  更多评论
  

# re: ImageLayers（入围赛750分真题） 2005-12-09 14:42 drekar
你的排序结果是用2个空格做间隔的("clouds<space><space>grass")，可能系统测试期望结果是1个空格("clouds<space>grass")。

把 String s = Arrays.toString(stAr).replace(",", "");
改成 String s = Arrays.toString(stAr).replace(",", "");
应该就好了。

下面是我的解法:

import java.util.ArrayList;
import java.util.Arrays;

public class ImageLayers {

　ArrayList canvas = new ArrayList();
　
　public String[] contents(String[] macro) {
　　if (null == macro)
　　　return new String[0];

　　for (int i=0; i<macro.length; i++) {
　　　String[] temp = macro[i].split(" ");
　　　if (temp[0].equalsIgnoreCase("OPEN"))
　　　　open(temp[1]);
　　　else
　　　　merge(temp[1]);
　　}
　　
　　String [] result = new String[canvas.size()];
　　for (int i=0; i<canvas.size(); i++)
　　　result[i] = (String)canvas.get(i);
　　return result;
　}
　
　public void open(String filename) {
　　canvas.add(filename);
　}
　
　public void merge(String layers) {
　　if (null == layers)
　　　return;
　　
　　String[] temp = layers.split("-");
　　int baseLayer = Integer.parseInt(temp[0]);
　　int lastLayer = Integer.parseInt(temp[1]);
　　if (baseLayer >= lastLayer || lastLayer >= canvas.size())
　　　return;
　　
　　String newLayerName = (String)canvas.get(baseLayer);
　　canvas.remove(baseLayer);
　　for (int i=baseLayer+1; i<= lastLayer; i++) {
　　　newLayerName += " " + canvas.get(baseLayer);
　　　canvas.remove(baseLayer);
　　}
　　temp = newLayerName.split(" ");
　　Arrays.sort(temp);
　　newLayerName = temp[0];
　　for (int i=1; i<temp.length; i++)
　　　newLayerName += " " + temp[i];

　　canvas.add(baseLayer, newLayerName);
　}
　
　/**
　 * @param args
　 */
　public static void main(String[] args) {
　　ImageLayers il = new ImageLayers();
　　String[] macro = { "OPEN sky", "OPEN clouds", "OPEN ground",
　　　　"MERGE 0-1", "OPEN grass", "MERGE 0-2", "OPEN trees",
　　　　"OPEN leaves", "OPEN birds", "MERGE 1-2", "MERGE 0-1" };
　　String[] result = il.contents(macro);
　　
　　for (int i=0; i<result.length; i++)
　　　System.out.println(result[i]);
　}
}

每次merge都排序，还是没有你的代码优化。  回复  更多评论
  

# 上个贴子有错 2005-12-09 14:44 drekar
第3－4行应该是『

把 String s = Arrays.toString(stAr).replace(',', ' ');
改成 String s = Arrays.toString(stAr).replace(",", "");


』, :)  回复  更多评论
  

# re: ImageLayers（入围赛750分真题） 2005-12-09 14:50 emu
这道题当时没有得分，恐怕不只是没有排序，还有这个空格的问题。  回复  更多评论
  

# re: ImageLayers（入围赛750分真题） 2005-12-11 11:51 john_wang71
试试看这个，完全用java.util.*中的类实现：
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Vector;

public class ImageLayers
{
public String[] contents(String[] macro)
{
String[] s = new String[] {};
try
{
Vector v = new Vector();
for (int i = 0; i < macro.length; i++)
{
String m = macro[i];
switch (m.charAt(0))
{
case 'O':
List c = new ArrayList();
c.add(m.substring(5));
v.add(c);
break;
case 'M':
int pos = m.indexOf('-');
int l1 = Integer.parseInt(m.substring(6, pos));
List c1 = (List) v.elementAt(l1);
int l2 = Integer.parseInt(m.substring(pos + 1));
for (int l3 = l2; l3 > l1; l3--)
{
List c3 = (List) v.elementAt(l3);
for (Iterator iter3 = c3.iterator(); iter3.hasNext();)
c1.add(iter3.next());
v.remove(l3);
}
}
}
s = new String[v.size()];
int i = 0;
for (Iterator iter = v.listIterator(); iter.hasNext();)
{
List c = (List) iter.next();
Collections.sort(c);
StringBuffer sb = new StringBuffer();
boolean first = true;
for (Iterator iter1 = c.iterator(); iter1.hasNext();)
{
if (first)
first = false;
else
sb.append(' ');
sb.append(iter1.next());
}
s[i++] = sb.toString();
}
}
catch (Exception e)
{
}
return s;
}
}
  回复  更多评论
  

# re: ImageLayers（入围赛750分真题） 2005-12-11 17:55 小飞侠
public class test {
public static String[] content(String[] macro) {
String[] mystr;
int cur, i,j, n, begin, end;
n = macro.length;
cur = 0;
mystr = new String[n];
//第一步操作,获取merge的String数组
for (i = 0; i < n; i++) {
if (macro[i].startsWith("OPEN")) {
mystr[cur] = macro[i].substring(5);
}

if (macro[i].startsWith("MERGE")) {
begin = Integer.parseInt(macro[i].substring(6, macro[i].indexOf("-")));
end = Integer.parseInt(macro[i].substring(macro[i].indexOf("-")+1));

//实现合并操作
cur = begin;
for (j = begin + 1; j <= end; j++) {
mystr[cur] = mystr[cur].concat(" ").concat(mystr[j]);
mystr[j] = null;
}
}
cur++;
}

for (i = 0; i < n; i++) {
System.out.println(mystr[i]);
}

//下面将原始的合并后的字符串数组,排序: 排序后,返回真正的数组
mystr = sorts(mystr);

System.out.println("sort ===");
for (i = 0; i < mystr.length; i++) {
System.out.println(mystr[i]);
}

return mystr;
}

public static String[] sorts(String[] mystr) {
String[] ret;
int i, j, n, cnt, cur=0;

n = mystr.length;
cnt = 0;

//获取实际的数组单元
for(i = 0, n = mystr.length; i < n; i++) {
if (mystr[i] != null)
cnt++;

}

ret = new String[cnt];

for (i = 0; i < n; i++) {
//对单元进行排序
if (mystr[i] != null) {
ret[cur++] = sort(mystr[i]);
}

}


System.out.println(cnt);
return ret;
}

//单元排序, 最简单的冒泡排序
public static String sort(String str) {
String[] a;
int i, j,n, flag;
String temp;

if (str.indexOf(" ") < 0) {
return str;
}

//开始排序
a = str.split(" ");
n = a.length;
for (i = 1; i < n; i++) {
flag = 0;
for (j = 0; j < (n - i) ; j++) {
if (a[j].compareTo(a[j+1]) > 0) {
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
flag = 1;
}
}

if (flag == 0) {
break;
}
}

//merge
str = a[0];
for (i = 1; i < n; i++) {
str = str.concat(" ").concat(a[i]);
}

return str;
}

public static void main(String args[]) {
String[] macro = {"OPEN sky",
"OPEN clouds",
"OPEN ground",
"MERGE 0-1",
"OPEN grass",
"MERGE 0-2",
"OPEN trees",
"OPEN leaves",
"OPEN birds",
"MERGE 1-2",
"MERGE 0-1"};

content(macro);

}
}  回复  更多评论
  

# re: ImageLayers（入围赛750分真题） 2005-12-12 09:12 emu
不赞成自己实现排序  回复  更多评论
  

# re: ImageLayers（入围赛750分真题） 2005-12-12 11:49 小飞侠
哈,是的:)

把自己的排序,改成Arrays.sort(split) :)

嘻嘻,今天要比赛了,祝福各位,祝福emu, 也祝福我,小飞侠:)嘻嘻  回复  更多评论
  

# re: ImageLayers（入围赛750分真题） 2005-12-12 15:23 emu
750分题的时间复杂度降不下来，看来通不过资格赛了，可惜……  回复  更多评论
  


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