01.01. 判定字符是否唯一(简单)

Posted on In Views:

1，问题描述

面试题 01.01. 判定字符是否唯一

难度：简单

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

示例 1：

1
2
输入: s = "leetcode"
输出: false

示例 2：

1
2
输入: s = "abc"
输出: true

限制：

  • 0 <= len(s) <= 100
  • s[i]仅包含小写字母
  • 如果你不使用额外的数据结构，会很加分。

2，初步思考

​ 解法1:空间换时间

​ 解法2:排序后依次比较是否重复

​ 解法3:位运算，本质就是空间换时间，只是这个空间很小，空间复杂度O(1)

3，代码处理

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
37
38
import java.util.Arrays;

public class _面试题01_01判定字符是否唯一 {

    // 位运算解决
    public boolean isUnique_bit(String astr) {
        int mark = 0, idx = 0;// 本身缓存数据
        for (char c : astr.toCharArray()) {
            idx = 2 << (c - 'a');
            if ((mark & idx) != 0) return false;
            mark |= idx;
        }
        return true;
    }

    // 排序后比较
    public boolean isUnique_sort(String astr) {
        char[] charArray = astr.toCharArray();
        Arrays.sort(charArray);
        int len = charArray.length;
        for (int i = 0; i < len - 1; i++) {
            if (charArray[i] == charArray[i + 1]) return false;
        }
        return true;
    }

    // 空间换时间
    public boolean isUnique_area(String astr) {
        int[] dp = new int['z' + 1];
        char[] charArray = astr.toCharArray();
        int len = charArray.length;
        for (int i = 0; i < len; i++) {
            if (dp[charArray[i]] == 1) return false;
            dp[charArray[i]] = 1;
        }
        return true;
    }
}