进入某机器人所读研已经半年多了，上个学期大部分时间都是各种各样的课程（贵校的课程强度果然名不虚传），累吐血了。这学期课程少多了，也在参与一些老师课题组的工作，但发现自己对导师的方向并不是很感兴趣（自己没规划好方向的锅）。由于我本科是车辆工程的，现在打算硕士毕业去工业界（比如汽车）做汽车电子控制相关的内容（互联网卷不动，也没那实力），所以准备开始学习C++，平常刷一些leetcode相关的题目，自己动动手做些小项目。

由于很久不动C++了，所以参考了知乎上最近很火的《LeetCode 101：和你一起你轻松刷题（C++）》，题解什么的真的很详细！但是作者大大也说了不会对代码语法作讲解，作为一个小白同志，自然得去读带佬的代码了，所以我就想着拿知乎当作笔记本吧，记录一下我利用这本电子书的leetcode刷题之路，在这里我会主要介绍记录电子书上我刷的题的相关语法知识以及我的解题思路，今天是第一篇。

1.相关C++语法知识

标准库类型vector表示对象的集合，其中所有对象的类型都相同，集合中的每个对象都有与之对应的索引，索引用于访问对象。

①vector对象的定义和初始化

可以使用迭代器机制来访问vector对象的元素，迭代器也能从一个元素移动到另一个元素，有效的迭代器或者指向某个元素，或者指向容器中尾元素的下一个位置。
有迭代器的类型同时拥有返回迭代器的成员，比如这些类型都拥有名为begin和end的成员，其中begin成员负责返回指向第一个元素的迭代器，end成员负责返回指向容器“尾元素的下一个位置的迭代器”

引用是为对象起了另外一个名字，通过将声明符写成&d的形式来定义引用类型，其中d就是声明的变量名：

一般在初始化变量时，初始值会被拷贝到新建的对象中。然而定义引用时，程序把引用和它的初始值绑定在一起，而不是将初始值拷贝到引用。一旦初始化完成，引用将和它的初始值对象一直绑定在一起。因为无法零引用重新绑定到另外一个对象，因此引用必须初始化。

定义了一个引用之后，对其进行的所有操作都是在与之绑定的对象上进行的。

在掌握了该部分代码所运用的关键知识点后，开始对有疑惑的地方进行分析

注意！这里作者大大使用的是引用而不是直接定义一个vector对象，为什么要这么做呢？

这就要用到引用的特性：如果形参是引用类型，它将绑定到对象的实参上；否则，将实参的值拷贝后赋给形参。

建议大家看一看这位大佬的博客，讲的很详细！

我们就以大佬博客中的第1个和第3个例子来讲：

代码很简单：上面的代码段试图利用swap1函数实现两个变量数值的交换，但是实际输出表明并没有实现预想的结果，为什么会这样呢？我们可以看到，在上面的代码段里，swap1函数的形参并不是引用类型，那么当主程序调用子函数时，计算机是将主函数里变量a,b的值拷贝出来复制给了形参！这是因为形参和函数体内部定义的变量是局部变量，他们对函数而言是“局部”的，仅在函数的作用域内可见。当子函数开始时，函数会为形参申请存储空间，因为形参定义在函数体作用域之内，所以函数一旦终止，形参也将会被销毁。

所以在上面那个代码段里，当主程序执行到swap1(a,b);时，函数为其形参a,b申请了两块存储空间，然后将主函数里的a,b的值拷贝赋给了子函数里的a,b，但子函数里的a,b并不是主函数里的a,b，因为两组变量此时在计算机中都有自己的存储空间，所以调用子函数swap1交换的只是为其两个变量临时申请的两个存储空间里存储的值，并不是主函数里两个变量a,b的存储空间里的值，当该语句执行结束之后，子函数终止，形参也就被销毁，其之前申请的存储空间也被清理，所以最终交换失败。

而在这部分代码中，子函数swap3中的形参为引用类型，之前我们已经说过了，如果形参是引用类型，它将绑定到对象的实参上，注意，引用只是为变量添加了一个别名，它并没有属于自己的数据存储空间！因此这里当执行到语句swap3(a,b）;的时候，子函数是直接对主函数变量a,b的存储空间进行交换数值的操作的，因此在这里a,b两个变量的数据交换成功。

sort(first,last)对容器或普通数组中 [first, last) 范围内的元素进行排序，默认进行升序排序。这就是利用sort函数实现对children与cookies内的元素排序，比较简单。

分发饼干问题很简单，作者通过贪心算法实现了对饼干的分配，这里对算法的理解并不难，我在这题上遇到的困难是在语法知识上（别骂了别骂了555菜鸡一个），所以就记录下来这些知识点，如果有错误之处，欢迎大家指正！

　　　　唉！最近忙着面试找实习，然后都是面试的很多是leetcode的算法题，所以自己就刷了一遍，并且做些笔记，以后再来复习好了，悲催的大学生。。。。。

一、从（排序！）数组中删除重复项

给定一个排序数组，你需要在删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在修改输入数组并在使用 O(1) 额外空间的条件下完成。

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
 

我第一次自写的代码（因为审题不认真，写成了无序数组的删除QAQ---）：

大佬们写的示例代码（）：

自我反思：因为题目看错导致跟大佬们的代码对比反思不多所以就总结两点

1. 　刚开始刷LeetCode没有认真对待，没有审题清楚。
2.    即使是写成无序数组的删除还是没有考虑到传入参数为0和1的情况。　

二、买卖股票的最佳时机 II

好吧这次没有大佬的代码，因为那个坐标图上12ms大佬的代码实在点不出来啊，太小了，我的鼠标移动了半天都点不出来，MMP这leetcode前端程序员该不会是个傻Z吧  天哪噜！！！！

自我反思：题目要求用O(1)的原地算法，而我的是O（n）,恩，我是个菜鸡，天哪好想看看12ms那个O（1）怎么写。。。。哪位大哥好心帮我点出来评论在我博客下面呗。。。。难受QAQ

　　上面两种其实只是运用场景不同，

　　第一种：全部存入后，再去看哪一个存入次数大于1次。适用于重复数在中间或者很后面。

　　第二种：每次存入时都判断是否已经有这个数字存入了，也就是每次都查找一次。适用于重复数在比较前的场景。

　　综合的话还是觉得第一种更好。

看到这个代码的时候我都懵了，天哪你们还可以用标准库自带的sort排序。。。。。我服了！！！

以及cin.tie(0);在默认的情况下cin绑定的是cout，每次执行 << 操作符的时候都要调用flush，这样会增加IO负担。可以通过tie(0)（0表示NULL）来解除cin与cout的绑定，进一步加快执行效率。这个有刷ACM的话就比较常见。

自我反思：果然我还是太单纯了，不够狡猾！！！

这次我看到这次就想到上一题，先排序好在进行常规遍历对比，没什么好说的，大部分人没有经常刷算法题的都是我这个思维。

这位大佬数学应用的不错啊，直接就用二分计数的方法加上类似于递归的形式，不断的确定出那个单数在哪一个值的区间，然后将其返回出来

这位大佬就让我感觉到了，他这编程基础肯定无比的扎实，直接就用异或这个办法一次遍历得出答案。

异或就是只有在两个比较的位不同时其结果是1，否则结果为0。两个数相同的时候就是0了，而这组数里只有一个数字是单独出现的，全部异或完一遍剩下的那个数就是结果

自我反思：对于编程这种事，数学跟编程知识基础都是不可或缺的，像小小的位运算符有时候都会帮助我们剩下很多多余的操作。

六、两个数组的交集 II

　　刚开始看到这个题目的时候我只想出了两个办法，第一个就是上面这个---复制两个数组之后可以判断两个数组，小的那个放在外循环，当然这里没有加这个判断，因为那是进阶的内容了。

　　一个外循环数组第二个数组里面查找，找到之后存入res，为了避免二次利用那个数，直接将第二个数组数（反正也是拷贝的数组，可以直接在上面进行操作）删除,最后返回的就是两个数组的交集了

这就是我第二个想法，用map来存储，不过呢，他是用unordered_map底层是hash，查找方面速度会有一些优势。

　　这个就是进阶里面将数组排序之后在去寻找两个数组的交集，这里两个数组排序完之后没有什么好探讨的，就是使用类似双指针的形式去不断遍历两个数组找到交集存储

自我反思：进阶里面的三没有怎么去思考，不过我想无非就是分段读取吧。

　　这题无非就是两种情况一种是末尾加一不会大于10的，就直接末尾加一返回数组就行了。

还有一种就是999，或者9999这种全是9的情况，加一的话要不断的进位，那么问题就转化成了如何在这个数组前面加一个1上去。

所以我这里用逆序补1后在逆序回来。

　　大佬们比我分析的好，我没有想到这题数组值全是0的情况恰好可以直接使用resize来改变内存，resize改变后的数组默认全部初始化为0，恰好这题就是，只要把第一个0改成1就行了。

自我反思：对STL容器的各种方法和使用场景还没有很好的掌握。

　　我的思路就是遇到0就将其删除然后补充在最后，这样的逻辑虽然简单，但是依靠vector函数来操作的话内部其实要做许许多多的事，导致时间很慢。

　　大佬的思路就是快慢指针，一个指针也就是for循环正常遍历，而另外一个指针就不断的先找到0的位置停止下来，等到for循环到了0后面的位置并且是有效值，就将他们交换。

　　说白了就是将0后最近的非0数与其交换，不过这样的换法，从全局上看就是不断的把每个0往末尾移动，移动的次数非常多。

　　这个代码就跟16ms那个代码不一样的思路，不是将0不断的往后搬了。而是将有效的数字都提到前面来，然后用i记住有效数字的最后一位在哪，之后空间的全部一次性置为0。

两种方法，一种常规遍历，一种hash存储

　　上面这种就是常规的遍历，没什么好说的。

　　这里还是用unordered_map容器来存储查找，因为要返回的是下标。所以先将所有的值作为键，下标作为值存入容器。然后就是遍历，因为两数之和为target，那么已经知道一个值为Nums[i]，那另外一个值就是target - nums[i]。

　　然后这里使用unodered_map而不是map，因为本题不需要存入有序序列，并且本题有频繁的查找工作，unodered_map底层为hash查找比红黑树更快。

 十、有效的数独

　　我的思路很简单，就是分别计算每一行每一列是否有重复，然后对于，判断每个九宫格是否有重复我则是采用一个二维数组来存储，看图可以划分为9个九宫格，我每次存储横向的三个九宫格然后进行判断里面是否出现重复。

　　然后跳到下三个个横向九宫格的时候，将数组清空在次存入判断

　　大佬则是采用创建三个标记空间的形式，把所有的数据用点亮标记的形式来判断，比如if（col[j][val]）就是判断j列里val是否已经点亮为1，如果已经为1那么说明这列里面已经存在一个val值，那么就重复了。行也是这样类推。

　　然后就是判断九个九宫格内是否重复，也是将九宫格划分好，比如sq[i/3][j/3][val]=1;这就是第i行的第j个九宫格中的val元素点亮置为1.。i除以3是因为i值为0-3之间就是第一行的某个九宫格，3-6则是第二行的某个九宫格。。。。j的意思也这样理解

　　这个大佬应该是有刷过ACM之类的，跟上一个12ms的思路其实差不多，就是对内存各方面做了优化，用bitset来存储数据，bitset就像一个bool类型的数组一样，但是有空间优化——bitset中的一个元素一般只占1 bit，相当于一个char元素所占空间的八分之一。