手机网站demo,wordpress 知更鸟 公告,php开发做网站,地方文明网站建设01.01、[简单] 判定字符是否唯一
1、题目描述
实现一个算法#xff0c;确定一个字符串 s 的所有字符是否全都不同。
在这一题中#xff0c;我们的任务是判断一个字符串 s 中的所有字符是否全都不同。我们将讨论两种不同的方法来解决这个问题#xff0c;并详细解释每种方法…01.01、[简单] 判定字符是否唯一
1、题目描述
实现一个算法确定一个字符串 s 的所有字符是否全都不同。
在这一题中我们的任务是判断一个字符串 s 中的所有字符是否全都不同。我们将讨论两种不同的方法来解决这个问题并详细解释每种方法的实现过程。
2、方法一使用哈希表计数
2.1、思路解析
我们可以利用一个哈希表数组来记录字符串中每个字符的出现次数。具体步骤如下
字符数判断如果字符串的长度超过 26那么肯定有重复字符因为只有 26 个小写字母。哈希表初始化创建一个长度为 26 的数组 hash用于记录每个字符的出现次数。遍历字符串对于字符串中的每个字符将对应的哈希表位置加 1。重复字符检测在遍历过程中如果某个字符的出现次数大于 1直接返回 false。返回结果遍历结束后如果没有发现重复字符返回 true。
2.2、代码实现
class Solution {
public:bool isUnique(string astr) {// 如果字符串长度超过 26必然有重复字符if (astr.size() 26) {return false;}// 初始化一个哈希表长度为 26对应 26 个字母int hash[26] {0};// 遍历字符串中的每个字符for (const auto ch : astr) {// 将字符转换为相应的索引位置hash[ch - a];// 如果某个字符的计数大于 1则返回 falseif (hash[ch - a] 1) {return false;}}// 如果没有发现重复字符返回 truereturn true;}
};2.3、代码详解
首先检查字符串长度。如果长度超过 26立即返回 false因为小写字母只有 26 个无法保证全部字符唯一。初始化一个长度为 26 的整型数组 hash用于记录每个字母的出现次数。使用范围循环遍历字符串中的每个字符。计算当前字符在 hash 数组中的索引并将其对应的值加 1。如果某个字符的计数大于 1表示该字符重复立即返回 false。遍历结束后如果没有重复字符则返回 true。
3、方法二使用位图优化
3.1、思路解析
第二种方法使用了位图bit vector来优化空间复杂度。这种方法的核心思想是使用一个整数的位来表示字符是否出现过。具体步骤如下
字符数判断与方法一相同首先判断字符串长度是否超过 26。位图初始化使用一个整数 bitMap 来表示字符出现情况初始值为 0。遍历字符串对于字符串中的每个字符检查 bitMap 中相应的位置是否已经设置。重复字符检测如果 bitMap 中相应的位置已经设置过返回 false。否则将该位置设置为 1。返回结果遍历结束后如果没有发现重复字符返回 true。
3.2、代码实现
class Solution {
public:bool isUnique(string astr) {// 利用鸽巢原理来做的优化如果字符串长度超过 26必然有重复字符if (astr.size() 26)return false;// 使用位图bit vector来记录字符出现情况int bitMap 0;// 遍历字符串中的每个字符for (const auto ch : astr) {int i ch - a; // 将字符转换为相应的位位置// 判断当前字符是否已经在 bitMap 中出现过if (((bitMap i) 1) 1)return false; // 如果已出现返回 false// 将当前字符加入到 bitMap 中bitMap | 1 i;}// 如果没有发现重复字符返回 truereturn true;}
};3.3、代码详解
同样首先检查字符串长度。如果长度超过 26直接返回 false。初始化一个整型变量 bitMap初始值为 0用于记录字符的出现情况。遍历字符串中的每个字符。计算当前字符在 bitMap 中对应的位位置。检查 bitMap 中相应的位是否已经为 1。如果为 1表示该字符已出现过返回 false。如果当前字符没有出现过将对应的位设置为 1。遍历结束后如果没有重复字符返回 true。
4、总结
这两种方法都可以有效地判断一个字符串中的字符是否全都不同。方法一使用了哈希表代码直观易懂而方法二使用了位图优化节省了空间。如果字符串长度超过 26直接返回 false因为小写字母只有 26 个因此这是一种基于鸽巢原理的优化。选择哪种方法取决于具体的需求和优化目标。
