C++数据结构和算法 01

首先开篇先来一道入门题：

给了一个接口定义，尝试实现：  Memmove

void *memmove(void *dest,const void *src,size_t n)
{
}

这个函数呢是想从内存中一块内容从src拷贝到dest ，固定长度是n，实现代码

要注意常见的陷阱有以下几种（是时候重温一下C++的课程了/(ㄒoㄒ)/~~）

1. 内存重叠的处理
2. 临时变量太对或者没有安全释放
3. 没有测试内存越界
4. 指针操作不熟悉 

好啦下面是有问题的代码 ：

void *memmove(void *dest,const void *src,size_t n)
{
    char *p1=dest;
    char *p2=src;
    while(*p2!=\0)
        *p1++=*p2++;
    return p1;
}

万事开头慢嘛，开始会很慢，先分析一下存在的问题：

内存重叠问题

（1） 有可能dest就是在src内存之内，那就导致了内存重叠；

（2）有可能dest在src前面，非内存重叠；

（3） 有可能dest在src后面，非内存重叠；

所以说，其实我一开始想到的就是dest 在 src 后面，然后通过循环赋值 把src内容赋值给dest，这的确是思维漏洞了，想的不够全面，的确有可能src的三个值里面就有dest 

学习一下正确的写法：

void *memmove (void *dest,const void *src,size_t n)
{
    char *p1=dest;
    const char *p2=src;//对应上
    //判断了 p1 和 p2 的位置关系
    if(p2//出现了内存重叠情况
    {
        p2+=n;//把p2支到了n+1的位置
        p1+=n;//把p1支到了不在p2内的位置
        while(n--!=0)//通过倒过来的方法，从后往前赋值
            *--p1=*--p2;
    }
    else//没有出现重叠情况
    {
        while(n--!=0)//正常顺序赋值
            *p1++=*p2++;
    }
    return p1;
}

 大概意思我画了个草图，方便我各个理解。

---

接下来呢记录一下一个二叉树的点

                4                                                           4   

             /     \                                                      /     \

         2            7                  =====>>>            7       2

        /  \          /  \                                             / \       / \

     1     3      6    9                                         9   6    3   1

如图，就是把上面二叉树的顺序调换

/**
* Definition for a binary tree node.
* struct TreeNode{
*   int val;
*   TreeNode *left;
*   TreeNode *right;
*   TreeNode(int x),left(NULL),right(NULL){}
* };
*/
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL)
            return NULL;
        TreeNode* tmpNode=root->left;
        root->left = invertTree(root->right);
        root->right = invertTree(tmpNode);
        return root;
    }
};

分析代码：注释部分就是定义一个树，判断树是否为空，不为空就把树左子树和右子树互换

有时候其实多看几遍我也能看懂代码的大概意思，我是觉得在精不在多，这么多次都没坚持下去就是因为总觉的得刷量，但是质量没有保障，忘了就跟没学过一样。加油吧

---

排列组合模板

1、全排列：就是所有排列顺序都显示出来 n个字符应该是有n!个结果

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);
        }
    }
}

2、组合：对于每个元素，可以有选和不选两个状态。 

---

这是我在b站上听的课，感兴趣的可以去看看，一起学习~

---

《《 数组和字符串 》》

入门题：有这么一个 strStr C语言的一个函数库，想在source里面寻找target，如果找到了返回第一次出现的位置，如果不存在返回 -1 。这是一个字符串匹配的问题。

首先介绍暴力算法（Brute-Force)

顺序的遍历母串，然后将每个字符作为匹配的起始字符，判断是否匹配子串。

时间复杂度是 O(m*n)

char* strStr(const char* str, const char* target)
{
    if (!*target) //判断target是否为空
    {
        return str;
    }
    char* p1 = (char*)str;
    while (*p1)
    {
        char* p1Begin = p1, * p2 = (char*)target;
        while (*p1 && *p2 && *p1 == *p2)
        {
            p1++;
            p2++;
        }
        if (!*p2)
        {
            return p1Begin;//临时存储p1位置
        }
        p1 = p1Begin + 1;
    }
    return NULL;
}