算法题：统计字符串中每个字符的个数

发表于 | 更新于 | 阅读次数：

算法题：统计字符串中每个字符的个数。

前言

本题及其变体曾经作为迅雷和美团点评的面试算法题出现过。

题目

解答1[Java]：只统计大写字母

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 只统计小写字母的情况
 */
class Solution {
    public void calculateCharacterFrequency(char[] str) {
        int length = str.length;
        int[] frequency = new int[26];

        for (int i = 0; i < length; ++i) {
            if (str[i] >= 'A' && str[i] <= 'Z') {
                ++frequency[str[i] - 'A'];
            }
        }

        printResult(frequency);
    }

    public void printResult(int[] frequency) {
        int length = frequency.length;

        for (int i = 0; i < length; ++i) {
            System.out.printf("%c : %d\n", 'A' + i, frequency[i]);
        }
    }

    public static void main(String[] args) {
        String str = "asjdhiashfahsdkjfhaksjhvouahshagasfgvasbgdjkhajfgbasbvas";
        Solution s = new Solution();
        s.calculateCharacterFrequency(str.toCharArray());
    }
}

解答2[Java]：大写小写都统计，大小写统一视为大写

思路

只需要在解答1的基础上，进行两次判断即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 大写小写都统计，大小写统一视为大写
 */
class Solution {
    public void calculateCharacterFrequency(char[] str) {
        int length = str.length;
        int[] frequency = new int[26];

        for (int i = 0; i < length; ++i) {
            if (str[i] >= 'A' && str[i] <= 'Z') {
                ++frequency[str[i] - 'A'];
            } else if (str[i] >= 'a' && str[i]<='z'){
                ++frequency[str[i] - 'a'];
            }
        }

        printResult(frequency);
    }

    public void printResult(int[] frequency) {
        int length = frequency.length;

        for (int i = 0; i < length; ++i) {
            System.out.printf("%c : %d\n", 'A' + i, frequency[i]);
        }
    }

    public static void main(String[] args) {
        String str = "AsjdhiashfabBhsdkjfhaksjhvouahshagasfgvasbgdjkhajfgbasbvas";
        Solution s = new Solution();
        s.calculateCharacterFrequency(str.toCharArray());
    }
}

解答3[Java]：大写小写都统计，大小写分开统计

思路

创建一个大小为 52 的整形数组，0 ~ 25 保存 A ~ Z 出现的次数，26 ~ 51 保存 a ~ z 出现的次数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 大写小写都统计，大小写分开统计
 */
class Solution {
    public void calculateCharacterFrequency(char[] str) {
        int length = str.length;
        int[] frequency = new int[52];

        for (int i = 0; i < length; ++i) {
            if (str[i] >= 'A' && str[i] <= 'Z') {
                ++frequency[str[i] - 'A'];
            } else if (str[i] >= 'a' && str[i] <= 'z') {
                ++frequency[str[i] - 'a' + 26];
            }
        }

        printResult(frequency);
    }

    public void printResult(int[] frequency) {
        int overallIndex = 0;
        for (int i = 0; overallIndex < 26; ++overallIndex, ++i) {
            System.out.printf("%c : %d\n", 'A' + i, frequency[overallIndex]);
        }

        for (int i = 0; overallIndex < 52; ++overallIndex, ++i) {
            System.out.printf("%c : %d\n", 'a' + i, frequency[overallIndex]);
        }
    }

    public static void main(String[] args) {
        String str = "AsjdhiashfabBhsdkjfhaksjhvouahshagasfgvasbgdjkhajfgbasbvas";
        Solution s = new Solution();
        s.calculateCharacterFrequency(str.toCharArray());
    }
}

解答4[Java]：使用 HashMap 实现

使用 HashMap 实现解答1的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.HashMap;

class Solution {
    public void calculateCharacterFrequency(char[] str) {
        int length = str.length;
        HashMap<Character, Integer> frequency = new HashMap<>();

        for (char c : str) {
            if (c >= 'A' && c <= 'Z') {
                int count = frequency.getOrDefault(c, 0);
                frequency.put(c, ++count);
            }
        }

        printResult(frequency);
    }

    private void printResult(HashMap<Character, Integer> frequency) {
        for (int i = 0; i < 26; ++i) {
            char letter = (char) ('A' + i);
            System.out.printf("%c : %d\n", 'A' + i, frequency.getOrDefault(letter, 0));
        }
    }

    public static void main(String[] args) {
        String str = "SDJHSHVKJAKJSIVJLKASDJKFHKJAHGVBHADFAL";
        Solution s = new Solution();
        s.calculateCharacterFrequency(str.toCharArray());
    }
}

其中 HashMap 的 getOrDefault() 方法的作用是，如果 get 的值不为 null ，就返回 get 到的值，如果 get 到的值为 null，就返回调用方法时传入的一个默认值。

所有英文字符都统计

思路：把数组长度设置为 256，保证 ASCII 表中的字符都可以统计。

所有字符都统计

思路：使用 HashMap。

参考资料

1.一道迅雷面试题:求出一个字符串中每个字母出现的次数 | 链接2-可能不稳定