day2 —— 判断字符串中的字符是否唯一
目录
前言
问题描述
代码解释
前言
若是想要了解基本语法的话,请到(7条消息) C语言从练气期到渡劫期_要一杯卡布奇诺的博客-CSDN博客查看相应的语法细节
强烈安利这篇文章 —— (4条消息) 筑基五层 —— 位运算看这篇就行了_要一杯卡布奇诺的博客-CSDN博客
问题描述
题目来源:面试题 01.01. 判定字符是否唯一 - 力扣(Leetcode)
代码解释
法一:暴力枚举比较
思路分析:直接循环遍历每个字符进行比较,找到了,返回false,没有找到,返回true
bool isUnique(char* astr)
{for(int i=0; i<strlen(astr); i++){for(int j=i+1; j<strlen(astr); j++){//找到相同字符if(astr[i] == astr[j])return false;}}//没有找到相同字符return true;
}
法二:哈希表
思路分析:把字符串中的值映射到哈希数组的下标中,字符串的每个字符在哈希数组着中有对应的下标,则该下标自增,如果哈希中有大于1的值,则说明字符串的字符不唯一
bool isUnique(char* astr)
{char hash[128] = {0};//哈希数组memset(hash,0,sizeof(hash));//初始化//把字符的对应值映射到哈希数组中for(int i=0; i<strlen(astr); i++)hash[astr[i]]++;for(int i=0; i<128; i++){//判断有没有下标的值超过1的if(hash[i] > 1)return false;} return true;
}
法三:排序
思路分析:进行排序,排序后比较相邻的值,如果有相同的值则说明字符串中的字符不唯一
bool isUnique(char* astr)
{//空指针判断if(astr == NULL)return false;//空串判断 if(strlen(astr) == 0)return true;//冒泡排序for(int i=0; i<strlen(astr)-1;i++){int flag = 1;//假设有序for(int j=0; j<strlen(astr) - i - 1; j++){if(astr[j] > astr[j+1]){flag = 0;//无序char tmp = astr[j];astr[j] = astr[j+1];astr[j+1] = tmp;}}//有序则跳出循环if(flag == 1)break;}for(int i=0; i<strlen(astr)-1; i++){//判断相邻字符if(astr[i] == astr[i+1])return false;}return true;
}
法四:双指针
思路分析:使用双指针进行对字符串遍历,思路和暴力枚举的思路一样
bool isUnique(char* astr)
{ char* cur = astr;assert(astr);//判断空指针//空串判断if (strlen(astr) == 0)return true;while (*astr != '\\0'){cur++;//指向astr的下一个if (*cur != '\\0'){char* tmp = cur;while (*tmp != '\\0'){//比较if (*tmp == *astr)return false;tmp++;}}astr++;}return true;}
!!恭喜你完成第二天的修仙之旅!!