剑指offer读书笔记：第三章，高质量的代码

朱雀 2022-05-29 20:09 193阅读 0赞

# 问题01 代码的全面性 #

在写代码的时候要注意各种情况的考虑，一般分为三个方面：

*  **功能测试：**这个主要测试可以不可以完成函数的功能，
 *  **边界测试：**这个尽量要考虑各种极端的case，比如循环条件的边界判断、数据溢出的考虑等等
 *  **负面测试**：这个主要是各种错误的输入，靠考虑系统的鲁棒性，比如指针为null应该怎么考虑，等等。
 *  \-

![这里写图片描述][70]

# 问题02 数值的整数次方 #

![这里写图片描述][70 1]

对于这道题，要考虑四种情况：  
1、底数为0，指数为负数的情况，无意义  
2、指数为0，返回1  
3、指数为负数，返回1.0/base,-exponent  
4、指数正数，base,exponent

**注意浮点数的等于运算是需要一个评估值**

public class Solution {
        public double Power(double base, int exponent) throws Exception{
            double result = 0.0;
            if (equal(base, 0.0) && exponent < 0) {
                throw new Exception("0的负数次幂无意义");
    
            }
            if (equal(exponent, 0)) {
                return 1.0;
            }
            if (exponent < 0) {
                result = powerWithExponent(1.0 / base, -exponent);
            } else {
                result = powerWithExponent(base, exponent);
            }
            return result;
      }
        private double powerWithExponent(double base, int exponent) {
            double result = 1.0;
            for (int i = 1; i <= exponent; i++) {
                result = result * base;
            }
            return result;
        }
        // 判断两个double型数据，计算机有误差
        private boolean equal(double num1, double num2) {
            if ((num1 - num2 > -0.0000001) && (num1 - num2 < 0.0000001)) {
                return true;
            } else {
                return false;
            }
        }
    }

进一步的优化，直接递归去做

private double powerWithExponent2(double base,int exponent){
            if(exponent == 0){
                return 1;
            }
            if(exponent == 1){
                return base;
            }
            double result = powerWithExponent2(base, exponent >> 1);
            result *= result;
            if((exponent&0x1) == 1){
                result *= base;
            }
            return result;
        }

# 问题03 打印1到最大的n位数 #

![这里写图片描述][70 2]

最简单的想法就是先找出最大的n位数，然后循环打印即可。然而上述程序在n很大时，显然会有溢出,int 的范围不够。那么我们会想到用long来存储，但是如果n的值还是很大，以至于long也无法满足要求。那么该怎么办？最好想问一下n的范围：假如在整数范围之内，可以考虑int，否者考虑字符串加法来做。

# 问题04 在O(1)时间删除链表结点 #

![这里写图片描述][70 3]

在单向链表中删除一个节点，通常的做法是从链表头开始遍历，如果某个节点的next等于要删除的节点，就将该next改为待删除节点的下一个节点，然后删除该链表节点即可。

因为我们要删除某个节点，如果不是第一个节点的话，就需要更改它前面节点的next值。而单链表是无法逆行的，所以我们可以按如下步骤做：  
1. 如果待删除节点不是最后一个节点，就用他的next节点的value覆盖它的value，然后删掉它的next节点。  
2. 如果是最后一个节点，还是老老实实的顺序遍历吧。

# 问题05 调整数组顺序使奇数位于偶数前面 #

![这里写图片描述][70 4]

首先，说一种时间复杂度为O(n),但是空间复杂度较高的。但是这种代码，肯定不会是面试官喜欢的。我们申请另外两个数组，每次输入数据时，直接比对是奇数还是偶数，顺序存放在两个数组中，并记录下标的变化。最后两个数组顺序输出就行了，  
　另一种思想，不开辟新的空间，直接在原始数组上，进行移动。但是考虑到前后的顺序不能变化，因此简单的哨兵替换思想就不可以了。这时候我们可以通过两个下标，进行数据元素的移动。

# 问题06 链表中倒数第K个结点 #

![这里写图片描述][70 5]

这个很简单，直接固定窗口即可

# 问题07 反转链表 #

![这里写图片描述][70 6]

头部插入法反转链表

注意node为null、node->next为null的情况考虑

# 问题08 合并两个有序链表 #

![这里写图片描述][70 7]

直接归并即可，主语链表头结点为null的考虑

# 问题09 树的子结构 #

![这里写图片描述][70 8]

双函数DFS深度优先遍历即可

# 总结 #

![这里写图片描述][70 9]

[70]: /images/20220530/fd7263ecd70f48abb9f688d455efa976.png
[70 1]: /images/20220530/7504b1556f914b73a66042d010a00fd4.png
[70 2]: /images/20220530/acf5cfa75a224d1d9843629cdc5ed37b.png
[70 3]: /images/20220530/f1b136a7004543598c958652881dd5e1.png
[70 4]: /images/20220530/b8751b5fd7604a51b1aec80508faede8.png
[70 5]: /images/20220530/bc29a5c5ac5c4ddaa149cac02a7d9465.png
[70 6]: /images/20220530/4a5045e0cb4141a09ba70edee25d562c.png
[70 7]: /images/20220530/0b0589cf60144831bed8b6ed793fec26.png
[70 8]: /images/20220530/c828627e63b04557982a7e7b071ca204.png
[70 9]: /images/20220530/d6fc386a69d64139af564beee2e11275.png