亿✧个小目标~启程

面试题 01.01. 判定字符是否唯一（三种解法）

实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

示例 1：

输入: s = "leetcode"
输出: false 
示例 2：

输入: s = "abc"
输出: true
限制：

0 <= len(s) <= 100
如果你不使用额外的数据结构，会很加分。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/is-unique-lcci

1、利用Set集合特性

//algorithm：算法
public class Alg01 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        System.out.print("请输入字符串：");
        String str=scanner.nextLine();
        System.out.println(isUnique1(str));
    }
    //方法一：利用Set集合不可重复性
    private static boolean isUnique1(String str) {
        if(str==null){
            return false;
        }
        Set<Character> set=new HashSet<>();
        char[] chr=str.toCharArray();
        for (char c: chr) {
            if(!set.add(c)){
                return false;
            }
        }
        return true;
    }
}

小结：此方法较为简单，使用Set集合不可重复的性质实现

2、利用数组做标记

//algorithm：算法
public class Alg01 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        System.out.print("请输入字符串：");
        String str=scanner.nextLine();
        System.out.println(isUnique2(str));
    }
    //方法二：利用数组做标记(字符串范围26个英文字母）
    private static boolean isUnique2(String astr) {
        if(astr==null){
            return false;
        }
        int[] num=new int[26];
        for (char c:astr.toCharArray()) {
            num[c-'a']++;
            if(num[c-'a']>1){
                return false;
            }
        }
        return true;
    }
}

思路解析

3、利用位运算✧（较难）

//algorithm：算法
public class Alg01 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        System.out.print("请输入字符串：");
        String str=scanner.nextLine();
        System.out.println(isUnique2(str));
    }
   //方法三位运算
    /*由第一次与a减并左移一位运算后如果不重复也就是等于零，那么将lack的值设置为这次减a（num | (1<<lack)）的差值，作为一个标识，一旦遇到相同的
    * 在与lack进行&运算则会0*/
    private static boolean isUnique3(String str) {
        if(str==null){
            return false;
        }
        int num=0;
        for (char c: str.toCharArray()) {
            int lack=c-'a';
            if((num &(1<<lack))!=0){
                return false;
            }else{
                num=num | (1<<lack);
            }
        }
        return true;
    }
}

难点解析：

✧不求每天，但求坚持!!✧