当前位置：网站首页>【剑指offer系列】面试题日记(前期题)

//main主程序
#include<stdio.h>
int main()
{
    int a = 0,b = 0;
    scanf("%d%d",&a,&b);
    int temp = a;
    a = b;
    b = temp;
    printf("a = %d,b = %d\n",a,b);
    return 0;
}
-----------------------------
//利用指针
#include<stdio.h>
void Swap(int *p,int *q)
{
    int temp = *p;
    *p = *q;
    *q = temp;
}
int main()
{
    int a = 0,b = 0;
    scanf("%d%d",&a,&b);
    int *p = &a;
    int *q = &b;
    Swap(&a,&b);
    printf("a = %d,b = %d",a,b);
    return 0;
}

第二问：如果不使用第三方变量（temp）：

这里使用加减乘除四则运算都可以：

加法：

#include<stdio.h>
int main()
{
    int a = 0,b = 0;
    scanf("%d%d",&a,&b);
    a = a + b;
    b = a - b;
    a = a - b;
    printf("a = %d,b = %d\n",a,b);
    return 0;
}

减法：

    a = a - b;
    b = a + b;
    a = b - a;

乘法：

    a = a * b;
    b = a / b;
    a = a / b;

除法：

    a = a / b;
    b = a * b;
    a = b / a;

第三问：面试官这时可能会问，那你知不知道四则运算交换法存在有哪些问题？

总结：四则运算交换法是存在问题的：

四则运算法没有第三方变量交换的方法直观；

在乘法和除法交换法中a和b任意一个数都不能为0；

四则运算交换法可能存在数据溢出的问题；

第四问：能不能不使用第三方变量，且a和b其中一个值可以等于0，还可以完成数据交换？

这里我们通过位运算（异或）的方式：

#include<stdio.h>
int main()
{
    int a = 0,b = 0;
    scanf("%d%d",&a,&b);
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;（运算方式是相同为0，不同为1）
    printf("a = %d,b = %d\n",a,b);
    return 0;
}

运行结果：

第五问：如果使用位运算异或交换法也存在一个问题，就是不能使用浮点值（浮点值是不能进行位运算的），能不能不使用上面的方法也不使用异或交换法：

直接将a和b的内存进行交换即可：

void swap(double *a,double *b)
{
    char temp[10];
    memcpy(temp,a,sizeof(*a));
    memcpy(a,b,sizeof(*b));
    memcpy(b,temp,sizeof(*a));
}

对程序的说明：语句实际上的意思是将a的内存直接拷贝给temp，然后再将b的内存直接拷贝给a，再将temp的内存拷贝给b。

运行结果：

比较两个数：

第一问：给你两个数，怎么比较出他们两个的大小？

解决方法1：直接使用if判断语句：

int get_max1(int a,int b)
{
    if(a >= b){
        return a;
    }
    else{
        return b;
    }
}

第二问：如果不使用if条件判断句其他的方法：

解决方法2:三目运算符：

int get_max2(int a,int b)
{
    return a > b ? a : b;
}

第三问：如果不使用if条件判断句和三目运算符，其他的方法？

解决方法3:使用switch语句：

int get_max3(int a,int b)
{
    switch(a > b){
        default:printf("error\n");
        break;
        case 0: return b;
        case 1: return a;
    }
}

第四问：不使用上述三种方法，其他的方法？

解决方法4: 利用循环语句：

int get_max4(int a,int b)
{
    return(a > b) * a + (b > a) * b;
}
int

第五问：不使用上述四种方法，其他的方法？

解决方法5:使用纯数学的方式，两个数的和加上两个数的差（绝对值）再除以2，绝对值使用abs函数，所以在开头要加上头文件：

#include<math.h>
int get_max5(int a,int b)
{
    return((a + b) + abs(a - b)) / 2;
}

在这里给出五种方法的代码：

#include<stdio.h>
#include<math.h>
int get_max1(int a,int b)
{
    if(a >= b){
        return a;
    }
    else{
        return b;
    }
}
int get_max2(int a,int b)
{
    return a > b ? a : b;
}
int get_max3(int a,int b)
{
    switch(a > b){
        default:printf("error\n");
        break;
        case 0: return b;
        case 1: return a;
    }
}
int get_max4(int a,int b)
{
    return(a > b) * a + (b > a) * b;
}
int get_max5(int a,int b)
{
    return((a + b) + abs(a - b)) / 2;
}
int main()
{
    int a = 0,b = 0;
    scanf("%d%d",&a,&b);
    printf("\n%d",get_max1(a,b));
    printf("\n%d",get_max2(a,b));
    printf("\n%d",get_max3(a,b));
    printf("\n%d",get_max4(a,b));
    printf("\n%d",get_max5(a,b));
    return 0;
}

如图我输入2和3来验证这五种方法，运行结果为：

sizeof关键字：

int main()
{
    int ar[3];
    int *a[3];
    int **aa[3][4];
    int ***aaa[3][4][5];
    int (*br)[4];
    printf("%d\n",sizeof(ar));
    printf("%d\n",sizeof(a));
    printf("%d\n",sizeof(aa));
    printf("%d\n",sizeof(aaa));
    printf("%d\n",sizeof(br));
}

此程序中，输出结果为？

我们对程序进行分析：

在第一行中，我们定义一个整形数组，所以数组中一共有三个元素，一个元素为4个字节，所以第一个语句返回ar的大小值应该是12

在第二行中，我们先观察有没有小括号和中括号，因为他们的优先级均高于“*”，第二行中有中括号，首先明确他是一个数组，“*”在前面，所以我们可以推断这是一个存放指针变量的数组，只要是指针，无论是什么类型，它的大小始终都是4字节，a中存放了三个指针，所以大小是12

在第三行中，没有小括号的存在，可以发现这是一个二维数组，二维数组中存放的是（int **）类型的值，因为存放的是指针，所以大小为4，所以大小为：3 * 4 * 4 = 48

在第四行中，也没有小括号，这是一个多位数组，里面每个单元格存放的是（int ***）类型的值，每个值的大小也是4，所以总大小为：3 * 4 * 5 * 4 = 240

在第五行中，有小括号，小括号的优先级是高于中括号和指针，只看小括号是指针，所以明确这是一个指向数组的指针，只要是指针无论他的类型，大小一律都是4.

因为我是macOS，所以指针的大小默认为8字节，所以运行结果应该是：12，24，96，480，4.我们使用程序进行验证：

在这里需要明确两个名词：

指针数组：就是存放指针的数组

数组指针：就是指向数组的指针

另外牵扯到优先级的问题，括号的优先级是高于指针操作符“*”的，例如上面的（*br）[4]中有小括号和大括号，先看小括号*br是一个指针，所以这个语句的意思是存放*br指针的数组。

sizeof问题（简单题）：

循环中的范围问题：

这里先看代码：

int main()
{
    int ar[3] = {12,23,34};
    int *br = (int *)malloc(3 * sizeof(int));
    if(br == NULL)
    {
        return 0;
    }
    br[0] = 45;
    br[1] = 56;
    br[2] = 67;
    for(int i = 0;i < sizeof(ar) / sizeof(int);++i){
        printf("%d ",ar[i]);
    }
    for(int i = 0;i < sizeof(br) / sizeof(int);++i){
        printf("%d ",br[i]);
    }
    return 0;
}

在这里我定义了一个元素个数为3的一位数组ar，定义了一个指针br向系统申请两个int类型的内存空间用于存储接下来的三个数，我意图通过两个for循环分别将ar和br打印了出来，在for循环里面的范围均是（i < sizeof(ar) / sizeof(int)），现在来看运行结果：

如图，系统将ar完整的打印了出来，但是br只打印出来了两个数据，下面来分析出现这种情况的原因：

在（i < sizeof(ar) / sizeof(int)）语句中，使用ar数组的总大小除以int类型值的大小，刚好就是3，ar的总大小为12，int类型值的大小为4。

但在（i < sizeof(br) / sizeof(int)）语句中，br本身是一个指针，指针的大小无关类型和级数，因为我是64位操作系统，大小始终都是8，所以br的总大小应该始终都是8字节，int类型的大小为4字节，结果为2，所以只会打印两个数据。

可以将语句这样更改：（i < sizeof(*br) * 3 / sizeof(int)）,后面和多少相乘取决于br所存储的元素有几个。我们再来看运行结果：

关于sizeof性质问题：

代码：

int main()
{
    int n = 10;
    printf("%d\n",sizeof(n));
    printf("%d\n",sizeof(n=6));
    printf("%d\n",sizeof(n++));
    printf("%d\n",n);
}

看一下运行结果：

在这里可以看到，sizeof关键字打印出来的前三行均是4，所以n = 6，n++语句均没有起到实质性作用，所以前三个sizeof中的语句均会转换成数据类型也就是都会转化为sizeof（int)，无论n怎样变化，数据类型都为int类型，所以都是4，最后由于n的值本身就是10，所以输出结果为10.

这种情况：

int n = 10;
printf("%d ",sizeof(n > 6));

这种情况下，n > 6 是一个判断语句，语句结果只有两种情况，是一个bool类型。

sizeof(bool)返回值就是一个1(无论语句中的命题是否成立)。

总结：首先明确sizeof并不是一个函数，也不是一个一元运算符，而是一个类似于宏的特殊关键字，sizeof括号中的内容在编译的过程中是不会被编译的，而是直接获取其数据类型。

面试指针相关（简单题）：

问题1：在一堆数据中，除了一个数据是单独出现的，其他的数据都是成对出现的，现在需要找到这个单独出现的数据：

int ar[] = {12,23,34,45,56,12,23,34,45};

思路：通过位运算异或，异或的法则是相同为0，不同为1，除了一个值所有的值都是成对出现的，所以最终结果就是那个单独出现的值。

代码：

#include<stdio.h>
{
    int ar[] = {12,23,34,45,56,12,23,34,45};
    int n = 0;
    for(int i = 0;i < sizeof(ar) / sizeof(ar[0]);i++){
        n = n ^ ar[i];
    }
    printf("The single number is %d\n",n);
    return 0;
}

运行结果：

总结：两个相同的数进行异或，结果为0；

0和任何一个值进行异或，结果都是任何一个值。

问题2（问题1的变式）：一堆数据中除了两个数据是单独出现的，其他数据都是成对出现的，现在需要找出那两个单独出现的数据：

int ar[] = {12,23,34,45,56,67,12,23,34,45};

思路：将这组数据分为两部分，保证这两个单独的数据分开（依然采用位运算）：

例如1的二进制表示为：00000001，让数组中的元素都与二进制形式的1进行异或，就可以将数组中的元素分为两个不同的部分：

#include<stdio.h>
int main()
{
    int ar[] = {12,23,34,45,56,67,45,34,23,12};
    int n = 0;
    for(int i = 0;i < sizeof(ar) / sizeof(ar[0]);i++){
        n = n ^ ar[i];
    }
    int index = 1;
    while((n & index) != 1){
        index *= 2;
    }
    //此时两个单独的数在二进制位上，权重位index的这个位不同
    int num1 = 0;
    int num2 = 0;
    for(int i = 0;i < sizeof(ar) / sizeof(ar[0]);i++){
        if((ar[i] & index) == 1){
            num1 = num1 ^ ar[i];
        }
        else{
            num2 = num2 ^ ar[i];
        }
    }
    printf("num1 = %d,num2 = %d",num1,num2);
    return 0;
}

我们来看运行结果：