《剑指offer》刷题代码 -2019.6.25
- 个人刷剑指offer书的代码仓库，可能有错和不完善的地方，努力改进
- C++语言，Xcode编辑器
- 实现方法，测试用例可能不全面，慢慢完善
- 参考内容：原书作者代码, 网上大佬整理多种方法
| 日期 | 题目 | 算法内容 | C++学习 |
|---|---|---|---|
| --- | --- | 第2章. 基础数据结构 | --- |
| 6.25 | 03 | 数组 | |
| 6.29 | 04;05 | 数组;字符串 | C++的几个输入用法 |
| 6.30 | 06 | 链表/栈 | 结构体中.和 ->的区别 |
| 7.1 | 07;08;09 | 二叉树;代码参考; 队列，栈 | 先序，中序，后序遍历;模板类写法，cin输入 |
| 7.2 | 10 | 递归 | |
| 7.3 | 11 ,12,13,14 | 二分查找(11);回溯(12,13) ;动态规划(14) | ;数组; |
| 7.4 | 15 | 位运算(15) | 逻辑操作 |
| --- | --- | 第3章. 高质量代码（全面考虑情况） | --- |
| 7.5 | 16 | Power()函数(16) | 考虑多种情况 |
| 7.6 | 17 | Print_Max_Number(17) | 字符串表示整数 |
| 7.7 | 18,20,21 | 链表操作(18_List_Operation);字符串和数字(20_String_Number);数组,向量,双指针(21_ReOrder_Array) | 输入，字符串操作;双指针,向量 |
| 7.8 | 22,23,24,25,26 | 连续的链表操作练习：22_Find_Kth_Node_From_End,23_EntryNode_List,24_Reverse_List,25_MergeList. 树的递归操作：26_SubTree | 链表的构建，结构体，指针问题 |
| 7.9 | 27,28 | 树的操作问题：27_镜像树,28_对称树 树的遍历;递归和循环 | 指针 |
| 7.10 | 29 | 顺时针打印数组 | 二维数组传参；画图理清思路 |
| 7.11 | 30,31 | 栈的出栈入栈操作问题：30_栈中最小元素,31_栈的压入弹出顺序 | 类，模板，向量和数组，指针传递，const |
| 7.12 | 32,33 | 树的遍历，结合栈/队列：32_层序遍历,33_二叉排序树的后序遍历 | 向量，递归 |
| 7.13 | 34 | 树的遍历，34_Path_in_Tree | 树遍历，递归 |
| 7.17 | 35，36 | 链表：35_Complex_List；36_Tree_Convert_List | map和哈希map的使用; |
| 7.18 | 37，38 | 树：37_序列化，38_字符串，递归 | 输入输出流，对文件操作; 字符串，递归，向量 |
| 7.19 | 39,40,42,43(未全实现) | 39_出现超过一半的数,40_最小的k个数,43_最大连续子数组和,43_1的个数 | Partition函数，思路问题，向量/数组，map的使用；容器set,迭代器，最大堆，红黑树结构；递归，贪心；观察数字规律 |
| 7.21 | 44,45,46 | 数字序列的某一位,45_数组最小数,46_数组to字符串 | 循环；排序，比较规则；字符串，递归/循环，动态规划 |
| 7.22 | 47 | 47_数组最大路径值 | DP,矩阵 |
| 7.23 | 48,49,50 | 48_最长不含重复字符的字符串,49_丑数,50_第一个出现一次的字符 | string,动态规划；数组，规律；字符串，哈希表 |
| 7.24 | 51,52 | 51_逆序对,52_两个链表第一个公共节点 | 数组/向量，归并；链表，栈，树 |
| 7.25 | 53,54,55 | 53_二分法查找各种变形,54_二叉搜索树第k大个节点, 55_判断是否平衡二叉树 | 二分查找，数组；BST,中序遍历；递归，后序遍历思路 |
| 7.26 | 56 | 56_数组中数字出现次数 | 异或运算，拆分 |
| 7.27 | 57,58 | 57_和为s的数字,58_字符串翻转 | 数组，双指针，逻辑；字符串多次翻转问题，cin，指针操作 |
| 7.28 | 59,60(未懂),61,62,63 | 59_滑动窗口和队列的最大值,60_n个骰子的点数和,61_扑克牌顺序,62_圆圈中剩下的数字(约瑟夫环),63_股票最大值 | 队列,分析能力，模板，向量，构造类;动态规划，递归；抽象数组；list环形链表抽象，公式法；数组，DP方法 |
| 7.30 | 64,65,66 | 64_不用循环求1+..+n,65_位运算做加法,66_数组相乘 | 考察全面：递归，构造，指针；理解位运算;数组运算，逻辑 |
- 数组，字符串，链表，树，栈与队列，递归/循环，查找排序，回溯，动态规划/贪心，位运算
- 对这些基础数据结构和算法要了熟于心，清清楚楚
- 04-05题：
- 06题学习： -2019.6.30
- C++基础：结构体 .和 ->的区别,结构的表达式用 .，结构体的指针用 ->。
- 算法：链表list：参考1，参考2
- 08题学习： — 2019.7.1
- 09题学习： - 2019.7.1
- 栈，对列的实现和熟悉，用栈实现队列操作
- 有时间实现一些用队列实现栈
- 参考原书代码，好好写成模板类
- cin连续输入的问题，while(cin >> a)终止条件：文件终止符（ctrl+D/ctrl+Z）;非法输入（要求int，输入其他）。cin终止参考
- 11题学习 - 2019.7.3
- 二分法比较了解，其中有当首尾和mid三者指针值相等的时候，只能用顺序查找，这点逻辑要注意
- 12题总结 - 2019.7.3
- 回溯法：适用每步有多个选项的问题，不断递归实现，不行返回上一步继续递归下去；比如二维矩阵找路径，人在二维方格运动这种问题。
- 今天对回溯的理解还不够， 代码基本是参考原书代码,加深理解如何理解拆分问题，如何递归遍历每步的选项
- 同时对C++基础比如数组，字符串的有要求，包括边界条件和遍历rows,cols的完整性，要多看这个代码.
- 14题总结 - 2019.7.3
- 动态规划和贪心策略：主要要明白动态规划的适应问题范围；同时明白自上而下分析和自下而上实现
- 对贪心算法有些不太清楚，需要看怎么用，以及贪婪策略如何选取
-
- 14题中，有时间再回过来练习一下，怎么把对应最大值的cut方法记录下来。
- 15题总结 - 2019.7.4
- 位运算的5种运算：&,|,^,<<,>>.(与，或，异或，左移，右移)。
- 每个整数都是以二进制存储，需要操作二进制时，可以直接对整数进行运算，即使运算二进制。
- 一个很好的思路：把整数减1再和原来的整数做&运算，得到的结果相当于把整数二进制表示中最右边的一位1变成0
- 规范性：书写，布局，命名
- 完整性：实现基本功能 -> 考虑边界条件 -> 错误输入处理
- 鲁棒性：防御性编程（考虑可能错误的情况）， 问题全面性， 无效输入/数据的处理
- 16题总结 - 2019.7.5
- 这是个看起来简单的题目，Power乘积函数，如果不看作者内容我肯定错误很多.
- 写代码注意特殊情况区分。比如这个题目里面指数为负数时，以及出现分母做负数的情况讨论.
- 还有个小点要注意:浮点数不能用==判断相等，要编写equal(float a, float b)函数判断.
- 书中作者有对时间优化，很好的点：位运算和新的计算power公式，使得时间复杂度为O(logn).
- 17题 - 2019.7.6
- 用字符串存储多位数字，可以表示很大数，避免溢出
- 这一题考察了完整性，多种条件，需要对多种情况讨论
- 多看这个代码，里面有很多小细节问题
- 第二种方法用了递归，有些迷迷糊糊，没事多看这个代码多理解递归用法思路
- 18,20题 - 2019.7.7
- 18题有两个，是对链表的基本操作熟悉，没什么问题
- 20题考察字符串和数字的表示，需要判断的情况很多，思考要清晰。
- 20题同时有字符串输入存储问题，需要想个更好的办法。
- 21题 - 2019.7.7
- 奇偶重排，借鉴了两种方法，一个稳定一个不稳定，了解一下。
- 同时用到了对向量的操作，很爽，注意向量迭代器的使用。
- 链表问题大集合 -2019.7.8
- 1.这几个问题集中对链表进行操作，对链表差不多清楚了，包括结构，创建，遍历。最重要理清楚链表中指针的关系，操作过程不要断链。
- 2.这几个链表操作有些方法：双指针，递归
- 3.同时这里考察的是高质量代码，就是考察全面，情况考虑清晰，不同的输入，边界条件。链表最多的就是空指针和不要断链。
- 22_Find_Kth_Node_From_End：双指针的使用;不同情况的考虑：空指针，不同的k值。
- 23_EntryNode_List：双指针使用;函数功能分块
- 24_Reverse_List：全面性考虑(头指针是nullptr,链表只有一个节点)；注意过程不要断链
- 25_MergeList：注意指针不要断链；特殊输入(空指针问题);递归方法解决.
- 24_SubTree - 2019.7.8
- 树的问题，这题参考写了树节点的操作
- 树的问题除了遍历这种，一般就用递归解决。
- 画图 ：二叉树，二维数组，链表
- 举例
- 分解：分治-递归，动态规划
- 27,28_Tree - 2019.7.9
- 两个数的问题，镜像和对称，和树的遍历很相关，要对前序中序后序遍历烂熟于心。
- 同时都有递归和非递归的解法，树的问题一般都用递归，非递归要多画图分析，主要是节点的关系，多借助栈。
- 多看这两个，对递归和非递归解法清楚，更要清楚树遍历的非递归方法
- 29_顺时针打印数组 - 2019.7.10
- 之前写过，每次都是很迷糊，说明对边界对判断都很迷糊，这次完全是参考作者的.
- c++二维数组输入问题，如何把二维数组作为参数，无非是指针和new空间的问题.(想一下这个题怎么改成vector,然后笔试的时候怎么进行输入)
- 二维向量的操作不太清晰明白，一写这样比较烦的题思路还是不够清晰
- 两个题都是对栈操作的使用，入栈出栈顺序，操作要烂熟，31题那个逻辑对比要清楚，拿过来问题要会模拟。
- 30题中的类要写成模板类啊，还有const参数要继续弄明白啊
- 31题中明确向量和数组的区别，后序再刷改成传入指针；
- 31题并不是特别清晰，手到擒来，如果自己写的话可能又会对一些细节犹豫，多看多理解。写题时的参考
- 32_从上到下打印二叉树 - 2019.7.12
- 连续三个问题关于树的层序遍历，借助栈/队列实现遍历。着重在和栈/队列的结合
- 第三个子问题中，奇偶压栈和出栈的顺序要清楚，想明白这个逻辑很重要。
- DFS遍历问题，不论是树还是图，基本都可借助栈实现。
- 33_二叉搜索树的后序遍历序列 - 2019.7.12
- 首先拿到这个题就迷糊害怕，难道要把所有后序子序列都弄出来对比，肯定不是这样
- 解法是先根据二叉搜索树后序特点（最后一个为root），找到根节点；然后划分为左右子树（比root小的为左，大的右）；最后对左右子树递归
- 同时注意，用了数组和向量两种，借鉴了网上的写法
- 最后，对所有的二叉树遍历序列问题，都采用这种方法：先根据特点找到根节点，然后划分左右子树，对左右子树递归操作。
- 复制复杂链表 - 2019.7.17
- 书中提到了几个方法，注意看map和hash map的用法
- 对链表的理解，指针问题要加深，如何用分治方法解决问题，如何拆分函数。
-
二叉搜索树变成双向链表,这个没看透，要重点二刷。参考 - 7.17
-
37_树的序列化和反序列化 - 7.18
- 这个题就是遍历问题以及字符串和整数的转换。
- 但是其中对文件的操作，输入输出流的使用要注意，下去要再查，总结使用，现在还不能灵活应用。
- 38_字符串全排列 - 7.18
- 这个是完全的分治，递归问题，获得全排列
- C++语法对string，vector的复习
- 这个要继续看，对递归考察的典型题目。同时对所有的排列问题都适用，比如八皇后问题，抽空来解决这写
- 原书代码参考,其他参考
- 降低时间复杂度 - （使用更好的算法）
- 指针/引用传参
- 递归分析，使用循环实现（保存中间值）
- 对常用算法清楚时间空间复杂度，写代码时不断优化
- 时间空间平衡 - （使用辅存，空间换时间）
- 39_找数组出现次数超过一半的数字. -7.19
- 使用了Partiton划分函数，可以直接找到第k个位置的元素。
- 结合特性，超过一半比其他都多，有了方法二
- 同时使用了map库函数，遍历一遍，记录每个元素出现的次数，最后查找出现最多的即可。
- 40_最小的k个数 - 7.19
- 很经典的题目了，多个解法
- 首先是Partition的方法，找到第k个索引，前面就是都小于第k个值的数了；time:O(n)，但是会改变原数组
- 再就是牺牲空间复杂度，使用容器存放前k小数，不断遍历；容器选取不同也不同，如果选取数组，每次找最大值和遍历的元素比较，找最大值复杂度为O(k)，如果选取set，使用红黑树/最大堆，则每次找最大元素复杂度为O(logk)。
- 这里有用set的STL数据结构，可以看一看，包括迭代器。
- 43题_找数字中1的个数 - 7.19
- 只写了一个最简单的方法，书中给出的参考没写，观察数字的规律，今天不想看
- 参考书中规律
- 44题_数字序列的某一位 - 7.21
- 就是数字规律，还有循环，设置子函数问题。 参考原书代码
- 45_数组最小数:把数组排序成最小数，很多地方不明白，sort()函数的参数是怎么回事；怎么把compare参数传入的。
- 46_数组翻译成字符串更好，对递归的复习；递归的循环写法和递归写法，参考网上代码写了动态规划形式，还有原书代码的循环形式，对递归还是很不熟练啊，好好看一下不同的写法。
- 47_找数组对应最大路径值 - 2019.7.22
- 动态规划的实现，相关的贪心怎么用好像忘了？ 48题也是典型的动态规划
- 添加了输出路径代码，感觉很啰嗦，如何优化？
- 50_第一个只出现一次的字符 - 2019.7.23
- 这个对字符串遍历，而且使用了哈希表，使用数组实现了简单了，很有用
- 同时注意数组哈希表大小是256，因为字符char是8位，256用来作为索引键值，值是出现次数
- 判断字符是否出现，出现多少次，都可以考虑基于数组形式的哈希表。
- 51_逆序对个数 - 2019.7.24
- 这个归并的递归逻辑完全迷迷糊糊，一定要回来再看啊，要不然肯定会犯晕
- 每步调试走一遍，会清晰的多。
- 原书代码参考, 网上的代码参考，感觉更清晰。
- 52_两个链表第一个公共节点 - 2019.7.24
- 这个有多个思路，可以启发一下，同时可扩展到树的最低公共祖先，具有参考价值。
- 多种实现参看网上这个代码
- 沟通能力
- 学习能力：对新概念的衍生
- 提问：对模糊的地方大胆提问
- 知识迁移能力
- 抽象建模能力：选取合理数据结构：分析内在规律，写代码
- 发散思维能力：灵活变通，知识面广
- 53_对二分法的典型应用 - 2019.7.25
- 这三个对二分法的典型，二分法使用与排序数组，只要在排序数组中查找一个数字，可以考虑二分法，复杂度降为 O(logn).
- 54_二叉搜索树第k大个节点, 55_判断是否平衡二叉树 - 2019.7.25
- 这两个题本质都是对树的遍历
- 54题要深刻明白二叉搜索树的中序遍历是递增序列，然后就是中序遍历，同时注意找到的条件判断。参考网上代码,原书的代码有些疑惑，调试有问题。
- 同时对树的递归仍然不是很清晰，犯迷糊。
- 55题要继续看啊，有些迷迷糊糊的，包括传参和判断条件，对每个节点层数的保存，如何想到思路,完成实现。参考代码
- 56_数组中出现的次数 - 2019.7.26
- 在找数组中只出现一次的数字，可用异或的方法，相同的数字就变为0.但是异或只能用于出现两次的数字，且查找只有重复一次的数字
- 如果有其他情况，则想把发分拆，比如分成两个数组；或者2中累计某一位0/1的个数，进行确定。具体问题好好分析
- 57_和为s的数字 - 2019.7.27
- 这两个个是典型的双指针问题
- 第57_2的while循环逻辑注意一下。
- 58_字符串翻转 - 2019.7.27
- 字符串翻转问题，一般是可以考虑字符串两次翻转解法，这类字符串问题好像也是一块。使用指针解决
- 这两个题在输入上需要改进，对于字符串指针和cin的操作还是不熟悉，这里没有解决，直接输入的。
- 指针问题，尤其是1中ReverseChar()函数的两个指针间的变换，要注意。同时要注意边界条件和空指针问题
- 59_滑动窗口和队列的最大值 - 2019.7.28
- 这个有点难，构造队列的最大值函数，其中保持最大值那一点还是很晕；
- 一是判断是否比队列中元素大；二就是判断队中最大值是否已经超出窗口范围，所以用索引存储判断。其他方法可以参考网上这个
- 包括2中构造最大队的类，如何表示最大值这个逻辑要清晰，多看这个代码。参考原书
- 62_圆圈中剩下的数字(约瑟夫环) - 2019.7.28
- 这个很经典，看的很多，用个链表，模拟环形链表（每次到尾部就指向头部）. O(nm)
- 还有种方法是用公式递推，很巧妙。O(n)
- 63_股票最大值 - 2019.7.28
- 同样是经典的问题，这个简单遍历，找最小值并更新最大差值即可
- 有多种变形，后面可用动态规划解决。具体参考
- 64_不用循环求1+..+n,65_位运算做加法 - 2017.7.30
- 发散题目，对C++基础，以及多种计算机基础进行考察，64中包括递归，构造函数，指针，位运算。64题其他参考解法
- 64题是对位运算，位移的典型应用解法，很优美巧妙。
- 6.25-7.30,虽然比计划多用了十天，但还是跌跌撞撞刷完了。每本书看完都有中莫名的成就感，感觉自己马上提高一大截，然而结果和想的总是不一致哈哈哈。
- 刷的过程中发现有几点需要加强：
- 对C++基础，以及很多细节还不熟练；（多看，多写）
- 同时对高级数据结构并没掌握；（选一本数据结构和算法分析继续全面深入）
- 对于贪心，回溯这样的算法也并不能灵活应用；（多刷题）