【Leetcode 程序员面试金典 01.01】判定字符是否唯一 —— 位运算|哈希表

简介: 可以使用哈希表或位运算来解决此问题:由题可知s[i]仅包含小写字母,int[26]即能表示字符的出现次数;

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

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

示例 1:

输入: s = "leetcode"
输出: FALSE

示例 2:

输入: s = "abc"
输出: TRUE

限制:

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

题目分析

哈希表

由题可知:s[i] 仅包含小写字母,故可以使用int[26]来标识 a-z 的出现次数,看是否存在相同字符

/**
 * 哈希表
 * @param astr
 * @return
 */
public boolean isUnique(String astr) {
   
    int[] tmp = new int[26];
    char[] chars = astr.toCharArray();
    for(char c : chars){
   
        if(tmp[c - 'a'] != 0){
   
            return false;
        }
        tmp[c - 'a']++;
    }
    return true;
}

位运算

由题可知:s[i] 仅包含小写字母,在 ASCII 码中,英文小写字母的序号范围是 97 到 122

  • 1L << 0 即为 a 字符存储位置
  • 1L << 25 即为 z 字符存储位置

算法思路:

  • i & (1 << k)用于判断 i 的第 k 位数字是否为 0;实际上和数组或哈希表记录相似,相当于nums[k]
  • i | (1 << k)用于将 i 的第 k 位数字赋值为 1, 相当于 nums[k] = 1
public boolean isUnique(String astr) {
   
    int tmp = 0;
    for (char k : astr.toCharArray()) {
   
        int bitIndex = 1 << (k - 97);
        if ((tmp & bitIndex) != 0) {
   
            return false;
        }
        tmp |= bitIndex;
    }
    return true;
}
相关文章
|
1月前
|
算法
【数组相关面试题】LeetCode试题
【数组相关面试题】LeetCode试题
|
1月前
|
存储
LeetCode刷题---817. 链表组件(哈希表)
LeetCode刷题---817. 链表组件(哈希表)
|
1月前
|
存储 Java
面试官:你真的搞清位运算了么?
面试官:你真的搞清位运算了么?
31 0
|
1月前
力扣面试经典题之哈希表
力扣面试经典题之哈希表
18 0
|
1月前
|
存储
力扣面试经典题之数组/字符串
力扣面试经典题之数组/字符串
23 0
|
1月前
力扣面试经典题之二叉树
力扣面试经典题之二叉树
16 0
|
2月前
|
JavaScript 前端开发 C语言
leetcode每日一题 2021/4/2 面试题 17.21. 直方图的水量
leetcode每日一题 2021/4/2 面试题 17.21. 直方图的水量
23 0
|
21天前
|
算法
【力扣经典面试题】121. 买卖股票的最佳时机
【力扣经典面试题】121. 买卖股票的最佳时机
|
21天前
|
存储
【力扣经典面试题】80. 删除有序数组中的重复项 II
【力扣经典面试题】80. 删除有序数组中的重复项 II
|
1月前
|
网络协议
《 LeetCode 热题 HOT 100》——无重复字符的最长子串
《 LeetCode 热题 HOT 100》——无重复字符的最长子串