day2 —— 判断字符串中的字符是否唯一

目录

前言

问题描述

代码解释

前言

若是想要了解基本语法的话，请到(7条消息) C语言从练气期到渡劫期_要一杯卡布奇诺的博客-CSDN博客查看相应的语法细节

强烈安利这篇文章 —— (4条消息) 筑基五层 —— 位运算看这篇就行了_要一杯卡布奇诺的博客-CSDN博客

问题描述

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

题目来源：面试题 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;

}

         ！！恭喜你完成第二天的修仙之旅！！