面试手撕代码

面试常见的手撕代码题型

所有代码都已经跑过，可以正常编译运行。

经典排序

冒泡排序

/* 交换两个数据 */
void swap(int *a, int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;

    return;
}

/* 冒牌排序算法 */
void BubbleSort(int arr[], size_t len)
{
    if(NULL == arr)
        return ;
    int i=0, j=0;
    for(i=0; i<len; i++)
    {
        for(j=1; j<len-i-1; j++)
        {
            if(arr[j]<arr[j-1])
                swap(arr[j], arr[j-1]);
        }
    }

    return;
}
   
int main(int argc, char *argv[])
{
    int i=0;
    int arr[10]={7, 5, 7, 9, 1, 0, 8, 7, 8};
    BubbleSort(arr);
    for(i=0; i< sizeof(arr)/sizeof(arr[0]);i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

输出结果：

0 1 5 7 7 7 8 8 9

快速排序

void swap(int *a, int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;

    return ;
}

void quickSort(int arr[], int left, int right)
{
    int i, j, temp;
    if(left > right)
        return;
    /* temp存放的是基数 */
    temp = arr[left];
    i = left;
    j = right;
    while(i != j){
        /* 顺序很重要，要从右边开始找 */
        while(arr[j] >= temp && i < j)
            j--;
        /* 再从左开始找 */
        while(arr[i] <= temp && i < j)
            i++;
        if(i < j)
            swap(&arr[i], &arr[j]);
    }
    arr[left] = arr[i];
    arr[i] = temp;

    quickSort(left, i-1);
    quickSort(i+1, right);

    return ;
}

查找算法

二分查找

二分查找也叫做折半查找，其优点是查找速度快，缺点是要求所要査找的数据必须是有序序列。

int binarySearch(int arr[], int n, int key)
{
    int low = 0;
    int hight = n-1;
    int mid, midVal;
    while(low <= hight){
        mid = (low+hight)/2;
        midVal = arr[mid];
        if(midVal < key)
            low = mid+1;
        else if(midVal > key)
            hight = mid-1;
        else
            return 1;
    }

    return 0;
}

int main(int argc, char *argv[])
{
    int key=0;
    int a[8]={-32, 12, 16, 24, 36, 45, 59, 98};
    for(int i=0; i<sizeof(a)/sizeof(a[0]); i++)
        printf("%d ", a[i]);
    printf("\n");
    printf("Please input the data.\n");
    scanf("%d", &key);
    int ret = binarySearch(a, sizeof(a)/sizeof(a[0]), key);
    if (1 == ret)
        printf("the key %d is exits.\n", key);
    else
        printf("the key %d is not exits.\n", key);

    return 0;
}

链表操作

反转单链表

/* 定义链表结构 */
typedef struct _listNode{
    int value;
    struct _listNode *next;
}listNode;

/* 反转链表 */
listNode *reverseList(listNode *head)
{
    if(NULL == head || NULL == head->next)
        return head;
    listNode *cur = head;
    listNode *prev = NULL;
    listNode *next = NULL;
    while(cur != NULL){
        /* 存放下一个节点 */
        next = cur->next;
        /* 翻转头结点的下一个节点 */
        cur->next = prev;
        /* 移动上一个节点 */
        prev = cur;
        /* 更新当前节点 */
        cur = next;
    }

    return prev；
}

int main(int argc, char *argv[])
{
    int arr[]={7,5,7,9,1,0,8,7,8};
    quickSort(arr, 0, sizeof(arr)/sizeof(arr[0])); 
    for (int i = 0; i < sizeof(arr)/sizeof(arr[0]); ++i)
    {
        /* code */
        if(0==i%16)
            printf("\n");
        printf("%d\n", arr[i]);
    }

    return 0;
}

判断链表是否有环

/* 判断链表是否有环 */
linkNode *isCircle(linkNode *head)
{
    assert(head != NULL);
    linkNode *slow = head->next;               /* 慢指针 */
    linkNode *fast = head->next->next;         /* 快指针 */
    while(fast != NULL && fast->next != NULL){
        if(slow == fast)
            break;
        slow = slow->next;
        fast = fast->next->next;
    }

    if(fast == NULL || fast->next == NULL)
         return NULL;   /* 无环 */
     else
        return slow;    /* 有环 */
}

字符串操作

实现memcpy函数

/* 不考虑内存重叠的情况 */
void *myMemcpy(void *dest, const void *src, size_t n)
{
    if(NULL == dest||NULL == src)
        return NULL;
    char *d = (char *)dest;
    char *s = (char *)src;
    while(n--)
        *d++ = *s++;
    return dest;
}

/* 优化版本按照CPU位宽度进行拷贝优化 */
void  *myMemcpy(void *dest, const void *src, size_t n)
{
    int nchucks = num/sizeof(dest);  /* 按照CPU的位宽进行拷贝 */
    int slice = num%/sizeof(dest);   /* 剩余的字节数按照一个一个字节进行拷贝 */

    unsigned long *s = (unsigned long *)src;
    unsigned long *d = (unsigned long *)dest;

    while(nchucks--)
        *d++ = *s++;
    while(slice--)
        *((char*)d++) = *((char*)s++);

    return dest;
}

/* 考虑内存重叠的情况 */

实现strstr函数

void *myStrstr() {
    return;
}

实现strlen函数

int myStrlen(const char *arr)
{
    assert(arr);
    int count=0;
    while('\0' != *arr++)
        count++;

    return count;
}

实现strcpy函数

char *myStrcpy(char *dest, const char *src)
{
    assert(dest);
    assert(src);
    char *d = dest;
    char *s = src;
    while('\0' != *s)
        *d++ = *s++;
    return dest;
}

reference

[1] https://blog.csdn.net/weixin_43496874/article/details/100868367?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-4.control&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-4.control

[2] http://c.biancheng.net/cpp/html/2744.html