面试题-数组与字符串(C实现)

朱雀 2022-10-11 12:13 116阅读 0赞

### 1、实现一个算法，确定一个字符串的所有字符是否全都不同。假使不允许使用额外的数据结构，又该如何处理？ ###

分析：假设上面的字符串是由ASCII字符集构成的。ASCII字符集一共只有256个字符，我们可以构建一个256大小的数组即可。选择构建一个布尔数组，索引值 i 对应的标记指示该字符串是否含有ASCII字符集中第 i 个字符。若这个字符第2次出现，则立即返回false。示例代码如下：

#include <stdio.h>
    #include <string.h>
    #include <stdbool.h>  //C99版本引入
    
    bool isUniqueChars(char *str)
    {
    	int length = strlen(str);
    	if(length > 256)
    		return false;
    	bool charSet[256]={false};  //声明一个bool数组
    	for(int i=0; i<length; i++){
    		int var = str[i];       //将第i个字符对应的ASCII值作为布尔数组的索引值
    		if(charSet[var])
    			return false;
    		charSet[var] = true;
    	}
    	return true;
    }
    
    //测试用例
    int main(char *argv[], int argc)
    {
    	char str[256]={0};
    	char ch;
    	printf("Please input a string: ");
    	int i=0;
    	while((ch=getchar()) != '\n')
    		str[i++]=ch;
    	if(isUniqueChars(str))
    		printf("[%s] is a Unique chars.\n", str);
    	else
    		printf("[%s] isn`t a Unique chars.\n", str);
    	return 0;
    }

> 编译命令：gcc demo.c -std=c99 //以标准C99版本编译，下同
> 
> 示例运行结果：
> 
> >a.exe  
> Please input a string: abcdefg  
> \[abcdefg\] is a Unique chars.
> 
> >a.exe  
> Please input a string: aaabbbbccc  
> \[aaabbbbccc\] isn\`t a Unique chars.
> 
> >a.exe  
> Please input a string: a b c 1234  
> \[a b c 1234\] isn\`t a Unique chars.

解法2，如果不考虑使用数组也是可以的，可以将字符串中的每一个字符与其他字符进行两两比较，如果有相等的情况，则直接返回false。这种方法的时间复杂度为O(n^2)，而空间复杂度为O(1)。代码如下：

//解法2
    bool isUniqueChars2(char *str)
    {
        int length = strlen(str);
        if(length > 256)
            return false;
        for(int i=0; i<length; i++)
            for(int j=i+1; j<length; j++){
                if(str[i] == str[j])
                    return false;
            }
        return true;
    }

### 2、用C语言实现 void reverse(char\* str) 函数，即反转一个字符串。 ###

这是一个很经典的面试题，需要注意的是：不分配额外空间，直接就地反转字符串。提醒：C/C++语言的字符串是以 '\\0' 字符为字符串的结束标志的。

分析：该题可以使用数组和指针两种方式来实现，具体代码如下：

#include <stdio.h>
    #include <string.h>
    
    //方法1-使用数组
    void reverse(char *str)
    {
        int length = strlen(str);
        if(length < 2)
            return;
        for(int i=0; i<length/2; i++){
            char tmp = str[i];
            str[i] = str[length-i-1];
            str[length-i-1] = tmp;
        }
    }
    
    //方法2-使用指针
    void reverse2(char *str)
    {
        int length = strlen(str);
        if(length < 2)
            return;
        
        char *end = str;
        while(*end != '\0')
            end++;
        end--;       //使end指针指向字符串的最后一个字符
        
        //从字符串首尾交换两个字符，直至两个指针在中间碰头
        while(str < end){
            char tmp = *str;
            *str++ = *end;
            *end-- = tmp;
        }
    }
    
    //测试用例
    int main(char *argv[], int argc)
    {
        char str[256]={0};
        char ch;
        printf("Please input a string: ");
        int i=0;
        while((ch=getchar()) != '\n')
            str[i++]=ch;
        reverse(str);
        // reverse2(str);
        printf("Reversed string: %s\n", str);
        return 0;
    }

> 编译命令： gcc demo.c -std=c99
> 
> 示例运行结果：
> 
> >a.exe  
> Please input a string: abcdefg  
> Reversed string: gfedcba
> 
> >a.exe  
> Please input a string: 1234 abc def  
> Reversed string: fed cba 4321

### 参考 ###

《程序员面试金典(第5版)》第8章