《剑指offer》解题笔记
《剑指offer》共50题，这两周使用C++花时间做了一遍，谨在此把一些非常巧妙的方法、写代码遇到的难点、易犯错的细节等做一个简单的标注，但不会太过具体。具体算法还是请參考书本。
做的比較急，代码还有非常多不完好的地方，如有错误。欢迎改正，地址为：github:sword_of_offer。
能够使用git命令获代替码。
clone https://github.com/heLomaN/sword_of_offer.git
当中，少数无法验证正确与否的题目没有写代码，部分二叉树的题目写了代码，但因为生成二叉树太过麻烦没有验证。
解题笔记
Q3
声明并初始化二维数组的语句怎样写？
cin怎样推断输入结束？
Q4
字符数组的末尾位置计算差了1，忘了加上\0。要小心
Q5
递归的方法更简洁
Q6
stl的find算法
vector传值性能差，应该用引用
截取一段时要依据左右子树的长度来截，再次find是错误的
Q7
stack的pop返回值是void。而top方法才返回顶部值
Q8
这个二分相当的难。
尤其是非递归的写法
边界值处理要细致想
不能忽略如1 0 1的特殊情况
Q9
应该用long long类型
Q10
求数的二进制表示种1的个数应记住：减1再&自身总会消去一个1
Q11
除以2用>>，模2用&，效率更高
应该加上错误检測
Q12
遇到数字有关的题，首先考虑是不是大数问题
Q13
把下一个节点的值复制到当前节点就可以。之后删除下一个节点
Q14
9du oj要求奇数或偶数的顺序不变。如今的代码没有符合这个要求
Q15
node *p,q仅仅把p声明为指针。小心
參考https://github.com/julycoding/The-Art-Of-Programming-By-July，*应该靠近类型名
Q16
绘图以帮助理解
Q18
!p推断指针为空是能够的
代码未測试
Q22
方法非常难想起来，要细致分析当中规律
Q25
代码未測试
Q26
方法非常难想起来 第三步分离链表操作不够简洁
Q27
使用了一个辅助vector，书上的方法不能细致的写出来
Q28
这样的解法无法处理多个字符反复的情况。会造成反复
递归的时候改动全局数组，但递归调用后要把全局数组改动回来，和之前递归调用前后出入栈的方法有异曲同工之妙
8皇后问题也能够用这种方法解决
Q29
求数组中随意第K大的数字有成熟的O(n)的算法
Q30
C++中throw new excetion("error")是不对的，不能用字符串初始化excetion
set和multiset是基于红黑树实现的
Q31
第一种解法和DP解法原理是一样的
Q32
1到n个9之间出现1的次数是n*10^(n-1)
代码未測试
Q33
itoa不是标准库函数，仅仅是linux下的库函数。能够用printf取代
string能够直接+、>、<运算
Q34
关键是怎样保证已经找到的丑数数组是有序的
Q35
memset函数是在cstring头文件里
Q35
关键是merge两个数组时的细节处理
归并排序相当于O(n)的空间换来了时间复杂度提升到O(nlogn)
Q37
代码未測试
Q38
关键是改变二分查找的循环推断条件
Q39
题目2的算法不易想起
代码未測试
Q40
方法非常巧妙
C++中auto& e : v遍历容器注意v指向元素的引用才干够改变容器中的值
Q41
书中未给出算法证明，亟待解决
Q43
方法巧妙。解法非常难想起来
Q45
方法巧妙，解法非常难想起来
Q50
假设有指向父节点的指针，那么找到这两个点到根节点的链表，求第一个公共节点
假设没有，那么dfs遍历得到这两个点的链表，求第一个公共节点
转载请注明作者：Focustc，博客地址为http://blog.csdn.net/caozhk，原文链接为点击打开