"常见手撕代码示例"

  "复习"

Posted by Xu on July 14, 2018

手写代码:

strcpy

char* strcpy(char *dst,char *src){
    assert(dst);
    assert(src);
    char *p = dst;
    while(*p++ = *src++);
    return dst;
}

strlen

int strlen(char *str){
    assert(str);
    int len = 0;
    while(*str++) len++;
    return len;
}

strcat

char *strcat(char *dst,char *src){
    assert(dst);
    assert(src);

    char *p = dst;
    while(*p) p++;
    while(*p++ = *src++);
    return dst;

}

memcpy

void *memcpy(char *dst,char *src)//可以带参数size
{
    assert(dst);
    assert(src);

    int len = 0;
    char *p = dst;
    char *s = src;
    while (*s){
        len++;
        p++;
        s++;
    } 
    if(dst - src <len && dst - src>0){//判断是否重复
        while(len--){
            *p-- = *s--;
        }
    }else{
        p = dst;
        s = src;
        while(*p++ = *s++);
    }

    return dst;
}

strcmp

int strcmp(char *str1,char *str2){
    assert(str1);
    assert(str2);

    while(*str1 == *str2 && str1 != '\0'){
        str1++;
        str2++;
    }

    if(str1 == str2){//说明str1到达末尾
        return 0;
    }
    //128种扩展ascii码使用最高位来标识,
    //所以在判断返回大于0还是小于0是,要转换为unsigned char,否则结果相反
    return *(unsigned char*)str1>*(unsigned char*)str2?1:-1;
}

quicksort

(partition过程中,交换结束后,hi指针位于分割元素的正确位置)

void quicksort(int *arr,int start,int end){
    if(start == end)
        return;
    if(arr == NULL)
        retrun ;
    int k = partition(arr,start,end);
    if(k-1>=start)
        quicksort(arr,start,k-1);
    if(k+1<=end)
        quicksort(arr,k+1,end);
}

int partition(int *arr,int lo,int hi){
    int p = arr[lo];
    int l = lo,h = hi+1;
    while(true){
        while(arr[++l]<p && l!=hi);
        while(arr[--h]>p && h!=lo);
        if(l>=h)
            break;
        swap(arr,l,h);//最后肯定是hi下标指向小于p的最后一个元素
     }
     swap(arr,lo,h);
     return h;
}

mergesort

(利用辅助空间,可以直接传进去处理,还有自底向上的方法)

void mergesort(int *arr,int start,int end){//传入一辅助空间,防止辅助空间不断创建和删除
    if(start == end)
        return;
    if(arr == NULL)
        return;
    int mid = (start+end)/2;
    if(mid>start)
        mergesort(arr,start,mid);
    if(mid+1<end)
        mergesort(arr,mid+1,end);
    merge(arr,start,mid+1,end);
}

void merge(int *arr,int start1,int start2,int end){
    int size = end-start1+1;
    int left = start1,right = start2;
    int copy[size];
    int i = 0;
    for( ;i<size;i++)
    {
        if(left<=start2-1 && right<=end)
            copy[i] = arr[left]<arr[right]?arr[left++]:array[right++];
        else
            break;
    }    

    if(left == start2){//处理尾部数据
        for(int j = right;j<=end;j++){
            copy[++i] = arr[j];
        }
    }else{
        for(int j = left;j<start2;j++){
            copy[++i] = arr[j];
        }
    }
    int k = 0;
    while(size--){//拷贝回原数组
        arr[start1+k] = copy[k];
        k++;
    }
}

堆排序

class Solution {
public:
  void sort_heap(vector<int> & vec) {
    make_heap(vec);
    int end = vec.size()-1;
    for (int i = 0; i < vec.size(); i++) {
      swap(vec[0],vec[end]);//将首元素和堆中最后一个元素互换
      down(vec,0,--end);//然后将首部元素下沉即可
    }
  }
  void make_heap(vector<int> & vec) {
    int len = vec.size();
    for (int i = len / 2 - 1; i >= 0; i--) {//对前N/2个元素进行下沉操作即可构建堆
      down(vec, i, len-1);
    }
  }
  void down(vector<int> & vec, int start, int end) {
    int pos = start;
    int child = 2*pos+1;
    while (child <= end) {//确定要交换的孩子节点的下标
      if (child+1 <=end && vec[child] > vec[child+1]) {
        child++;
      }

      if (vec[child] < vec[pos]) {//如果最小的孩子节点都小于该节点时,则交换位置
        swap(vec[child],vec[pos]);
      }
      else {
        break;//说明无需调整
      }
      pos = child;
      child = 2 * pos + 1;
    }
  }

};

智能指针的实现

  • 特别注意拷贝赋值的实现,要先递增被拷贝的智能指针的引用计数后递减被赋值的引用计数来支持自赋值
template <typename T>
Shared_Ptr{
public:
    Shared_Ptr(T *p):ptr(p),count(new int(1)){};
    Shared_Ptr(const Shared_Ptr &rhs):ptr(rhs.pt),count(rhs.count){
        (*count)++;
    }

    Shared_Ptr& operator=(const Shared_Ptr &rhs){
        (*rhs.count)++;//可以处理自赋值,要先递增引用计数,再减
        if(--(*count)==0){
            delete ptr;
            delete count;
        }
        ptr = rhs.ptr;
        count = rhs.count;

    }

    ~Shared_Ptr(){
        if(--(*count)==0){
            delete ptr;
            delete count;
        }
    }

private:
    int *count;
    T *ptr;
}