用leetcode刷题对stl效率的感性认识。期望证实即使对stl（或某些c++特性）即使在不熟练的应用下也和裸写c没有性能代差（就是有差距也是小系数线性的），后面的文章会用string源码为例剖析下stl的实现细节和性能，而本文只是个简单的事实堆砌。
ps：stl网上有不少说法，这里就取standard template library的本意，用模板实现的那部分容器算法迭代器和各种trait都算，string也算，因为string也是基于模板的。
说明：
1.leetcode测试比较完备方便，即改即传即比；
2.刷leetcode的有不少有志之士，得到的效率分布数据相对靠谱；
3.刷的全是leetcode中easy的题，因为本文目的不是看算法效率，而是看代码优化效率；
4.是一口气全写完后，string源码看完后再写的博客，所以知道的有烂的地方没有改，因为目的是希望得到stl实现和纯c实现没有代差；
5.以前也做过不多的leetcode，和同学一起刷，发生过leetcode说某个代码效率低但一起分析和自测后发现该代码更优的情况，所以leetcode的结果是作参考用的；
6.到写的时候发现......!!!不同语言的效率对比没有了！！！好吧，和c++最优的比估计和c最优解比差不多，毕竟前者对后者的完全兼容。
415. Add Strings
题意：字符串模拟大数相加；string addStrings(string num1, string num2)；
思路：
1.如果num2比num1长，swap二者，从而保证num1不比num2短；
2.num1和num2都和string("0")相加，string("0") + num1，从而进位不用特殊处理;
3.用std::transform，遍历num1和num2,把结果写回num1。加操作用lamda函数，进位与否用函数局部变量up表示；
4.最后看第一位是否进位（为1?），不是就把0给剪掉。
可能的败笔：
1.和string("0")相加导致string总体向后移位；
效率对比：
前85%，比最优速度差25%，如果在自己的实际工作中无论何时都可以忽略不计。
121. Best Time to Buy and Sell Stock
题意：int maxProfit(vector<int>& prices)；对于prices，找到prices[j] - prices[i]的最大值，其中i<=j；
思路：
1.从数组第一个元素开始遍历数组，找到局部最高最低点push_back到一个新数组，比如76543212321，那么从7开始一路下降到的1就是一个最低点,再往后一路上升到的3是最高点；
2.呵呵，从第一个元素开始遍历暴力破解...，std::max_element查找之后的最大元素与当前元素做差值。
可能的败笔：
1.暴力破解...
效率对比：
前35%，比最优速度差25%，实际工作中忽略不计即可。
202. Happy Number
题意：“开心数”这种数要么能够循环回某个非开心数循环，要么就各位数平方和为1。
思路：
1.用set<int>存已经开心过的数，如果某一步循环回开心过的数，那么返回false。
败笔：
1.求各位数平方和说不定有啥非除10求余再相加的解法，比如构造一个array存储；
效率对比：
前98%，但是存在0ms的解，实际工作中如果此步骤重要且重复需要进一步查找深究。不过这个效率差距大概率在算法。
326. Power of Three
题意：检查一个数是否是3的某次方；bool isPowerOfThree(int n)。
思路：
1.暴力破解，3一直乘下去直到大于等于该数n；
2.注意数据溢出；
3.对于int可以取中位的数，如果大于该数，从该数开始乘；
败笔：
1.int想当然认为是32位并且闯对了，可以用static_cast<unsigned int>(-1) / 2或者climits下面的INT_MAX；
效率对比：
前百分之80,这个倒和stl无关。
231. Power of Two
题意：检查一个数是否是2的某次方；bool isPowerOfTwo(int n)；
思路：
1.2每次乘方从位角度看是唯一的置位左移一位；
2.bitset<64>(n).count() == 1。
败笔：
暂无。
效率对比：
前百分之100。
83. Remove Duplicates from Sorted List
题意：从排序链表中删除重复结点；ListNode* deleteDuplicates(ListNode* head)；
思路：
1.注意各种情况的边界条件；
2.delete结点；
败笔：
1.可以尝试定义class lnIter{ListNode * ln;}，重载lnIter的前置++操作符和*、==，再用std::unique把重复的移动到链表最后，在手动删除或者remove_if。实现细节不少，但是std::unique保证无bug。
效率对比：
前百分之75，比最快的慢25%，实际工作可以忽略。
35. Search Insert Position
题意：int searchInsert(vector<int>& nums, int target)；对于给定排好序的数组nums，找到最后一个不大于等于target的nums中数的下标；
思路：
1.return std::lower_bound(nums.cbegin(),nums.cend(),target) - nums.cbegin();用lower_bound找到下标；
败笔：
想不到。
效率对比：
前百分之百。
70. Climbing Stairs
题意：爬梯子；int climbStairs(int n)；其实是对于n，找到一个数列1 2 1 1 2 1......只能有2或者1,并且数列之和为n，问这种组合的个数；
思路：
1.只能想到递归了，对于偶数的n = 2m，对第m阶台阶来说，有刚好走到m阶和走过m阶走到m+1阶两种情况：对于刚好走到m阶的情况，下一次不能走一步，因为走1步就会走到m+1阶，那么和情况2重复了，所以情况1有climbStairs(m) * climbStairs(m - 2)种走法；刚好走到m+1阶的情况2有climbStairs(m+1) * climbStairs(m-1)种走法；情况1和2之和就可以递归；
败笔：
1.非递归解法，需要查证。
效率对比：
前百分之100,不过此题和stl无关。
437. Path Sum III
题意：int pathSum(TreeNode* root, int sum)；找到二叉树结点和等于sum的所有路径数量和；
思路：
1.递归，但是写得很麻烦，无法总结思路；
2.set<pair<TreeNode*,int>> tSet，用一个set来存储遍历过的结点和到该结点的当前数之和的二元组；
败笔：
1.此题
效率对比：
前百分之一，效率比最好的差了十倍。但是估计是算法差距。
53. Maximum Subarray
题意：int maxSubArray(vector<int>& nums)；求最大连续子序列和；
思路：
1.先斩头去尾，把头尾的负数或0全部掉；
2.从vector最后一位开始向前加一直到前一位是负数，把和tempSum按情况赋值给max，再把tempSum往前加一直加到下一位是正数，如果tempSum此时是正数则加入下一回合计算，否则tempSum清0；
3.返回tempSum。
败笔：
1.可以从第一位开始加，并且可以用find和accumlate计算。
效率对比：
前百分之百。
191. Number of 1 Bits
题意：int hammingWeight(uint32_t n)；返回n二进制1的数量；
思路：
1.bitset<64>(n).count()；
败笔：
1.可以用查表方式逐字节试试；也许还有某种位运算玩法；
效率对比：
前百分之5,效率是最快解法三分之一，如果实际工作这里不是关键重复处，可以接受，毕竟写法优雅呵呵。
263. Ugly Number
题意：bool isUgly(int num)；如果一个数只能被2 3 5整除，那么num就是丑陋数；
思路：
1.除2一直到余数为0,再除3,除5,如果剩下1,那么就是丑陋的；
败笔：
1.暴力破解，可以尝试用素数去除；
效率对比：
前百分之35,是最好效率的一半，效率可接受，但解法太丑。
217. Contains Duplicate
题意：bool containsDuplicate(vector<int>& nums)；数组中是否有重复数；
思路：
1.std::set<int> numSet，通过insert判断是否insert成功；
败笔：
1.unordered_multiset，哈希表应该更好；哈希表大小和哈系函数优化；这道题后面值得深入；
效率：
前百分之80,比最快慢了10%。
206. Reverse Linked List
题意：ListNode* reverseList(ListNode* head)；反转链表；
思路：
1.直接反转；
败笔：
1.和unique要求的ForwardIterator不同，std::reverse需要双向迭代器，封装ListNode *调用stl恐怕不行；
效率：
前百分之85,比最快慢33%,但是和stl无关。
350. Intersection of Two Arrays II
题意：vector<int> intersect(vector<int>& nums1, vector<int>& nums2)，求nums1和nums2的交集；
思路：
1.先sort重新排序两个数组，再std::set_intersection求交集；
败笔：
效率：
前百分之百，也证明了stl的高效。
551. Student Attendance Record I
题意：bool checkRecord(string s)，如果字符串多余一个A，或者有两个以上连续的L，返回false；
思路：
1.用find_first_not_of分析出现A或者L的具体情况；
败笔：
效率：
前百分之100。
268. Missing Number
题意：int missingNumber(vector<int>& nums)，nums含有0-n，n+1个数中的n个，找出少的那个数；
思路：
1.std::accumlate求和，再用公式求0-n的总和，返回差值；
败笔：
效率：
前百分之50,比最快慢五分之一。
541. Reverse String II
题意：string reverseStr(string s, int k)，s按照k，先反转k个，再跳过k个。
思路：
1.用std::reverse；
败笔：
1.应该使用string自带的reverse，std不会比string更懂自己；
效率：
前百分之百。
543. Diameter of Binary Tree
题意：int diameterOfBinaryTree(TreeNode* root)，求二叉树相差最远的两个结点距离；
思路：
1.递归，int findMax(TreeNode *root)，返回树的最大深度，二叉树的周长等于左右子树深度之和，在求左右子树最大深度的同时更新周长；
效率：
前百分之40,比最快的慢三倍，此题和stl无关。
371. Sum of Two Integers
题意：求两个整数之和，不能用+-号；int getSum(int a, int b)；
思路：
1.用个intWrapper，定义一个减法操作实际执行加法，int到intWrapper的构造函数，intWrapper到int的隐式转化；
败笔：
1.可以看下编译结果看是否最终代码没有调用任何函数；
效率：
前百分之40，尽管和stl无关，知识相通。
258. Add Digits
题意：返回数字各位数字之和，直到之和为各位数为止；
思路：
1.递归调用；
2.每一次递归，用to_string把int转换为string，再调用accumulate相加，再减去'0'*str.length()；
效率：
前百分之65,比最快慢一倍。
283. Move Zeroes
题意：void moveZeroes(vector<int>& nums)，把nums中的0移到最后，其他的相对位置不变；
思路：
1.建议一个和nums等长初始值为0的数组；
2.copy_if拷贝；
效率：
前百分之90,额，其实此题要求不能拷贝数组，呵呵。
530. Minimum Absolute Difference in BST
题意：求二叉搜索树中两个相邻node的最大差值；相邻的node B是比当前node A大或者等于的第一个数；
思路：
1.遍历二叉树得到所有的数，sort，transform得到相邻数字差数组，再用min_element找到最小差值返回。
效率：
前百分之50,比最快慢25%。
506. Relative Ranks
题意：vector<string> findRelativeRanks(vector<int>& nums)，求nums前三大的数；
思路：
1.std::sort，再遍历nums，用std::lower_bound找num对应的rank；
效率：
前百分之60。
时间紧张，下面的就写效率了。
167. Two Sum II - Input array is sorted
80%。
383. Ransom Note
先统计note中的字符频率，再find_if。
60%。
349. Intersection of Two Arrays
和350比起来多一个unique和resize。
100%。
453. Minimum Moves to Equal Array Elements
一个move等价于一个数减1。先min_element求到最小值min，再遍历求差值之和。
可以accumulate求和再求差值。
5%,比最快的慢60%。
455. Assign Cookies
80%。
387. First Unique Character in a String
用一个int cCount[26]计数。
90%。
100. Same Tree
遍历树，用字符串作为遍历的路线图，比如7l8m9r，前序遍历，7左子树结点（l），最后比较路线图字符串是否相同。路线图相同==数相同，需要证明。
65%。
237. Delete Node in a Linked List
85%。
169. Majority Element
先sort排序，返回nums[nums.size()/2]。
60%。慢30%。
409. Longest Palindrome
85%,慢一倍。
504. Base 7
10%，慢三倍。
242. Valid Anagram
先sort，再==比较。
其实统计字符数就可以了。
3%，慢4倍。
389. Find the Difference
accumlate之后求差值，需要注意溢出。
70%。
508. Most Frequent Subtree Sum
50%，和stl无关。
448. Find All Numbers Disappeared in an Array
std::iota填充满一个1-n 的数组，在sort源数组，再set_difference求得差集。
30%，慢50%。
520. Detect Capital
用any_of和find_if。
75%。
136. Single Number
75%。
442. Find All Duplicates in an Array
20%，和stl无关。
485. Max Consecutive Ones
for_each,lamda函数，加局部变量。
30%，慢25%。
406. Queue Reconstruction by Height
8%，和stl无关。
463. Island Perimeter
70%，和stl无关。
344. Reverse String
直接调std::reverse。
应该调string::reverse。
30%，慢80%。
412. Fizz Buzz
generate_n和lamda函数生成。
80%。
500. Keyboard Row
用到了find_if。
70%。
557. Reverse Words in a String III
用到了istringstream和reverse。
50%,慢40%。
461. Hamming Distance
40%，和c++新特性无关。
最后，从这些例子，我自己得到初步结论，使用stl不熟练时应该根据使用场景来测试代码性能选择是否使用；熟练使用后可以减少测试工作，通过分析来看是否用stl。一般来说，直接用，stl没bug，文档清晰，抛异常规范，接口通用，功能全面，这是优点；源码晦涩，不知道在干什么，这是不足（代码不易读，知乎和stackoverflow不少人都这么说，《stl源码剖析》头一章也显而易见）；写stl的人是业界最牛的人，他们的代码可以放心使用，如果不好用，那说不定是自己用不好，这也是优点。
