首页 > 数据结构 > Hash表 > POJ 1051 P,MTHBGWB [解题报告] Java
2013
11-09

POJ 1051 P,MTHBGWB [解题报告] Java

P,MTHBGWB

问题描述 :

Morse code represents characters as variable length sequences of dots and dashes. In practice, characters in a message are delimited by short pauses. The following table shows the Morse code sequences:

A .- H …. O V …-
B -… I .. P .–. W .–
C -.-. J .— Q –.- X -..-
D -.. K -.- R .-. Y -.–
E . L .-.. S Z –..
F ..-. M T -    
G –. N -. U ..-    

Note that four dot-dash combinations are unassigned. For the purposes of this problem we will assign them as follows (these are not the assignments for actual Morse code):

underscore ..– period —.
comma .-.- question mark —-

Thus, the message “ACM_GREATER_NY_REGION” is encoded as:

.- -.-. — ..– –. .-. . .- – . .-. ..– -. -.– ..– .-. . –. .. — -.

M.E. Ohaver proposed an encryption scheme based on mutilating Morse code. Her scheme replaces the pauses between letters, necessary because Morse is a variable-length encoding that is not prefix-free, with a string that identifies the number of dots and dashes in each. For example, consider the message “.–.-.–”. Without knowing where the pauses should be, this could be “ACM”, “ANK”, or several other possibilities. If we add length information, however, “.–.-.–242″, then the code is unabiguous.

Ohaver’s scheme has three steps, the same for encryption and decryption:

1. Convert the text to Morse code without pauses but with a string of numbers to indicate code lengths

2. Reverse the string of numbers

3. Convert the dots and dashes back into to text using the reversed string of numbers as code lengths

As an example, consider the encrypted message “AKADTOF_IBOETATUK_IJN”. Converting to Morse code with a length string yields “.–.-.–..—-..-…–..-…—.-.–..–.-..–…—-.232313442431121334242″. Reversing the numbers and decoding yields the original message “ACM_GREATER_NY_REGION”.

输入:

This problem requires that you implement Ohaver’s encoding algorithm. The input will consist of several messages encoded with Ohaver’s algorithm. The first line of the input is an integer n that specifies the number of test cases. The following n lines contain one message per line. Each message will use only the twenty-six capital letters, underscores, commas, periods, and question marks. Messages will not exceed 100 characters in length.

输出:

For each message in the input, output the line number starting in column one, a colon, a space, and then the decoded message. The output format must be adhered to precisely.

样例输入:

5
AKADTOF_IBOETATUK_IJN
PUEL
QEWOISE.EIVCAEFNRXTBELYTGD.
?EJHUT.TSMYGW?EJHOT
DSU.XFNCJEVE.OE_UJDXNO_YHU?VIDWDHPDJIKXZT?E

样例输出:

1: ACM_GREATER_NY_REGION
2: PERL
3: QUOTH_THE_RAVEN,_NEVERMORE.
4: TO_BE_OR_NOT_TO_BE?
5: THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG

解题代码:

//* @author 
import java.io.*; 
import java.util.*; 

public class Main 
{ 
    static HashMap< String,String> codeMap = new HashMap< String,String>(); 
    static HashMap< String,String> ref = new HashMap< String,String>(); 

    public static void main(String[] args) throws Exception 
    { 
        initMap(); 
        readFile(); 
    } 
    static void readFile() throws Exception 
    { 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
        int n = Integer.valueOf(br.readLine()); 
        int count = 0; 
        while(count< n) 
        { 
            process(br.readLine()); 
            count++; 
        } 
    } 
    static void initMap() 
    { 
        codeMap.put("A",".-"); 
        codeMap.put("B","-..."); 
        codeMap.put("C","-.-."); 
        codeMap.put("D","-.."); 
        codeMap.put("E","."); 
        codeMap.put("F","..-."); 
        codeMap.put("G","--."); 
        codeMap.put("H","...."); 
        codeMap.put("I",".."); 
        codeMap.put("J",".---"); 
        codeMap.put("K","-.-"); 
        codeMap.put("L",".-.."); 
        codeMap.put("M","--"); 
        codeMap.put("N","-."); 
        codeMap.put("O","---"); 
        codeMap.put("P",".--."); 
        codeMap.put("Q","--.-"); 
        codeMap.put("R",".-."); 
        codeMap.put("S","..."); 
        codeMap.put("T","-"); 
        codeMap.put("U","..-"); 
        codeMap.put("V","...-"); 
        codeMap.put("W",".--"); 
        codeMap.put("X","-..-"); 
        codeMap.put("Y","-.--"); 
        codeMap.put("Z","--.."); 
        codeMap.put("_","..--"); 
        codeMap.put(".","---."); 
        codeMap.put(",",".-.-"); 
        codeMap.put("?","----"); 

        ref.put(".-","A"); 
        ref.put("-...","B"); 
        ref.put("-.-.","C"); 
        ref.put("-..","D"); 
        ref.put(".","E"); 
        ref.put("..-.","F"); 
        ref.put("--.","G"); 
        ref.put("....","H"); 
        ref.put("..","I"); 
        ref.put(".---","J"); 
        ref.put("-.-","K"); 
        ref.put(".-..","L"); 
        ref.put("--","M"); 
        ref.put("-.","N"); 
        ref.put("---","O"); 
        ref.put(".--.","P"); 
        ref.put("--.-","Q"); 
        ref.put(".-.","R"); 
        ref.put("...","S"); 
        ref.put("-","T"); 
        ref.put("..-","U"); 
        ref.put("...-","V"); 
        ref.put(".--","W"); 
        ref.put("-..-","X"); 
        ref.put("-.--","Y"); 
        ref.put("--..","Z"); 
        ref.put("..--","_"); 
        ref.put("---.","."); 
        ref.put(".-.-",","); 
        ref.put("----","?"); 
    } 
    static void process(String str) 
    { 
        StringBuffer strCode = new StringBuffer(str); 
        StringBuffer lengthCode = new StringBuffer(); 
        StringBuffer currentCode = new StringBuffer(); 
        int index = 0; 
        while(index< strCode.length()) 
        { 
            String code = codeMap.get(strCode.charAt(index++)+""); 
            currentCode.append(code); 
            lengthCode.append(code.length()); 
        } 
        index = lengthCode.length()-1; 
        int start = 0; 
        int end = 0; 
        StringBuffer result = new StringBuffer(); 
        while(index>=0) 
        { 
            end = Integer.valueOf(lengthCode.charAt(index--)+"")+start; 
            String ttt = currentCode.substring(start,end); 
            result.append(ref.get(ttt)); 
            start = end; 
        } 
        if(flag!=0) 
            System.out.println(); 
        flag++; 
        System.out.print(flag+": " + result.toString()); 
    } 
    static int flag = 0; 
}

  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

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

  4. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  5. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }