首页 > 专题系列 > Java解POJ > POJ 1240 Pre-Post-erous! [解题报告] Java
2013
11-09

POJ 1240 Pre-Post-erous! [解题报告] Java

Pre-Post-erous!

问题描述 :

We are all familiar with pre-order, in-order and post-order traversals of binary trees. A common problem in data structure classes is to find the pre-order traversal of a binary tree when given the in-order and post-order traversals. Alternatively, you can find the post-order traversal when given the in-order and pre-order. However, in general you cannot determine the in-order traversal of a tree when given its pre-order and post-order traversals. Consider the four binary trees below:

a a a a
/ / \ \
b b b b
/ \ / \
c c c c

All of these trees have the same pre-order and post-order traversals. This phenomenon is not restricted to binary trees, but holds for general m-ary trees as well.

输入:

Input will consist of multiple problem instances. Each instance will consist of a line of the form

m s1 s2

indicating that the trees are m-ary trees, s1 is the pre-order traversal and s2 is the post-order traversal.All traversal strings will consist of lowercase alphabetic characters. For all input instances, 1 <= m <= 20 and the length of s1 and s2 will be between 1 and 26 inclusive. If the length of s1 is k (which is the same as the length of s2, of course), the first k letters of the alphabet will be used in the strings. An input line of 0 will terminate the input.

输出:

For each problem instance, you should output one line containing the number of possible trees which would result in the pre-order and post-order traversals for the instance. All output values will be within the range of a 32-bit signed integer. For each problem instance, you are guaranteed that there is at least one tree with the given pre-order and post-order traversals.

样例输入:

2 abc cba
2 abc bca
10 abc bca
13 abejkcfghid jkebfghicda
0

样例输出:

4
1
45
207352860

解题代码:

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

public class Main{
 static Scanner cin;
 public static void main(String args[]){
	cin = new Scanner(System.in);
	while(run()==true)
			;
 }

 static boolean run(){
   int n = cin.nextInt();
   if(n==0)
        return false;

   Tree tree = new Tree(n, cin.next(), cin.next());
   System.out.println(tree.compute());
   return true;
 }
}


class Tree{
  static String preMap, postMap;
  static int M;

  static int[][] C;

  int preStart, postStart, length;

  public Tree(int M, String preMap, String postMap){
	this.M = M;
	this.preMap = preMap;
	this.postMap = postMap;

	C = new int[100][100];
	initialC();
		
	preStart = 0;
	postStart  = 0;
	length   = preMap.length();
   }

  public Tree(int preStart, int postStart, int length){
	this.preStart = preStart;
	this.postStart  = postStart;
	this.length = length;
  }

 ArrayList< Tree> subTree(){
	ArrayList< Tree> nodes = new ArrayList< Tree>();

	int start = preStart+1;
	int pEnd = postStart-1;
	int pstart, subLength;

	while(start< (preStart+length)){
         pstart = pEnd+1;
	  pEnd  = postMap.indexOf(preMap.charAt(start));
		subLength = pEnd-pstart+1;

	  nodes.add(new Tree(start, pstart, subLength));

	  start = start+subLength;
	}

	return nodes;
   }

  int compute(){
	ArrayList< Tree> nodes = subTree();
	int count = C(M, nodes.size());
	for(Tree t:nodes)
         count *= t.compute();
	return count;
   }

  void initialC(){
	int i,j;
	for(i=0;i< 100;i++)
         for(j=0;j< 100;j++)
	    C[i][j] = -1;

	for(i=0;i< 100;i++){
	  C[1][i] = (i>1? 0:1);
	  C[i][0] = 1;
	}
   }

int C(int n, int m){
  if(C[n][m] == -1)
	return C(n-1, m)+C(n-1, m-1);
  else
	return C[n][m];
  }
}

  1. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

  2. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

  3. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  4. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  5. [email protected]