曾彪彪的个人博客 -- P1598 垂直柱状图解题优化

# P1598 垂直柱状图

## 题目描述

写一个程序从输入文件中去读取四行大写字母（全都是大写的，每行不超过 $100$ 个字符），然后用柱状图输出每个字符在输入文件中出现的次数。严格地按照输出样例来安排你的输出格式。

## 输入格式

四行字符，由大写字母组成，每行不超过 $100$ 个字符

## 输出格式

由若干行组成，前几行由空格和星号组成，最后一行则是由空格和字母组成的。在任何一行末尾不要打印不需要的多余空格。不要打印任何空行。

## 输入输出样例 #1

### 输入 #1

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

### 输出 #1

```
*
                            *
        *                   *
        *                   *     *   *
        *                   *     *   *
*       *     *             *     *   *
*       *     * *     * *   *     * * *
*       *   * * *     * *   * *   * * * *
*     * * * * * *     * * * * *   * * * *     * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
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
```

## 说明/提示

每行输出后面不允许出现多余的空格。

第一次解题思路如下：
``` c++
/**
start time: 8:45
End time:
Solution:
- use map to record word frequence.
- find out max value of frequence
- use two dimensional array to output the diagram with inverted order
-
first submit score:
cause:
test case:
-
THE QUICK BROWN FOX JUMPED OVER THE LAZY DOG.
THIS IS AN EXAMPLE TO TEST FOR YOUR
HISTOGRAM PROGRAM.
HELLO!

-
AAAA
BBB
CC
D
-
ABCDE
ABCDE
ABCDE
ABCDE
-
ABCDEFG
ABCDEFGH
ABCDEFGHI
ABCDEFGHIJ
-
AAA

BBB
-

BBB
**/

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n = 4;
    string str = "";
    while (n--)
    {
        string input;
        getline(cin, input);
        str.append(input);
    }
    unordered_map<char, int> freqMap;
    for (auto c : str)
    {
        if (c >= 'A' && c <= 'Z')
        {
            freqMap[c]++;
        }
    }
    int maxValue = 0;
    for (auto const &p : freqMap)
    {
        maxValue = max(maxValue, p.second);
    }
    vector<vector<char>> ans(maxValue + 1, vector<char>(26));
    for (int j = 0; j < 26; j++)
    {
        ans[maxValue][j] = (char)('A' + j);
    }
    for (int i = maxValue - 1; i >= 0; i--)
    {
        for (int j = 0; j < 26; j++)
        {
            int v = freqMap[ans[maxValue][j]];
            if (maxValue - i <= v)
            {
                ans[i][j] = '*';
            }
            else
            {
                ans[i][j] = ' ';
            }
        }
    }

for (int i = 0; i < ans.size(); i++)
    {
        for (int j = 0; j < ans[0].size(); j++)
        {
            cout << ans[i][j];
            if (j < (ans[0].size() - 1))
            {
                cout << " ";
            }
        }
        cout << endl;
    }
    return 0;
}

```

后面看别人代码，改用数组实现。
总结：对于统计次数，或者存储k,v结果，如果key是连续且有限的，如a,b,c...z，或者是1,2,3...100等，那么可以使用数组替换map，这样可以简化编程。如果key不连续，如a,c,d，并且具有不确定性，那么老老实实用map。
使用数组可以简化编程，如遍历，取值都可以简化。
更新后代码
``` c++
/**
start time: 8:45
End time:
Solution:
- use map to record word frequence.
- find out max value of frequence
- use two dimensional array to output the diagram with inverted order
-
first submit score:
cause:
test case:
-
THE QUICK BROWN FOX JUMPED OVER THE LAZY DOG.
THIS IS AN EXAMPLE TO TEST FOR YOUR
HISTOGRAM PROGRAM.
HELLO!

-
AAAA
BBB
CC
D
-
ABCDE
ABCDE
ABCDE
ABCDE
-
ABCDEFG
ABCDEFGH
ABCDEFGHI
ABCDEFGHIJ
-
AAA

BBB
-

BBB
**/

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n = 4;
    string str = "";
    while (n--)
    {
        string input;
        getline(cin, input);
        str.append(input);
    }
    vector<int> arr(26, 0);
    for (auto c : str)
    {
        if (c >= 'A' && c <= 'Z')
        {
            arr[c - 'A']++;
        }
    }
    int maxValue = 0;
    for (auto v : arr)
    {
        maxValue = max(maxValue, v);
    }
    vector<vector<char>> ans(maxValue + 1, vector<char>(26));
    for (int j = 0; j < 26; j++)
    {
        ans[maxValue][j] = (char)('A' + j);
    }
    for (int i = maxValue - 1; i >= 0; i--)
    {
        for (int j = 0; j < 26; j++)
        {
            if (maxValue - i <= arr[j])
            {
                ans[i][j] = '*';
            }
            else
            {
                ans[i][j] = ' ';
            }
        }
    }

```

P1598 垂直柱状图解题优化

评论(0)