剑指offer-高质量的代码

大家好，我是Nefelibat。

在博客上记录算法笔记，是因为想push自己每天坚持刷几道算法题，同时也希望能把自己总结到的经验分享给大家，希望大家阅读愉快

目录

面试官常常考虑的

代码的规范性

注意：应聘者在写代码的时候，最好用完整的英文单词组合命名变量和函数。

代码的完整性

题目：数值的整数次方

思路

代码

全面高效的代码

 题目：打印从1到最大的n位数

思路

代码

思路

代码

 将问题转换成数字排列的问题，递归让代码更简洁

 测试用例

扩展

题目：删除链表的节点

思路

存在问题：

如果要删除的节点位于链表的尾部，遍历链表得到这个节点的前序节点，那么就不存在下一个节点， 如果链表中只有 一个节点，那么在删除节点之后将链表的头节点设置为nullptr.

代码

用例

题目：删除链表中重复的节点

思路

代码（后续需要看）

用例

题目：正则表达式匹配

思路

代码

 用例

题目：表示数值的字符串

思路

代码

 用例

题目：调整数组顺序使奇数位于偶数前面

思路

改进思路

 代码

 扩展题目：将一个数组中的负数放在非负数的前面

 扩展题目：将一个数组能被3整除的数放在不能被3整除的数前面

代码

 用例

题目：链表中的倒数第K个节点

思路

代码

存在的问题

改进代码

用例

题目：链表中的环的入口节点

思路

 代码

用例

题目：反转链表

思路

代码

用例

题目：合并两个排序的链表

思路

代码

用例

 题目：树的子结构（和链表相比，树的指针更难）

思路

代码

用例

 注意

---

面试官常常考虑的

从程序的正确性和鲁棒性两方面检验代码的质量，比如输出参数的检测，处理错误和异常的方式，命名方式。

代码的规范性

注意：应聘者在写代码的时候，最好用完整的英文单词组合命名变量和函数。

代码的完整性

检查代码是否完成基本的功能，输入的边界值是否能得到正确的输出、对各种用例就做出了处理。

题目：数值的整数次方

用手写代码实现C语言中的pow()函数。

思路

需要考虑指数小于1的情况。当指数为负数，先对指数取绝对值，算出结果之后再取倒数。但是当底数是0的时候取倒数会报错，需要进行特殊处理，同样0的0次方在数学上是没有意义的，因此取0和取1都是可以接收的。

代码

全面高效的代码

如果指数比较大的化，需要做31次乘法，求一个数的32次方，如果已经知道了它的的16次方，那么只要在16次方的基础上再平方一次就可以，这样的化32次方我们需要做5次乘法。

 

我们用右移代替了除2，位运算的效率比较高

 题目：打印从1到最大的n位数

输入数字n,按顺序从1到最大的n位十进制数，比如输入3，则打印出1,2,3，...999

思路

最容易想到的是先求出最大的n位数，然后循环从1开始打印，代码如下：

代码

 但是当输入n很大的时候，是不是会溢出？

思路

在字符串上模拟数字加法的解法，可以用字符串表示大数。字符串表示数字的时候，字符串中的每个字符都是0-9之间的某一个字符，用来表示数字中的一位。因为数字最大是n位，我们需要一个长度为n+1的字符串，字符串中的最后一位是结束符号\0,当实际数字不够n位的时候，在字符串的前半部分补0. Increment表示数字的字符串number上增加1，PrintNumber打印出number,

我们需要最大什么时候停止在number增加1，在每次递增之后，调用strcmp()表示数字的字符串number和最大的n位数“99...99”,只有在“99..99”加1的时候，才会在第一个字符的基础上产生进位，

代码

 

 将问题转换成数字排列的问题，递归让代码更简洁

 测试用例

1、功能测试，输入1,2,3,..

2、特殊输入测试，输入-1,0

扩展

在前面的代码。我们用char的一个字符表示十进制数中的一位，8bit的字符最多能表256个字符，2的8次方，但是十进制的数字0-9只能表示10个数字，因为char字符能充分利用内存，那么有没有更高效的表示大数？

题目：删除链表的节点

在o(1)时间内删除节点，跟定一个单链表的头指针和一个节点指针。

思路

遍历链表找到需要删除的节点，并从链表中删除节点。

存在问题：

如果要删除的节点位于链表的尾部，遍历链表得到这个节点的前序节点，那么就不存在下一个节点， 如果链表中只有 一个节点，那么在删除节点之后将链表的头节点设置为nullptr.

代码

用例

删除头节点，删除尾节点，删除只有一个节点的链表

题目：删除链表中重复的节点

在一个排序的链表中，如何删除重复的节点

思路

从头遍历链表，如果当前节点与下一个节点的值相同，就删除

代码（后续需要看）

 

用例

重复的节点位于链表的头部、尾部，中间，链表中没有重复的节点，指向链表头节点的是nullptr指针，链表中的所有节点都是重复的。

题目：正则表达式匹配

设置一个函数用来匹配包含“.”和“*”的正则表达式，模式中的“.”可以表示任意一个字符，“*”表示它前面的字符可以出现任意次，例如，“aaa”与“a.a”和“ab*ac*a”匹配。

思路

当模式中第二个字符不是“*”时，如果字符串中的第一个字符和模式中的第一个字符相匹配，那么字符和模式都向后移动一个字符，然后匹配剩余的字符串和模式，如果字符串中的第一个字符和模式中的第一个字符不匹配，返回false.

当模式中的第二个字符是“*”时，模式上向后移动两个字符，相当于“*”和它前面的字符被忽略，

代码

 

 

 用例

字符串和模式字符串是nullptr或者空字符串，模式字符串汇总包含“.”和“*”，模式字符串和输入字符串匹配或者不匹配

题目：表示数值的字符串

实现用一个函数判断字符串是否表示数值

例如“12e“,"1a3.14"不是数值

思路

用A，B, C 三部分分别代码数值的整数、小数和指数部分，首先扫描数值的整数部分，如果遇到“.”,扫描数值的小数部分，如果遇到e或者E，扫描数值的指数部分。

代码

 

 用例

正数、负数、包含不包含整数部分的数值，包含不包含小数部分的数值，包含不包含指数部分的数值；输入字符串或者模式字符串是nullptr,空字符串。

题目：调整数组顺序使奇数位于偶数前面

思路

如果不考虑时间问题，从头扫描这个数字，每碰到一个偶数，拿出这个数字，将位于这个数字后面的数字往前挪动一位，数字末尾空出一个空位，将该偶数放入这个空位，移动一次的时间复杂度是o(n),因此时间复杂度是o(n2)

改进思路

在扫描数组的时候发现偶数出现在奇数的前面，交换两个数字，用一个指针指向数组的第一个数字，往后移动，一个指针指向数组的最后一个数字，往前移动，如果前面的指针指向的是偶数，并且第二个指针指向的是奇数，交换两个数字。

 代码

 扩展题目：将一个数组中的负数放在非负数的前面

 扩展题目：将一个数组能被3整除的数放在不能被3整除的数前面

为了解决这一类问题，只需要修改判断条件，因此可以将这个逻辑框架抽象出来，用一个单独的函数用来判断数字是否符合标准。

代码

 用例

数组中的偶数和奇数交替出现，输入的所有数组都出现在奇数的前面，输入的所有的奇数都出现在偶数的前面，输入nullptr指针，数组只包含一个数字

题目：链表中的倒数第K个节点

思路

1、先遍历到链表的尾端，然后回溯k步，但是单向链表没有前向指针

2、从头开始遍历链表，链表有n个节点，那么倒数第K个节点即使从头节点开始的n-K+1个节点

3、第二种方法需要遍历链表2次，如果面试官要求遍历链表1次，那么第二种方法不可行，需要两个指针，第一个指针从头开始遍历k-1个节点时，第二个指针从链表的头节点开始遍历，这样两个指针的距离就是k-1,当第一个指针到达尾部时，第二个指针指向链表的第K个节点。

代码

存在的问题

如果输入的头节点指向的是空指针，输入的链表的节点数小于k,输入的k是0，针对这三个问题分别处理。

改进代码

用例

第 k个节点是链表的头节点，尾节点；链表的头节点是nullptr,链表的总节点数小于k,k等于0.

题目：链表中的环的入口节点

思路

第一步确定链表中是否含有环，定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步，如果两个指针相遇，那么链表就有环，如果一个指针到了链表的末尾，那么就不包含环。

第二步是找到环的入口，假设一个链表包含n个节点，一个指针先走n步，然后另一个指针从头指针出发，一个指针从尾部出发，两个指针相遇的节点就是入口节点。然后从这个节点开始计数，再次回到这个节点计数结束。

 代码

用例

链表中包含环或者不包含环，链表中有多个或者只有一个节点，链表头节点为nullptr指针

题目：反转链表

思路

在我们调节节点i的时候，需要知道节点i的前一个节点h,我们将 i的next指针指向h

代码

用例

链表中有多个节点，链表中有一个节点，链表头节点为nullptr指针

题目：合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

 

思路

1、链表1的头节点小于链表2的头结点的值，因此链表1的头节点是合并后链表的头节点。

2、在剩余的节点中，链表2的头结点小于链表1的头结点，因此链表2的头结点是剩余节点的头节点

因为合并的步骤都是一样的，因此这可以看做是一个递归过程。

代码

 

用例

待合并的两个链表有多个节点；节点的值互不相同或者存在值相等的多个节点；两个链表汇总只有一个节点；两个链表的头指针是nullptr.

 题目：树的子结构（和链表相比，树的指针更难）

输入两棵二叉树A和B，判断B是不是A的子结构。

思路

第一步，在A 中找到和B的根节点一样的节点R，第二步，判断A中以R为根节点的子树是不是包含和B一样的结构。

代码

第一步需要遍历树，树的遍历可以递归，可以循环，递归的方法较简单。

 

用例

A和B是普通的二叉树，B不是A的子结构，A和B的一个或者两个根节点为nullptr指针，A 或B没有左指数或者右指数。

 注意

1、在每次使用指针的时候，我们都要问自己这个指针有没有可能是nullptr,如果是nullptr应该怎么处理。

2、由于计算机表示小数有误差，我们不能直接使用符号==判断两个小数是否相等，如果两个小数的差的绝对值很小，就可以认为相等。