了解字符串算法中的“查找最大占用字符”

u4dcyp6a  于 2021-07-03  发布在  Java
关注(0)|答案(2)|浏览(346)

我在学习数据结构和算法,还有一个小问题,就是如何找到字符串中出现最多的字符。
我理解一般的目标——拥有一个表示特定字符计数的数组,我显然理解如何在数组中找到max,但我对这堆代码(来自https://www.geeksforgeeks.org/return-maximum-occurring-character-in-the-input-string/):

int count[] = new int[256]; 

          for (int i=0; i<str.length(); i++) 
            count[str.charAt(i)]++; <-- what I don't understand

我正在初始化count数组以保存int,但在for循环中,我正在搜索字符串中的特定字符,例如:

count["t"]++

所以它基本上告诉我“给我指数t的值”?我怎么能用chararter搜索我应该用索引搜索的地方呢?
在Kotlin我也有了期待( count[str.get(i)] )应该是int,而不是char。
我可能错过了阻止我理解这一点的基本概念,但在短暂的谷歌搜索之后,我没有找到太多。

w41d8nur

w41d8nur1#

基本上, count[str.charAt(i)]++ ,存储输入字符串中每个字符的计数。java将每个char索引转换为ascii值。

let say str = "abca";

For each iteration : 
count['a'] = 1; or count[97] = 1;  a has ascii value 97
count['b'] = 1; or count[98] = 1;  b has ascii value 98
count['c'] = 1; or count[99] = 1;  c has ascii value 99
count['a'] = 2; or count[97] = 2;
3gtaxfhh

3gtaxfhh2#

java将转换 char 变成一个 int ,例如,“a”到 65 根据 ASCII table。

只要你 string 不包含将返回大于的值的字符 255 (例如。, "€" ),一组 256 位置将足以绘制可能的 chars 进入阵列位置。例如,对于英语字母表来说,这就足够了。然而,由于java中的char是 2 bytes (16位),大小的数组 65536 (2^16)足够安全了。您还可以计算
max int 值,并相应地分配数组:

int count[] = new int[str.chars().max().getAsInt()+1];

回到你的问题:

count[some_char]++

皈依者 some_char 变成一个 int ,并在相应数组上递增一个值 count 位置。
你可以把这个过程看作是一个简单的散列函数,它将charMap到int,尽管它很简单,但它非常适合当前的问题,因为它唯一地将给定的charMap到数组上的一个位置。
我正在初始化count数组以保存int,但在for循环中,我正在搜索字符串中的特定字符,例如:
count[“t”]++所以它基本上告诉我“给我索引“t”的值”?我怎么能用chararter搜索我应该用索引搜索的地方呢?
请注意 count["t"]++ 会给你一个编译错误,函数 str.charAt(i) 还给你一个 char ,不是 String ,因此是“t”,而不是“t”。
运行示例:

import java.util.*;
import java.util.stream.Collectors;

public class SomeClass {

    public static void main(String[] args) {
        String str = "miaumiauuuuu";
        int count[] = new int[str.chars().max().getAsInt()+1];
        for (int i=0; i<str.length(); i++)
            count[str.charAt(i)]++;

        String str_without_duplicated_char = Arrays.stream(str.split(""))
                .distinct()
                .collect(Collectors.joining());

        for (int i=0; i<str_without_duplicated_char.length(); i++){
            System.out.println("The char '"+str_without_duplicated_char.charAt(i)+"' shows up "
                    + count[str_without_duplicated_char.charAt(i)] +" times");
        }
    }
}

输出:

The char 'm' shows up 2 times
The char 'i' shows up 2 times
The char 'a' shows up 2 times
The char 'u' shows up 6 times

相关问题