<rt id="bn8ez"></rt>
<label id="bn8ez"></label>

  • <span id="bn8ez"></span>

    <label id="bn8ez"><meter id="bn8ez"></meter></label>

    emu in blogjava

      BlogJava :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理 ::
      171 隨筆 :: 103 文章 :: 1052 評論 :: 2 Trackbacks



    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 閱讀(1677) 評論(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;
        }

    }
      回復(fù)  更多評論
      

    # re: ImageLayers(入圍賽750分真題) 2005-08-25 11:01 emu
    遺憾的很,我這個(gè)答案沒有通過google的系統(tǒng)測試。  回復(fù)  更多評論
      

    # re: ImageLayers(入圍賽750分真題) 2005-12-09 09:55 chenrenbo
    你好像沒有對結(jié)果排序  回復(fù)  更多評論
      

    # re: ImageLayers(入圍賽750分真題) 2005-12-09 10:54 emu
    Arrays.sort(stAr); 不是排序是什么?  回復(fù)  更多評論
      

    # re: ImageLayers(入圍賽750分真題) 2005-12-09 14:42 drekar
    你的排序結(jié)果是用2個(gè)空格做間隔的("clouds<space><space>grass"),可能系統(tǒng)測試期望結(jié)果是1個(gè)空格("clouds<space>grass")。

    把 String s = Arrays.toString(stAr).replace(",", "");
    改成 String s = Arrays.toString(stAr).replace(",", "");
    應(yīng)該就好了。

    下面是我的解法:

    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都排序,還是沒有你的代碼優(yōu)化。  回復(fù)  更多評論
      

    # 上個(gè)貼子有錯(cuò) 2005-12-09 14:44 drekar
    第3-4行應(yīng)該是『

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


    』, :)  回復(fù)  更多評論
      

    # re: ImageLayers(入圍賽750分真題) 2005-12-09 14:50 emu
    這道題當(dāng)時(shí)沒有得分,恐怕不只是沒有排序,還有這個(gè)空格的問題。  回復(fù)  更多評論
      

    # re: ImageLayers(入圍賽750分真題) 2005-12-11 11:51 john_wang71
    試試看這個(gè),完全用java.util.*中的類實(shí)現(xiàn):
    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;
    }
    }
      回復(fù)  更多評論
      

    # 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數(shù)組
    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));

    //實(shí)現(xiàn)合并操作
    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]);
    }

    //下面將原始的合并后的字符串?dāng)?shù)組,排序: 排序后,返回真正的數(shù)組
    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;

    //獲取實(shí)際的數(shù)組單元
    for(i = 0, n = mystr.length; i < n; i++) {
    if (mystr[i] != null)
    cnt++;

    }

    ret = new String[cnt];

    for (i = 0; i < n; i++) {
    //對單元進(jìn)行排序
    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);

    }
    }  回復(fù)  更多評論
      

    # re: ImageLayers(入圍賽750分真題) 2005-12-12 09:12 emu
    不贊成自己實(shí)現(xiàn)排序  回復(fù)  更多評論
      

    # re: ImageLayers(入圍賽750分真題) 2005-12-12 11:49 小飛俠
    哈,是的:)

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

    嘻嘻,今天要比賽了,祝福各位,祝福emu, 也祝福我,小飛俠:)嘻嘻  回復(fù)  更多評論
      

    # re: ImageLayers(入圍賽750分真題) 2005-12-12 15:23 emu
    750分題的時(shí)間復(fù)雜度降不下來,看來通不過資格賽了,可惜……  回復(fù)  更多評論
      

    主站蜘蛛池模板: 亚洲AV无码国产丝袜在线观看| 亚洲视频手机在线| 亚洲Aⅴ在线无码播放毛片一线天| 99在线观看免费视频| 91嫩草私人成人亚洲影院| 91精品国产免费久久国语蜜臀| 久久精品国产亚洲AV麻豆不卡 | 国产嫩草影院精品免费网址| 亚洲人成人伊人成综合网无码| 色妞WWW精品免费视频| 亚洲熟女www一区二区三区| 日本成人免费在线| 免费毛片毛片网址| 亚洲人成网站在线观看播放| 在线观看黄片免费入口不卡| 久久久久久久综合日本亚洲| 久9热免费精品视频在线观看| 亚洲视频小说图片| 女人张开腿等男人桶免费视频 | 黄视频在线观看免费| 亚洲爆乳无码专区| 五月婷婷综合免费| 国产亚洲蜜芽精品久久| 国产亚洲成人在线播放va| 人妻无码一区二区三区免费| 亚洲六月丁香婷婷综合| 亚洲av午夜精品一区二区三区| 免费网站观看WWW在线观看| 亚洲大香伊人蕉在人依线| 国产精品免费视频一区| 国产黄在线观看免费观看不卡 | 亚洲精品高清视频| 十八禁的黄污污免费网站| 亚洲中文字幕无码不卡电影 | 国产精品亚洲精品观看不卡| 免费大片黄手机在线观看| 暖暖免费日本在线中文| 亚洲av无码专区首页| 久久精品国产精品亚洲艾| 午夜免费福利在线观看| 中文字幕成人免费高清在线视频|