首页 > 数据结构 > Hash表 > POJ 2538 WERTYU [解题报告] Java
2013
11-11

POJ 2538 WERTYU [解题报告] Java

WERTYU

问题描述 :



A common typing error is to place the hands on the keyboard one row to the right of the correct position. So “Q” is typed as “W” and “J” is typed as “K” and so on. You are to decode a message typed in this manner.

输入:

Input consists of several lines of text. Each line may contain digits, spaces, upper case letters (except Q, A, Z), or punctuation shown above [except back-quote (`)]. Keys labelled with words [Tab, BackSp, Control, etc.] are not represented in the input.

输出:

You are to replace each letter or punctuation symbol by the one immediately to its left on the QWERTY keyboard shown above. Spaces in the input should be echoed in the output.

样例输入:

O S, GOMR YPFSU/

样例输出:

I AM FINE TODAY.

解题代码:

//* @author  [email protected]
import java.util.Hashtable;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        String[] s={"`1234567890-=","QWERTYUIOP[]","ASDFGHJKL;'","ZXCVBNM,./"};
        Scanner scan=new Scanner(System.in);
        s[1]+=(char)(92);
        String cad="",out="";
        Hashtable< String,String> table=new Hashtable< String,String>();
        for(int i=0;i< 4;i++){
            for(int j=1;j< s[i].length();j++){
                table.put(s[i].charAt(j)+"", s[i].charAt(j-1)+"");
            }
        }
        table.put(" ", " ");
        while(scan.hasNext()){
            cad=scan.nextLine();
            out="";
            for(int i=0;i< cad.length();i++){
                out+=table.get(cad.charAt(i)+"");
            }
            System.out.println(out);
        }
    }
}

  1. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  2. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  3. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }

  4. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  5. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的