首页 > 专题系列 > Java解POJ > POJ 3516 Johnny Hates Math [解题报告] Java
2013
11-12

POJ 3516 Johnny Hates Math [解题报告] Java

Johnny Hates Math

问题描述 :

Johnny is on probation! He has failed so many math courses and the Department has forced him to register in a remedial math course. He must pass the course or he’d be expelled from the University. In an attempt to impress his professor, Johnny is typing all his assignments on the computer. The latest assignment is rather simple, Johnny was given a set of problems to solve. Each problem had a list of one or more numbers that Johnny was supposed to add. Johnny has worked all night on the assignment, neatly typing his solution to each problem using a word processor as seen here:

4+12+3=19

As usual, Johnny woke up late, he hardly had the time to print the assignment and rush to class. Only in the classroom did he discover that, due to a printer driver problem, non of the plus signs were printed. The above line was printed as:

4123=19

Write a program to figure out where the pluses are supposed to be. All what Johnny remembers is that all the numbers were positive; None of the numbers, other than possibly the sum, had more than 5 digits; And none of the numbers had a zero as the left-most digit.

输入:

Your program will be tested on one or more expressions. Each expression is specified on a single line. No line will be longer than 256 characters. The last line, which is not part of the test cases, will be 0=0.

输出:

For each expression in the input, your program must print a line of the form:

k. result

Where k is the expression number (starting at 1), and result is the expression with the necessary plus signs in place. There are no spaces in result. If there are more than one possible solution, print a solution that requires the least number of plus signs. Knowing how bad Johnny is in arithmetic, it is possible that there is no solution, in which case your program should print "IMPOSSIBLE" as the result.

样例输入:

4123=19
15442147612367219875=472
111=8
0=0

样例输出:

1. 4+12+3=19
2. 15+44+21+47+61+23+67+21+98+75=472
3. IMPOSSIBLE

解题代码:

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
class Queue{
	int pre;
	int cnt_posi;
	int cnt_num;
	int cnt_sum;
	void set(int pre_t,int cnt_num_t,int cnt_sum_t,int cnt_posi_t){
		this.pre = pre_t;
		this.cnt_num = cnt_num_t;
		this.cnt_sum = cnt_sum_t;
		this.cnt_posi = cnt_posi_t;
	}
}
class node{
	int who;
	int value;
}
public class Main {
	static final int N = 4000000+10,P=256;
	
	static int n,p;
	static Queue myque[] = new Queue[N];

	static HashMap map[] = new HashMap[P];
	static int ans[] = new int[P],num[][] = new int[P][6];
	
	static void start_que(){
		int i,j;
		for(i=0;i< N;++i)
			myque[i] = new Queue();
		for(i=0;i< P;++i)
			map[i] = new HashMap();
	}
	
public static void main(String []args) throws Exception{
		
  int i,j,cs=1;
  String str = new String();
  Scanner cin = new Scanner(System.in);
  //Scanner cin = new Scanner(new FileInputStream("input.txt"));
  start_que();
  while(cin.hasNext()){
	str = cin.next();
	if(str.equalsIgnoreCase("0=0"))
		break;
	for(i=0;i< str.length();++i){
		if(str.charAt(i)=='=')
			break;
	}
	n = i;
	p = Integer.valueOf(str.substring(i+1, str.length()));

	System.out.print(cs+". ");
	++cs;
	solve(str,cs);
   }
 }

 public static void init_num(String str){
  int i,j;
  for(i=0;i< n;++i){
	num[i][0] = 0;
	for(j=1;j< 6 && i+j<=n;++j){
		num[i][j] = num[i][j-1]*10+str.charAt(i+j-1)-'0';
		//System.out.println(num[i][j]);
	}
   }
   for(i=0;i<=n;++i)
	map[i].clear();
  
   }


  static void get_ans(int cnt){
	String str="";
	int i,j,top=0;
	while(cnt>0){
		ans[top++] = myque[cnt].cnt_num;
		cnt = myque[cnt].pre;
	}
	str += String.valueOf(ans[top-1]);
	for(i=top-2;i>=0;--i){
		str+="+";
		str+=String.valueOf(ans[i]);
	}
	str+="="+String.valueOf(p);
	System.out.println(str);
  }

  public static void solve(String str,int cs){
   init_num(str);

   int i,j,k,left=0,right=0;
		
   myque[right].set(-1, 0, 0, 0);
   ++right;
		
   while(left< right){
    //System.out.println(left+" "+right);
    for(i=1;i< 6 && num[myque[left].cnt_posi][1]>0 && myque[left].cnt_posi+i<=n;++i){
	if(num[myque[left].cnt_posi][i]+myque[left].cnt_sum<=p){
					
	  myque[right].set(left, num[myque[left].cnt_posi][i], 
           num[myque[left].cnt_posi][i]+myque[left].cnt_sum, myque[left].cnt_posi+i);
	  if(myque[right].cnt_posi==n && myque[right].cnt_sum==p){
		get_ans(right);
		return ;
	    }
		if(!has_in_hash(myque[right].cnt_posi,myque[right].cnt_sum,cs))continue;
			++right;
		}
		
	}
	++left;
    }
    System.out.println("IMPOSSIBLE");
  }

  public static boolean has_in_hash(int posi,int sum,int cs){

		if(map[posi].containsKey(sum))
			return false;
		map[posi].put(sum, 1);
		return true;
	}
	
}

  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

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