首页 > 专题系列 > Java解POJ > POJ 2136 Vertical Histogram [解题报告] Java
2013
11-10

POJ 2136 Vertical Histogram [解题报告] Java

Vertical Histogram

问题描述 :

Write a program to read four lines of upper case (i.e., all CAPITAL LETTERS) text input (no more than 72 characters per line) from the input file and print a vertical histogram that shows how many times each letter (but not blanks, digits, or punctuation) appears in the all-upper-case input. Format your output exactly as shown.

输入:

* Lines 1..4: Four lines of upper case text, no more than 72 characters per line.

输出:

* Lines 1..??: Several lines with asterisks and spaces followed by one line with the upper-case alphabet separated by spaces. Do not print unneeded blanks at the end of any line. Do not print any leading blank lines.

样例输入:

THE QUICK BROWN FOX JUMPED OVER THE LAZY DOG.
THIS IS AN EXAMPLE TO TEST FOR YOUR
HISTOGRAM PROGRAM.
HELLO!

样例输出:

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

解题代码:

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.Arrays;

 

public class Main {

    public static void main(String[] args) throws NumberFormatException,

           IOException {

       BufferedReader read = new BufferedReader(new InputStreamReader(

              System.in));

       int[] a = new int[26];

       int tt;

       for (int i = 0; i < 4; i++) {

           String str = read.readLine();

           for (int j = 0; j < str.length(); j++) {

              tt = str.charAt(j) - 'A';

              if (tt >= 0 && tt <= 25) {

                  a[tt]++;

              }

           }

       }

       int max = 0;

       for (int i = 0; i < 26; i++) {

           if (a[i] > max) {

              max = a[i];

           }

       }

       char[][] c = new char[max + 1][51];
       for (int i = 0; i < max + 1; i++) {
           Arrays.fill(c[i], ' ');
       }
       for (int i = 0; i < 26; i++) {
           int h = a[i];
           for (int j = 0; j < h; j++) {

              c[max - 1 - j][i * 2] = '*';

           }
       }
       for (int i = 0; i < 26; i++) {
           c[max][i * 2] = (char) ('A' + i);
       }

       for (int i = 0; i < max + 1; i++) {
           String str = String.valueOf(c[i]);
           while (str.endsWith(" ")) {
              str = str.substring(0, str.length() - 1);
           }
           System.out.println(str);
       }
    }
}

  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. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

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