题意整理。

  • 输入一行没有空格的字符串。
  • 统计字符串中不同字符的种数（要求ASCII码在0-127范围内）。

方法一（set）

1.解题思路

  • 新建一个set，用于记录不同字符的种数。
  • 然后遍历整个字符串，将范围内的字符加入到set。由于set中不允许出现重复的元素，所以set的大小即是不同字符的种数。

动图展示： alt

2.代码实现

import java.util.Scanner;
import java.util.HashSet;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String s=sc.nextLine();
        //用于记录不同字符的种数
        HashSet<Character> set=new HashSet<Character>();
        //遍历所有字符
        for(int i=0;i<s.length();i++){
            char c=s.charAt(i);
            //如果在范围内，则加入到set
            if(c>=0&&c<=127){
                set.add(s.charAt(i));
            }
        }
        //set的大小即是不同字符的种数
        System.out.println(set.size());
    }
}

3.复杂度分析

  • 时间复杂度：假设字符串长度为n，需要遍历字符串中每一个字符，所以时间复杂度为O(n)O(n)。
  • 空间复杂度：不同字符种数最多为128种，需要set的大小为常数级别，所以空间复杂度为O(1)O(1)。

方法二（位图）

1.解题思路

  • 新建位图，用于后续将字符串映射到位图。
  • 然后遍历整个字符串，将范围内的字符set到位图。然后利用cardinality统计不同字符的种数。

与方法一相比，最多只需128位的空间，大大地降低了空间复杂度。

2.代码实现

import java.util.Scanner;
import java.util.BitSet;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String s=sc.nextLine();
        //新建位图
        BitSet bit=new BitSet();
        for(int i=0;i<s.length();i++){
            char c=s.charAt(i);
            //将ASCII码在0-127范围内的字符加入到位图
            if(c>=0&&c<=127){
                bit.set(c);
            }
        }
        //输出统计的字符种数
        System.out.println(bit.cardinality());
    }
}

3.复杂度分析

  • 时间复杂度：假设字符串长度为n，需要遍历字符串中每一个字符，所以时间复杂度为O(n)O(n)。
  • 空间复杂度：需要额外常数级别的空间，所以空间复杂度为O(1)O(1)。