《剑指Offer》读书笔记。感谢强哥给的书。希望明年的我也可以Offer满满~
代码基本都在这里了：https://github.com/ixsim/OJ
Problems
-
class A{ static A getInstance(); void func(); private: A(); A(A& rth); ~A(); }; A A::getInstance(){ static A a; return a; } -
if(p->left||p->right){ swap(p->left,p->right); }//这样就不行 //这样就可以 if(p->left||p->right){ TreeNode *temp = p->left; p->left = p->right; p->right = temp; }看上去一样。但其实 swap两个指针。在里面操作半天。回来p的左右孩子还是没变化。
Notes
- 在C/C++中，数组作为函数的参数进行传递时，数组就自动退化为同类型的指针。
- 需要倒着再干啥的考虑【栈】
- 很多需要快速找到最大值或最小值的问题都可以用【堆】来解决
- 由于精度原因不能用等号判断两个小数是否相等。如果两个小数差的绝对值很小，就可以认为他们相等
- 我们有成熟的O(N)算法得到数组中任意第k大的数字
- 采用值传递，形参到实参会产生一次复制操作
- 题目描述一棵树--> 是不是二叉树 --> 是不是排序树
第二章 基础知识
3搜索二维数组
-
牛客的没AC。先LeetCode上找了74搜索二维矩阵，这个稍微简单点，用一个二分查找就可以。然后240题搜索二维矩阵II就是一样的了。
-
看书知道了要删减的思路后。就从右上角开始。先排除的列，又排除的行。然后继续用最笨的方法去查找（其实也是一步步排除行和列的过程）。没有考虑到：
排除 列 和 行 的过程可以同时进行，直到循环结束啊。
-
PS:我之前这种思路是错误的：
类似二分查找，先找到要搜的列，再从这一列用二分查找。这样其实有的元素存在，但并不在你要找的这一列。
4替换空格
5尾到头打印链表
用栈比较easy了.但是递归的写法注意：
//我的写法：
while(node->next!=nullptr){function递归(a,b);}
//1.递归不能用while 要用if 啊
//2.不能只看是不是最后一个节点。还要看当前节点：
if(node!=null){
if(node!=nullptr){
func();
}
}
6重建二叉树
确定递归思路后一口气撸下来，⌘ + R , 测试没问题 。提交OJ。PASS。这一周看书最爽的一次AC。
7用两个栈实现队列
虽然自己写AC了。但是方案不如书上。
我是借助stack2进行pop, 每次pop完再回传给stack1。
其实不需要的。好好考虑考虑吧！
8 旋转数组的min
看似水题。但遍历一次要O(N)
二分查找可以边O(logN)。然后还要考虑特殊情况。不可轻视
int minNumberInRotateArray(vector<int> v) {
int n = v.size();
int l = 0, r = n-1;
int m = l;
while(v[l]>=v[r]){
if(r-l==1){
m = r;
break;
}
int m = (l+r)>>1;
if(v[m]>=v[l])
l = m;
if(v[m]<=v[r])
r = m;
}
return v[m];
}
9 斐波那契
除了普通法和递归法，要注意还有O(logN)的解法。
10 二进制中1的个数
位运算。
-
1不停地执行左移。执行到首位（符号位）不就成了负的？然后再左移不就永远成了负的？
ANS: 左移不会保留符号位。右移才保留
-
位运算效率远高于乘除。尽可能得用位运算代替乘除。
第三章 高质量代码
11 快速幂
马马虎虎地过了，看了书后发现，我并没有考虑底数是特殊值的情况。（只分了指数的情况）
Note：
- 用全局变量的方式抛出异常。
12 打印1到n位最大数
不能用int型。要用string型。
13 O(1)时间内删除链表节点
题目思路简单。注意这种情况：
- 只有一个节点，要删除这个节点。
14 调整数组顺序
判断奇数偶数这回我知道用位运算了。但是请注意这个Warn：
& has lower precedence than ==;等号运算符的优先级高于&！所以要用位运算判断的与或非 记得加括号
15 链表中倒数第k个节点
-
我这个二傻子。把节点一个个存到栈里。然后出栈到第k个。AC了。
为啥不存到vector里然后用下标就能返回倒数第k个呢。
-
书上的方法，用两个指针，两个相距k，当一个走到尾的时候，另个就是答案了。
16 反转链表
先用了栈做。龙哥刚好过来。让我自己想想别用栈。我一想。哈哈。挺简单。
17 合并有序链表
我用循环写的。比较简单。Note:
18 判断是不是树的子结构
我最后AC的版本存在本地了。有这么个错误代码需要注意：
bool HasSubtree(TreeNode* p1, TreeNode* p2){
if(p1==nullptr||p2==nullptr)
return false;
if(p1->val==p2->val)
{
if(isSame(p1,p2))
return true;
else {
if(p1->left)
HasSubtree(p1->left,p2);
if(p1->right)
HasSubtree(p1->right,p2);
}
}
return false;
}
问题出现在第10行。我的想法是，如果有左子树就去走左子树。但是Debug的时候我发现，就算走到了第7行的return true, 程序也不会返回true的。因为我的第10行根本没有返回啊。只是去走一走。返回的一个true是从栈里返回到了第10行，并没有从第10行返回给main啊。
PS：这题牛客的测试用例绝对不全。
&&的短路特性
/*求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句.
解：利用&&的短路特性：如a&&b即如果a为假，b则被短路（不运算）
*/int add_fun(intn)
{ int num=0;
(n>0)&&(num=n+add_fun(n-1));
return num;
}
int main( )
{
intsum=0;
intn=100;
printf("%d\n",add_fun(n));
return0;
}
第四章 解决思路
19 二叉树的镜像
easy 秒过
20 顺时针打印
思路清晰。一次撸过。下次看看自己怎么写的就好啦。
不要二刷。
21最小栈
easy不多说
22入栈出栈次序
知道了用辅助栈的思路。比较好写。
不过，我没仔细看书上的代码。有空还是好好看一看。
23二叉树层序遍历
层序遍历就用队列嘛。easy。
24判断是不是后序遍历序列
没思路。看书吧！
看书知道了思路。过了。其中输入数组为空的情况没考虑。细心点！
25路径选择
应该是深度优先搜索。但我最近脑子不转，写递归的思路老是抽。
老是想，这个节点遍历完往回退的时候，怎么减到当前的节点。
其实在循环的最后一步把栈给POP一下就行了
26复杂链表的复制
我的思路还是很清晰的。用一个map存。Key是原链表的地址，Value是新链表的地址。这样就有了一一对应关系。看代码：
RandomListNode* Clone(RandomListNode* pHead)
{
RandomListNode *ans = new RandomListNode(-1);
RandomListNode *cur = ans;
map<RandomListNode *,RandomListNode *> map;
while(pHead!=nullptr){
if(map.find(pHead)!=map.end()){//如果有就不new了
cur->next = map[pHead];
cur = cur->next;
}else{//没有就new了 并存到map里
RandomListNode *tmp = new RandomListNode(pHead->label);
map[pHead] = tmp;
cur->next = tmp;
cur = cur->next;
}
if(pHead->random){
//寻找 map 中有没有 pHead的random
if(map.find(pHead->random)!=map.end()){//如果有就指向
cur->random = map[pHead->random];
}else{//没有就new了并存到map里
RandomListNode *tmp = new RandomListNode(pHead->random->label);
map[pHead->random] = tmp;
cur->random = tmp;
}
}
pHead = pHead->next;
}
return ans->next;
}
- 注意第20行的
if(pHead->random)之前一直过不了正是由于有的节点没有random指针，为空时自然取不到label值。以后写的时候要思考全面。
27 二叉树与双向链表
先中序遍历，存到栈里。
然后再设置左右子树就很简单了。
思路好想，关键是输入为null的特殊情况我一直没处理。导致过不了。
-
TreeNode* Convert(TreeNode* pRootOfTree) { if(pRootOfTree == nullptr) return nullptr; TreeNode* pre = nullptr; convertHelper(pRootOfTree, pre); TreeNode* res = pRootOfTree; while(res ->left) res = res ->left; return res; } void convertHelper(TreeNode* cur, TreeNode*& pre) { if(cur == nullptr) return; convertHelper(cur ->left, pre); cur ->left = pre; if(pre) pre ->right = cur; pre = cur; convertHelper(cur ->right, pre); }
28 字符串的排列
全排列嘛。我知道要用递归写。可是就是钻进了牛角尖。一时间想不出来递归的参数怎么设置。
- multiset是允许key相同的set
- 输入的string 为
“”时，要特判！
第五章 时间空间效率
29 绝对众数
-
之前刷LeetCode知道有摩尔投票法了。做起来很轻松。
当然这题不一样的就是，可能不存在。要输出0。所以我找到后，又遍历一次判断是不是真的大于 n/2 。效率还是O(N)的
-
看书的解法。快速排序。是时候去复习一下基本的排序了。撤。
-
我们有成熟的O(N)算法得到数组中任意第k大的数字--》partition()
-
刚刚用Partion解法做了一遍。
感觉穿参数的时候有点绕啊，比如找第k大的，坐标是k-1。
然后如果一趟快拍之后的坐标 i<k，说明第k大在i后面，
要传的参数就是 k-i-1;
综上，我感觉不如在数组前加一个数，放到0位置。这样第k大的数坐标就是k。其他的逻辑也清晰很多。具体是否能行我们在下一题里用一下试试
30 最小的前k个数
-
先用最low的冒泡AC过了。现在开始去查资料看高端解法~
- 我错了。我用的方法是比冒泡还low的，纯一个一个比较。
-
vector初始化要声明空间！
-
用partition的写法试试~
-
事实证明，在vector的0位置加一个垃圾数。然后整个代码写起来就特别清晰了，可以完全按照思路写出：
if(i==k) return; if(i<k){ partition(vt,i+1,jj,k-i); }else partition(vt,ii,i-1,k);如果不在0位置加垃圾数。i就要和k-1做比较，而且k-i那里要写k-i-1