首页 > 专题系列 > Java解POJ > POJ 3340 Barbara Bennett’s Wild Numbers [解题报告] Java
2013
11-12

POJ 3340 Barbara Bennett’s Wild Numbers [解题报告] Java

Barbara Bennett’s Wild Numbers

问题描述 :

A wild number is a string containing digits and question marks (like 36?1?8). A number X matches a wild number W if they have the same length, and every non-question mark character in X is equal to the character in the same position in W (it means that you can replace a question mark with any digit). For example, 365198 matches the wild number 36?1?8, but 360199, 361028, or 36128 does not. Write a program that reads a wild number W and a number X from input, both of length n, and determines the number of n-digit numbers that match W and are greater than X.

输入:

There are multiple test cases in the input. Each test case consists of two lines of the same length. The first line contains a wild number W, and the second line contains an integer number X. The length of input lines is between 1 and 10 characters. The last line of input contains a single character #.

输出:

For each test case, write a single line containing the number of n-digit numbers matching W and greater than X (n is the length of W and X).

样例输入:

36?1?8
236428
8?3
910
?
5
#

样例输出:

100
0
4

解题代码:

//* @author 洪晓鹏<[email protected]>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

/**
 * @param args
 * @throws IOException
 */
public static int count(String a, String b) {
 int len = a.length();
 int result = 1;
 for (int i = 0; i < len; i++) {
	if (Character.isDigit(a.charAt(i))) {
		if (a.charAt(i) > b.charAt(i)) {
			for (int j = i + 1; j < len; j++) {
				if (a.charAt(j) == '?')
					result *= 10;
			}
			return result;
		}
		if (a.charAt(i) < b.charAt(i))
			return 0;
	} else {
		if (len == i + 1)
			return '9' - b.charAt(i);
		else {
			String new_a = a.substring(i + 1);
			String new_b = b.substring(i + 1);
			for (int j = i + 1; j < len; j++) {
				if (a.charAt(j) == '?')
					result *= 10;
			}
			return ('9' - b.charAt(i)) * result + count(new_a, new_b);
		}
	}
  }
  return 0;
}

 public static void main(String[] args) throws IOException {
	// TODO Auto-generated method stub
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	while (true) {
		String wild = br.readLine();
		if (wild.equals("#"))
			break;
		String num = br.readLine();
		System.out.println(count(wild, num));
	}
 }

}

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

  2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  4. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }