emu in blogjava

  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  171 随笔 :: 103 文章 :: 1052 评论 :: 2 Trackbacks


Problem Statement
????
When a web client (like a browser) requests a particular web page, it typically replaces certain characters with escape sequences. For instance, spaces are replaced with "%20". Your task is to reverse this, replacing every escape sequence in the input with the character it represents. Each escape sequence is formatted as "%XX" where XX is the ASCII value of the escaped character in hexadecimal.
Definition
????
Class:
URLParser
Method:
parse
Parameters:
String
Returns:
String
Method signature:
String parse(String url)
(be sure your method is public)
????

Constraints
-
url will contain between 1 and 50 characters, inclusive.
-
Each '%' in the input will be followed by a hexadecimal value between 20 (hex) and 7E (letters will be uppercase).
-
Each character in the input will have ASCII value between 32 and 126, inclusive.
Examples
0)

????
"http://www.%20%40%20%40%20.com/%25"
Returns: "http://www. @ @ .com/%"
"%20" is the escape sequence for ' ', while "%40" stands for '@' and "%25" stands for '%'.
1)

????
"%20%21%22%23%24%25%26%27%28"
Returns: " !\"#$%&'("

2)

????
"%48%65%6C%6C%6F%20%57%6F%72%6C%64%21"
Returns: "Hello World!"

3)

????
"%2525"
Returns: "%25"

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

评论

# emu的解法 2005-08-23 16:51 emu
这个题基本上就是我以前写的 java版本的escape和unescape函数 的简化版了。
public class URLParser {
    public static void main(String[] args)
    {
        URLParser u = new URLParser();
            System.out.println(u.parse("%48%65%6C%6C%6F%20%57%6F%72%6C%64%21"));
    }
    public String parse(String url){
        StringBuffer tmp = new StringBuffer();
        tmp.ensureCapacity(url.length());
        int lastPos = 0, pos = 0;
        char ch;
        while (lastPos < url.length()) {
            pos = url.indexOf("%", lastPos);
            if (pos == lastPos) {
    ch = (char) Integer.parseInt(url.substring(pos + 1, pos + 3),16);
    tmp.append(ch);
    lastPos = pos + 3;
            } else {
                if (pos == -1) {
                    tmp.append(url.substring(lastPos));
                    lastPos = url.length();
                } else {
                    tmp.append(url.substring(lastPos, pos));
                    lastPos = pos;
                }
            }
        }
        return tmp.toString();
    }
}
  回复  更多评论
  

# re: URLParser(入围赛250分真题) 2005-08-23 22:35 coordinator
其实你应该向google提一份简历的
他们不来这边办比赛真是失误  回复  更多评论
  

# re: URLParser(入围赛250分真题) 2005-08-25 09:18 emu
google的比赛谁都可以参加啊,为什么一定要来中国办呢?考场里面也见到不少中国人。  回复  更多评论
  

# re: URLParser(入围赛250分真题) 2005-12-09 16:16 drekar
这几个测试样本会出错:

"--%--%48%65%6C"
"%4X%65%6C"


我还是用正则表达式做的。

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class URLParser {

 Public String parse(String url) {
  if (null == url)
   return "";

  Pattern p = Pattern.compile("%[0-9A-Fa-f]{2}");
  Matcher m = p.matcher(url);
  boolean found = m.find();
  if (found) {
   StringBuffer sb = new StringBuffer();
     do {
      String temp = m.group(0).substring(1);
      char a = (char)Integer.parseInt(temp, 16);
       m.appendReplacement(sb, ""+a);
       found = m.find();
     } while (found);
     m.appendTail(sb);
     return sb.toString();
  } else
   return url;
 }

 public static void main(String[] args) {
  String url = "%48%65%6C%6C%6F%20%57%6F%72%6C%64%21";
  URLParser up = new URLParser();
  System.out.println(up.parse(url));
 }
}
  回复  更多评论
  

# re: URLParser(入围赛250分真题) 2005-12-09 16:34 emu
>这几个测试样本会出错:
>"--%--%48%65%6C"
>"%4X%65%6C"

这两个是样本本身的错误。 escape后的数据是绝对不会出现 “%--” 和“%4X”这样的字符串的。因为“%”作为转义符,它不能用来表示“%”自己。你的parse结果吧它当成自己,其实也只是掩盖了问题而已。

你的代码里面  Public String parse(String url) { 第一个字母P怎么大写了?

为什么你只留名字不留联系方式啊,搞的好像地下党单线联系一样。  回复  更多评论
  

# re: URLParser(入围赛250分真题) 2005-12-09 17:13 drekar
哦。
我看题目给的样本也不全是URL,就自己编了几个,嘿嘿。。。

那个大写的P是我copy进来的时候不小心敲掉了,手工补了一个,也没管大小写,看来是自己依赖机器校验惯了,不好意思。

如果你要我的联系方式,那我的email是liouxiao_AT_gmail_DOT_com
不过我觉得这里就是一个很好的交流平台啊。  回复  更多评论
  

# re: URLParser(入围赛250分真题) 2005-12-09 18:31 emu
试试看你的程序比我的慢几倍?

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class URLParser {

  public String drekar(String url) {
    if (null == url)
      return "";

    Pattern p = Pattern.compile("%[0-9A-Fa-f]{2}");
    Matcher m = p.matcher(url);
    boolean found = m.find();
    if (found) {
      StringBuffer sb = new StringBuffer();
          do {
            String temp = m.group(0).substring(1);
            char a = (char)Integer.parseInt(temp, 16);
              m.appendReplacement(sb, ""+a);
              found = m.find();
          } while (found);
          m.appendTail(sb);
          return sb.toString();
    } else
      return url;
  }
    public String emu(String url){
        StringBuffer tmp = new StringBuffer();
        tmp.ensureCapacity(url.length());
        int lastPos = 0, pos = 0;
        char ch;
        while (lastPos < url.length()) {
            pos = url.indexOf("%", lastPos);
            if (pos == lastPos) {
    ch = (char) Integer.parseInt(url.substring(pos + 1, pos + 3),16);
    tmp.append(ch);
    lastPos = pos + 3;
            } else {
                if (pos == -1) {
                    tmp.append(url.substring(lastPos));
                    lastPos = url.length();
                } else {
                    tmp.append(url.substring(lastPos, pos));
                    lastPos = pos;
                }
            }
        }
        return tmp.toString();
    }

  public static void main(String[] args) {
    String url = "a%20b%20c%20d%20e%20f%20g%20h%20i%20j%20k%20l%20m%20n%20o%20p%20q%20r%20s%20t%20u%20v%20w%20x%20y%20z%20A%20B%20C%20D%20E%20F%20G%20H%20I%20J%20K%20L%20M%20N%20O%20P%20Q%20R%20S%20T%20U%20V%20W%20X%20Y%20Z%20" ;
    URLParser up = new URLParser();
    long t = System.currentTimeMillis();
    for(int i=0;i<1000;i++)
    up.drekar(url);
    System.out.println("drekar time used "+(System.currentTimeMillis()-t));
    t = System.currentTimeMillis();
    for(int i=0;i<1000;i++)
    up.emu(url);
    System.out.println("emu time used "+(System.currentTimeMillis()-t));
  }
}

正则如果不能直接进行全局replace的话,还没有自己实现替换来的快。  回复  更多评论
  

# re: URLParser(入围赛250分真题) 2005-12-09 23:26 drekar
这里的代码就是照着replaceAll改的,事实上就算用replaceAll也不会快多少,这主要是前面用到的正则表达式判断花的时间长。
如果样本不会出现我所举的例子,那确实没必要用正则表达式;但是如果转换的规则再复杂一些,也许实现上可以更灵活呢。  回复  更多评论
  

# re: URLParser(入围赛250分真题) 2005-12-09 23:29 drekar
这里的代码就是照着replaceAll改的,事实上就算用replaceAll也不会快多少,这主要是前面用到的正则表达式判断花的时间长。
如果样本不会出现我所举的例子,那确实没必要用正则表达式;但是如果转换的规则再复杂一些,也许实现上可以更灵活呢。

(刚发现我用firefox1.5无法提交留言,是blogjava的bug吗?)  回复  更多评论
  

# re: URLParser(入围赛250分真题) 2005-12-10 00:52 emu
有一个现成的更复杂一点点的转换规则啊,试试javascript里面的escape/unescape:

%u5165%u56F4%u8D5B250%u5206%u771F%u9898 《==》 入围赛250分真题

我的解答前面贴过了 java版本的escape和unescape函数  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: