对于《leetcode题解》的学习笔记。
1.编程技巧
一些常规技巧
- 在判断两个浮点数a和b是否相等时，不要用a==b，应该判断二者之差的绝对值
abs(a-b)是否小于某个阈值，例如1e-9。 - 判断一个整数是否是为奇数，用x%2！=0，不要用x%2==1，因为x可能是负数。
- 用char的值作为数组下标(例如，统计字符串中每个字符岀现的次数)，要考虑到char可能是负数。有的人考虑到了，先强制转型为 unsigned int再用作下标，这仍然是错的。正确的做法是，先强制转型为 unsigned char，再用作下标。这涉及C艹+整型提升的规则。
关于STL(C++标准模板库)使用技巧
vector和string优先于动态分配的数组
- 在性能上，由于 vector能够保证连续内存，因此一旦分配了后，它的性能跟原始数组相当。
- 如果用new，意味着你要确保后面进行了 delete，一旦忘记了，就会出现BUG，且这样需要都写一行 delete，代码不够短。
- 声明多维数组的话，只能一个一个new，用 vector的话一行代码搞定。
如下代码所示——
多维数组的声明——
int** ary = new int*[row_num];
for(int i =0; i < row_ num; ++i)
ary[i] = new int[col_num];
vector的声明——
vector<vector<int>> ary (row_num, vector <int>(col_num, 0));
使用reserve来避免不必要的重新分配
reserver函数用来给vector预分配存储区大小，即capacity的值 ，但是没有给这段内存进行初始化。reserve 的参数n是推荐预分配内存的大小，实际分配的可能等于或大于这个值，即n大于capacity的值，就会reallocate内存 capacity的值会大于或者等于n 。这样，当ector调用push_back函数使得size 超过原来的默认分配的capacity值时 避免了内存重分配开销。
2.线性表
考察线性表的操作，如数组、单链表、双向链表等。
Remove Duplicates from Sorted Array
Search in Rotated Sorted Array
二分查找算法
在计算机科学中，二分搜索（binary search）,也称对数搜索（logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
参考资料
【LeetCode】 Search in Rotated Sorted Array 在旋转有序数组中搜索
【LeetCode】 Search in Rotated Sorted Array II 在旋转有序数组中搜索之二
Search in Rotated Sorted Array I, II
二分查找（面试必备）
【二分查找法】你真的写对了吗？
二分查找法的实现和应用汇总
Median of Two Sorted Arrays
在两个有序数组中找到第k小的元素
参考资料
Longest Consecutive Sequence
参考资料
Longest Consecutive Sequence – LeetCode
Longest Consecutive Sequence 最长连续数列
Two Sum
3Sum
关于左右夹逼
多用于有序数组的求和，我们设定两个指针i丶j.一个指向数组头部，一个指向尾部。sum = nums[i] + nums[j]。这样我们只需要比较sum 与 target的情况，来移动指针，就可以快速求解。
参考资料
3Sum Closest
4Sum
Remove Element
Next Permutation
算法分析
参考资料
Permutation Sequence
算法分析
这道题可以用暴力枚举法，但由于比较费时费空间，我们可以在编程之前先找到规律，然后简化编程实现。
参考资料
Valid Sudoku
Trapping Rain Water
参考资料
Rotate Image
关键基础
对于矩阵中的各个元素的表示，如下图示例——
参考资料
Plus One
参考资料
Climbing Stairs
问题分析
斐波那契数列
- 又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）。
- 斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368……..
- 这个数列从第3项开始，每一项都等于前两项之和。