思路讲解与算法实现 LeetCode - 判定字符是否唯一
每天一道公司算法真题，讲解解题思路与各种算法实现；欢迎大家点评或者说出你的解题想法，或评论想让我讲解哪道题！
题目
实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
示例1：
- 输入： s = “leetcode”
- 输出：false
示例2：
- 输入：s = “abc”
- 输出：true
限制
- 0 <= len(s) <= 100
- 如果你不使用额外的数据结构，会很加分。
解法一
判断一个字符串中所有字符是否唯一，最简单的暴力求解就是两两对比是否相同，即双重循环，但是算法复杂度为O(n^2)，性能也是最低的。
package com.nobody;
/**
* @Description 实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
* @Author Mr.nobody
* @Date 2021/4/18
* @Version 1.0
*/
public class StrIsUnique { public boolean isUnique(String astr) { // 字符串为null或者为空，自然没有字符重复，即唯一 if (null == astr || 0 == astr.length()) { return true; } // 双重循环，两两对比 for (int i = 0; i < astr.length() - 1; i++) { for (int j = i + 1; j < astr.length(); j++) { if (astr.charAt(i) == astr.charAt(j)) { return false; } } } return true; } public static void main(String[] args) { String astr = "leetcode"; StrIsUnique strIsUnique = new StrIsUnique(); System.out.println(strIsUnique.isUnique(astr)); }
}
- 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
解法二
既然是判断唯一性，那我们可以遍历每一个字符，然后通过某种规则将它们放入指定位置，因为相同字符肯定会被放到相同的位置，我们只需要判断放入此位置之前是否有字符放入过，如果有，就代表有重复的字符。借助散列表这种数据结构就能达到这种效果。
package com.nobody;
import java.util.HashMap;
import java.util.Map;
/**
* @Description 实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
* @Author Mr.nobody
* @Date 2021/4/18
* @Version 1.0
*/
public class StrIsUnique { public boolean isUnique(String astr) { // 字符串为null或者为空，自然没有字符重复，即唯一 if (null == astr || 0 == astr.length()) { return true; } Map<Character, Integer> map = new HashMap<>(astr.length() + 1); // 遍历每一个字符，从map中判断是否存在相同的字符 for (int i = 0; i < astr.length(); i++) { // 存在相同的字符 if (null != map.get(astr.charAt(i)) && map.get(astr.charAt(i)) == 1) { return false; } // 在map中不存在此字符，放入map中 map.put(astr.charAt(i), 1); } return true; } public static void main(String[] args) { String astr = "陈皮的JavaLib"; StrIsUnique strIsUnique = new StrIsUnique(); System.out.println(strIsUnique.isUnique01(astr)); }
}
- 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
解法三
如果我们不再借助其他数据结构，如何解法呢？因为要求唯一性，肯定要有字符比较的。解法二我们借助了散列表这种数据结构，结果内存消耗方面只击败了27.28%的用户。
假设字符串中的字符是26个小写字母，解法二是将每一个字符放入散列表中，如果散列表中每一个位置都没有重复的字符，则唯一性。那我们可以将每一个字符映射到一个二进制数组中，通过与运算，如果相同位置都为1，则结果为1，则代表有重复字符。
借助一个初始值为0的int变量mark，二进制形式为0000…0000，遍历每一个字符，计算字符与a字符的距离move_bit，然后使用左移运算符1 << move_bit创建对应下标为1，其余下标为0的数num。将num与mark做与运算，如果结果不为0，则代表有重复字符。如果结果为0，则代表这个字符之前没出现过，将num和mark通过或运算的结果赋值给mark，即在mark中将此字符的对应下标的值设为1。
package com.nobody;
import java.util.HashMap;
import java.util.Map;
import java.util.function.BinaryOperator;
/**
* @Description 实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
* @Author Mr.nobody
* @Date 2021/4/18
* @Version 1.0
*/
public class StrIsUnique { public boolean isUnique02(String astr) { // 字符串为null或者为空，自然没有字符重复，即唯一 if (null == astr || 0 == astr.length()) { return true; } int mark = 0; int num = 0; // 遍历每一个字符 for (int i = 0; i < astr.length(); i++) { num = 1 << (astr.charAt(i) - 'a'); // 通过与运算判断对应下标是否都为1，即是否有相同字符 if ((mark & num) != 0) { return false; } // 在map中将对应下标置为1 mark |= num; } return true; } public static void main(String[] args) { String astr = "javalib"; StrIsUnique strIsUnique = new StrIsUnique(); System.out.println(strIsUnique.isUnique02(astr)); }
}
- 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
- 39
- 40
上下篇
上一篇：思路讲解与算法实现 LeetCode - 实现 strStr()
下一篇：思路讲解与算法实现 LeetCode - 判定是否互为字符重排
文章来源: javalib.blog.csdn.net，作者：陈皮的JavaLib，版权归原作者所有，如需转载，请联系作者。
原文链接：javalib.blog.csdn.net/article/details/115815577
- 点赞
- 收藏
- 关注作者
评论（0）