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

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

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

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

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

  1. count["t"]++

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

w41d8nur

w41d8nur1#

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

  1. let say str = "abca";
  2. For each iteration :
  3. count['a'] = 1; or count[97] = 1; a has ascii value 97
  4. count['b'] = 1; or count[98] = 1; b has ascii value 98
  5. count['c'] = 1; or count[99] = 1; c has ascii value 99
  6. 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 值,并相应地分配数组:

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

回到你的问题:

  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”。
运行示例:

  1. import java.util.*;
  2. import java.util.stream.Collectors;
  3. public class SomeClass {
  4. public static void main(String[] args) {
  5. String str = "miaumiauuuuu";
  6. int count[] = new int[str.chars().max().getAsInt()+1];
  7. for (int i=0; i<str.length(); i++)
  8. count[str.charAt(i)]++;
  9. String str_without_duplicated_char = Arrays.stream(str.split(""))
  10. .distinct()
  11. .collect(Collectors.joining());
  12. for (int i=0; i<str_without_duplicated_char.length(); i++){
  13. System.out.println("The char '"+str_without_duplicated_char.charAt(i)+"' shows up "
  14. + count[str_without_duplicated_char.charAt(i)] +" times");
  15. }
  16. }
  17. }

输出:

  1. The char 'm' shows up 2 times
  2. The char 'i' shows up 2 times
  3. The char 'a' shows up 2 times
  4. The char 'u' shows up 6 times
展开查看全部

相关问题