search

yuenshome / yuenshome.github.io

https://yuenshome.github.io
MIT License
85 stars 15 forks source link

sort等classic onsite problem #32

Open ysh329 opened 5 years ago

ysh329 commented 5 years ago

比较

image

image

十大经典排序算法+sort排序 http://www.mamicode.com/info-detail-2239459.html

ysh329 commented 5 years ago

MergeSort

def merge_sort(l):
    if len(l)<=1:
        return l
    mid = len(l) / 2
    left = merge_sort(l[:mid])
    right = merge_sort(l[mid:])
    return merge(left, right)

def merge(left, right):
    res = []
    i, j = 0, 0
    while i<len(left) and j<len(right):
        if left[i] < right[j]:
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1
    res += left[i:]
    res += right[j:]
    return res

if __name__ == "__main___"
    l = [4,1,8,9,2,6,5,7,3,0]
    print(l)
    print(merge_sort(l))
ysh329 commented 5 years ago

QuickSort

def quick_sort(L, low, high):
    if low>high:
        return L
    i, j = low, high
    key = L[i]
    while i<j:
        while i<j and L[j]>=key:
            j-=1
        L[i] = L[j]
        while i<j and L[i]<=key:
            i+=1
        L[j] = L[i]
    L[i] = key
    quick_sort(L, low, i-1)
    quick_sort(L, j+1, high)
    return L

if __name__ == "__main__":
    L = [9, 4, 1, 6, 5, 3, 2, 8, 7]
    print(L)
    print(quick_sort(L=L, low=0, high=len(L) - 1))
ysh329 commented 5 years ago

HeapSort

ysh329 commented 5 years ago

字符串

字符串拷贝

char *my_strcpy(char *dst, const char *src)
{
    assert(dst && src); // if(!dst || !src) return NULL;
    char *res = dst;
    while((*dst++ = *src++) != '\0');
    *dst = '\0';
    return res;
}

strcpy和memcpy都是标准C库函数，它们有下面的特点。 strcpy提供了字符串的复制。即strcpy只用于字符串复制，并且它不仅复制字符串内容之外，还会复制字符串的结束符。

已知strcpy函数的原型是：char strcpy(char dest, const char src); memcpy提供了一般内存的复制。即memcpy对于需要复制的内容没有限制，因此用途更广。 void memcpy( void dest, const void src, size_t count );

内存拷贝

void *mem_copy(void *dst, void *src, size_t len)
{
if(!dst || !src || len<=0) return NULL; // assert(src && dst && len);
char *dst_tmp = (char*)dst;
char *src_tmp = (char*)src;
while(len--)
{
*dst_tmp++ = *src_tmp++;
}
return src;
}

strcpy和memcpy主要有以下3方面的区别：

  1. 复制的内容不同。strcpy只能复制字符串，而memcpy可以复制任意内容，例如字符数组、整型、结构体、类等；
  2. 复制的方法不同。strcpy不需要指定长度，它遇到被复制字符的串结束符"\0"才结束，所以容易溢出。memcpy则是根据其第3个参数决定复制的长度；
  3. 用途不同。通常在复制字符串时用strcpy，而需要复制其他类型数据时则一般用memcpy。

字符串反转

char* reverse(const char *dst, const int len) //也可以不带返回值
{
    assert(dst); // if(!dst) return NULL;

    char tmp;
    for(int lo=0, hi=len-1; lo<hi; ++lo, --hi)
    {
        tmp = dst[lo];
        dst[lo] = dst[hi];
        dst[hi] = tmp;
    }
    return dst; //或者可以省略
}

char *reverse_tr(char *str, size_t len)
{
assert(str); // if(!str) return NULL;
char *start = str;
char *end = str + len - 1;
char  ch;
while (start < end)
{
    ch = *start;
    *start++ = *end;
    *end-- = ch;
}
return str;

}



## 字符转数字
ysh329 commented 5 years ago

permutation

#include<iostream>  
using namespace std;  
#include<assert.h>  
  
void Permutation(char* pStr, char* pBegin)  
{  
    assert(pStr && pBegin);  
  
    if(*pBegin == '\0')  
        printf("%s\n",pStr);  
    else  
    {  
        for(char* pCh = pBegin; *pCh != '\0'; pCh++)  
        {  
            swap(*pBegin,*pCh);  
            Permutation(pStr, pBegin+1);  
            swap(*pBegin,*pCh);  
        }  
    }  
}  
  
int main(void)  
{  
    char str[] = "abc";  
    Permutation(str,str);  
    return 0;  
}  
vector<string> res;

void helper(string &str, int stridx)
{
    const int str_len = static_cast<int>(str.size());
    if(str.size()==str_len-1)
    {
        res.push_back(str);
        return;
    }
    for(int sidx = stridx; sidx < str_len; ++sidx)
    {
        swap(str[sidx], str[stridx]);
        helper(str, stridx+1);
        swap(str[sidx], str[stridx]);
    }
    return;
}

vector<string> permute(string &str)
{
    if(str.empty()) return vector<string>();
    helper(str, 0);
    return res;
}

int main(int argc, char *argv[])
{
    string str = "abc";
    vector<string> res = permute(str);
    return 0;
}

性能分析

int a[10000][10000];
for(int i=0; i<10000; ++i)
    for(int j=0; j<10000; ++j)
        a[i][j] = func(i, j);

存在性能问题 容易导致栈溢出 数组是开在栈上的，涉及到编译期限制栈大小的问题。 如果申请这么大的数组是会栈溢出 二维数组也是按照像一维数组那样的存储

函数内申请的变量，数组，是在栈（stack）中申请的一段连续的空间。栈的默认大小为2M或1M，开的比较小。

全局变量，全局数组，静态数组（static）则是开在全局区（静态区）（static）。大小为2G，所以能够开的很大。

而malloc、new出的空间，则是开在堆（heap）的一段不连续的空间。理论上则是硬盘大小。

ysh329 commented 5 years ago

count 1 number of int value

int count_binary_one(long value)
{
    int MAX_BIT_NUM = 32;
    int b = 1;
    int counter = 0;
    for(int i = 0; i < MAX_BIT_NUM; ++i)
    {
        if(b & value) counter++;
        b = b << 1;
    }
    return counter;
}
class Solution {
public:
     int  NumberOf1(int n) {
         int count = 0;
         while(n)
         {
             ++count;
             n = n & (n-1);
         }
         return count;
     }
};
ysh329 commented 5 years ago

Print Binary Tree

struct TreeNode
{
    int value;
    struct TreeNode* left;
    struct TreeNode* right;
    TreeNode(int x): value(x), left(nullptr), right(nullptr){}
}

vector<int> BFS(TreeNode *p)
{
    vector<int> res;
    if(!p) return res;
    queue<TreeNode*> que;
    que.push_back(p);
    while(que.size())
    {
        TreeNode* t = que.front(); que.pop();
        res.push_back(t->value);
        if(t->left) que.push_back(t->left);
        if(t->right) que.push_back(t->right);
    }
    return res;
}

二叉树序列化与反序列化

typedef struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(nullptr), right(nullptr) {
    }
} node;
typedef TreeNode* pnode;

vector<int> buf;

// 前序遍历
void pre(pnode p){
    if(!p)
    {
        buf.push_back(0x12345);
    }
    else
    {
        buf.push_back(p->val);
        pre(p->left);
        pre(p->right);
    }
}

char* Serialize(TreeNode *p)
{
    buf.clear();
    pre(p);
    int *res = new int[buf.size()];
    for(int pidx = 0; pidx < static_cast<int>(buf.size()); ++pidx)
        res[pidx] = buf[pidx];
    return (char*)res;
}

pnode des(int& p)
{
    if(*p == 0x12345)
    {
        ++p;
        return nullptr;
    }
    pnode res = new node(*p);
    ++p;
    res -> left = des(p);
    res -> right = des(p);
    return res;
}

// 反序列化过程
TreeNode* Deserialize(char *str)
{
    int *p = (int*)str; // 读取树根
    TreeNode *pnode = des(p);
    return pnode;
}
ysh329 commented 5 years ago

Pooling

typedef struct layer
{
    float *input;
    int input_n;
    int input_c;
    int input_h;
    int input_w;

    float *output;
    int output_n;
    int output_c;
    int output_h;
    int output_w;

    // pool param
    int stride;
    int kernel_size;
    int pad_h;
    int pad_w;
} layer_t;

#define OUT_INDEX(n,c,h,w) (n)*l.output_c*l.output_h*l.output_w + \
                                      (c)*l.output_h*l.output_w + \
                                                 (h)*l.output_w + \
                                                             (w)

#define IN_INDEX(n,c,h,w)  (n)*l.input_c*l.input_h*l.input_w + \
                                     (c)*l.input_h*l.input_w + \
                                               (h)*l.input_w + \
                                                          (w)
void maxpooling_forward()
{
    int offset_h = -l.pad_h*2;
    int offset_h = -l.pad_w*2;
    int l.output_h = 

    for(int b=0; b<input_n; ++b)
    {
        for(int k=0; k<input_c; ++k)
        {
            for(int i=0; i<l.output_h; ++i)
            {
                for(int j=0; j<l.output_w; ++j)
                {
                    int out_index = OUT_INDEX(b, k, i, j);
                    float max = -FLT_MAX; // float.h
                    int max_i = -1;
                    for(int n=0; n<l.kernel_size; ++n)
                    {
                        for(int m=0; m<l.kernel_size; ++m)
                        {
                            int cur_h = offset_h + i*l.stride + n;
                            int cur_w = offset_w + j*l.stride + m;
                            int index = IN_INDEX(b, k, n, m);
                            int valid = (cur_h>=0 && cur_h<l.input_h) &&
                                        (cur_w>=0 && cur_w<l.input_w);
                            float val = (valid!=0) ? l.input[index] : -FLT_MAX;
                            int max = (val > max) ? val : max;
                            int max_i = (val > max) ? index : max_i;
                        }
                    }
                }
            }
            l.output[out_index] = max;
            l.indexes[out_index] = max_i;
        }
    }
}
ysh329 commented 5 years ago

Conv

void forward_convolutional_layer(convolutional_layer l, network net)
{
    int i, j;
    fill_cpu(l.outputs*l.batch, 0, l.output, 1);

    int m = l.n/l.groups;
    int k = l.size*l.size*l.c/l.groups;
    int n = l.out_w*l.out_h;

    for(i = 0; i < l.batch; ++i){
        for(j = 0; j < l.groups; ++j){
            float *a = l.weights + j*l.nweights/l.groups;
            float *b = net.workspace;
            float *c = l.output + (i*l.groups + j)*n*m;
            float *im =  net.input + (i*l.groups + j)*l.c/l.groups*l.h*l.w;

            if (l.size == 1) {
                b = im;
            } else {
                im2col_cpu(im, l.c/l.groups, l.h, l.w, l.size, l.stride, l.pad, b);
            }
            gemm(0,0,m,n,k,1,a,k,b,n,1,c,n);
        }
    }

    if(l.batch_normalize){
        forward_batchnorm_layer(l, net);
    } else {
        add_bias(l.output, l.biases, l.batch, l.n, l.out_h*l.out_w);
    }

    activate_array(l.output, l.outputs*l.batch, l.activation);
}

im2col

float im2col_get_pixel(float *im, int height, int width, int channels,
                        int row, int col, int channel, int pad)
{
    row -= pad;
    col -= pad;

    if (row < 0 || col < 0 ||
        row >= height || col >= width) return 0;
    return im[col + width*(row + height*channel)];
}

//From Berkeley Vision's Caffe!
//https://github.com/BVLC/caffe/blob/master/LICENSE
void im2col_cpu(float* data_im,
     int channels,  int height,  int width,
     int ksize,  int stride, int pad, float* data_col) 
{
    int c,h,w;
    int height_col = (height + 2*pad - ksize) / stride + 1;
    int width_col = (width + 2*pad - ksize) / stride + 1;

    int channels_col = channels * ksize * ksize;
    for (c = 0; c < channels_col; ++c) {
        int w_offset = c % ksize;
        int h_offset = (c / ksize) % ksize;
        int c_im = c / ksize / ksize;
        for (h = 0; h < height_col; ++h) {
            for (w = 0; w < width_col; ++w) {
                int im_row = h_offset + h * stride;
                int im_col = w_offset + w * stride;
                int col_index = (c * height_col + h) * width_col + w;
                data_col[col_index] = im2col_get_pixel(data_im, height, width, channels,
                        im_row, im_col, c_im, pad);
            }
        }
    }
}