首页 > 专题系列 > Java解POJ > POJ 1782 Run Length Encoding [解题报告] Java
2013
11-10

POJ 1782 Run Length Encoding [解题报告] Java

Run Length Encoding

问题描述 :

Your task is to write a program that performs a simple form of run-length encoding, as described by the rules below.

Any sequence of between 2 to 9 identical characters is encoded by two characters. The first character is the length of the sequence, represented by one of the characters 2 through 9. The second character is the value of the repeated character. A sequence of more than 9 identical characters is dealt with by first encoding 9 characters, then the remaining ones.

Any sequence of characters that does not contain consecutive repetitions of any characters is represented by a 1 character followed by the sequence of characters, terminated with another 1. If a 1 appears as part of the sequence, it is escaped with a 1, thus two 1 characters are output.

输入:

The input consists of letters (both upper- and lower-case), digits, spaces, and punctuation. Every line is terminated with a newline character and no other characters appear in the input.

输出:

Each line in the input is encoded separately as described above. The newline at the end of each line is not encoded, but is passed directly to the output.

样例输入:

AAAAAABCCCC
12344

样例输出:

6A1B14C
11123124

解题代码:

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;

public class Main {

	/**
	 * @param args
	 */
public static void main(String[] args) throws Exception{
// TODO Auto-generated method stub
		
int i,j,n,cotinue;
boolean is_first;
String str;

Scanner cin = new Scanner(System.in);
while(cin.hasNext()){
	str = cin.nextLine();
	n = str.length();
	
	cotinue = 1;
	is_first = false;
	
	for(i=0;i< n;)
	{
		if(i+1< n&&str.charAt(i)==str.charAt(i+1))
		{
			while(i+1< n&&str.charAt(i)==str.charAt(i+1)&&cotinue<9)
			{
				cotinue++;
				i++;
			}
			System.out.print(cotinue);
			System.out.print(str.charAt(i));
			i++;
			is_first = false;
			cotinue = 1;
		}
		else{
			cotinue = 1;
			if(!is_first)
				System.out.print("1");
			if(str.charAt(i)=='1')
				System.out.print("11");
			else
				System.out.print(str.charAt(i));
			if(i==n-1||(i< n-2&&str.charAt(i+1)==str.charAt(i+2)))
					System.out.print("1");
			i++;
			is_first = true;
		}
	}
	System.out.println("");
 }
}

}

  1. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  2. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.

  3. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1

  4. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。