美文网首页
【剑指Offer学习】【面试题35:第一个只出现一次的字符】

【剑指Offer学习】【面试题35:第一个只出现一次的字符】

作者: 林大鹏 | 来源:发表于2018-01-30 17:01 被阅读24次

题目:

在字符串中找出第一个只出现一次的字符。

思路:

  • 由于题目与字符出现的次数相关, 我们是不是可以统计每个字符在该字符串中出现的次数?要达到这个目的,我们需要一个数据容器来存放每个字符的出现次数。在这个数据容器中可以根据字符来查找它出现的次数。

  • 我们可以开辟一个哈希数组,全部初始化为0,然后遍历字符串将字符串中字符对应的映射位置每次加1,表示这些位置对应的字符出现的次数。

  • 然后再次从头开始遍历字符串,找到字符串在哈希数组中对应映射位置值为1的字符,找到就直接返回,否则返回空。

代码:

#import <Foundation/Foundation.h>

/**
 找到 第一个不重复出现的字符

 @param charArray 字符数组
 @param charArrayLength 字符数组长度
 @return 返回第一个不重复 出现的字符
 */
char firstNotRepeatingChar(char *charArray, int charArrayLength) {
    if (charArray == NULL) {
        return '\0';
    }
    
    if (charArrayLength <= 0) {
        return '\0';
    }
    
    if (charArrayLength == 1) {
        return charArray[0];
    }
    
    // 保存 字符数组 第一个字符 位置
    char *firstCharAddress = charArray;
    int hashTable[256];
    memset(hashTable, 0, sizeof(hashTable));
    
    while (*charArray != '\0') {
        //ASCII值在128-255之间的的字符,
        //用char保存,转化为int型,在-128--1之间
        int index;
        if(*charArray >= 0)
            index = *charArray;
        else {
            index = *charArray + 256;
        }
        
        hashTable[index] ++;
        ++charArray;
    }
    // 赋值 字符 数组
    charArray = firstCharAddress;
    while (*charArray != '\0') {
        int index;
        if(*charArray >= 0)
            index = *charArray;
        else {
            index = *charArray + 256;
        }
        
        if (hashTable[index] == 1) {
            return *charArray;
        }
        ++charArray;
    }
    return '\0';
    
}
int main(int argc, const char * argv[]) {
    @autoreleasepool {
        char str1[] = "They are students";
        printf("%c\n", firstNotRepeatingChar(str1, sizeof(str1)));
    }
    return 0;
}

相关文章

网友评论

      本文标题:【剑指Offer学习】【面试题35:第一个只出现一次的字符】

      本文链接:https://www.haomeiwen.com/subject/ibhczxtx.html