章节主要目的

主要是围绕高质量代码，完成性、规范性和鲁棒性。
测试用例的编写，通常情况，我们为了完成单元测试覆盖率都是草草了事，学习这一章我们可以发现，我们之前的测试用例实用性很差，只有正常情况的用例，并且很多时候只有一个。之后我也跟着用例从三方面来运行：1、功能测试，2、负面测试，3、边界测试。负面测试可以理解为错误测试，异常情况的测试。

正式开始第三章

面试题11:数值的整数次方

leetcode-cn.com/problems/shu-zhi-d...
按照题意，很容易写出来基本的逻辑代码。

func myPow(x float64, n int) float64 {
   var result = 1.0

   if n < 0 {
       x = 1 / x
       n = -n
   }
   for i := 0; i < n; i++ {
       result *= x
   }
   return result
}

可惜，会提示超时，尴尬的很，于是乎看了一遍原文的逻辑，重新实现一遍，逻辑如下：
快速幂 算法
算法流程：
当 x = 0 时：直接返回 0 （避免后续 x = 1 / x操作报错）。
初始化 res = 1
当 n < 0 时：把问题转化至 n≥0 的范围内，即执行 x = 1/x ，n = - n ；
循环计算：当 n = 0时跳出；
当 n & 1 == 1 时：将当前 x乘入 res （即 res *= x）；
执行 x = x^2 （即 x *= x）
执行 n 右移一位（即 n >>= 1）。
返回 res

func myPow(x float64, n int) float64 {
    var result = 1.0

    if n < 0 {
        x = 1 / x
        n = -n
    }
    for ; n > 0; {
        if n&1 == 1 { //又学了一招位运算，等价于 n % 2 == 1
            result *= x
        }
        x *= x
        n >>= 1 // 指数减半
    }
    return result
}

面试题12: 打印1到最大的n位数

leetcode-cn.com/problems/da-yin-co...
虽然能通过leetcode，但是不符合书本上出题的目的，因为要考虑大数的情况下才行，书上给出的思路是转换成字符串来进行输出

func printNumbers(n int) []int {
   res := make([]int,0)
   var count = 1
   for i := 1; i < n; i++ {
       count *= 10
   }

   for i := 0; i < count; i++ {
       res = append(res,i)
   }

   return res
}

这不包括大数，不是书本出题的本意，修改如下：
考察的是代码的完整性 返回就不能是[]int 而应该是[]string，看具体代码，没办法在leetcode验证，只能自己打印日志看了。

func printNumbers(n int) []string {
    if n <= 0 {
        return nil
    }
    res := make([]int, 0)
    result := make([]string, 0)
    number := make([]int, n)
    for !increment(number) {
        for i := 0; i < len(number); i++ {
            res = append(res, number[i])
        }
    }
    //数组按n位切分成而为数组
    temp := make([]int, 0)
    for i := 0; i < len(res); i++ {
        temp = append(temp, res[i])
        if (i+1)%n == 0 { // 3余数是0 。说明是n的整数倍
            result = append(result, getString(temp))
            temp = make([]int, 0)
        }
    }
    return result
}

func getString(number []int) string {
    var res string
    isBegin := false
    for i := 0; i < len(number); i++ {
        if number[i] != 0 {
            isBegin = true
        }
        if isBegin {
            res += fmt.Sprintf("%d", number[i])
        }
    }
    return res
}

func increment(number []int) bool {
    var isOverFlow = false //是否溢出结束
    var nTakeOver = 0      // 进位
    var nLength = len(number)
    for i := nLength - 1; i >= 0; i-- {
        nSum := number[i] + nTakeOver
        if nLength-1 == i {
            nSum++
        }
        if nSum >= 10 {
            if i == 0 {
                isOverFlow = true
            } else {
                nSum -= 10
                nTakeOver = 1
                number[i] = nSum
            }
        } else {
            number[i] = nSum
            break
        }
    }
    return isOverFlow
}

面试题13: 在O(1)时间删除链表节点

leetcode-cn.com/problems/shan-chu-...
leetcode要求比书本上的低，没有时间复杂度的要求

// 先不考虑O（1），遍历是最直接的
func deleteNode(head *ListNode, val int){
   if head == nil {
       return
   }
   for head.Next != nil {
       if head.Next.Val == val {
           head.Next = head.Next.Next
       }
       head = head.Next
   }
}

链表少不了假头、新链表、双指针等辅助，目前就是使用假头的最佳实例，和书上的不一样哈，课本上的删除就完了，不用返回，力扣是要删除后返回头节点的

func deleteNode(head *ListNode, val int) *ListNode {
   //for head.Next != nil {
   //    if val == head.Next.Val {
   //        head = head.Next.Next//删除节点 课本上这就结束了。
   //    }
   //}
   dummy := &ListNode{}// 生成一个新链表
   tail := dummy
   for head != nil {
       if head.Val != val {
           //添加到新的链表中
           tail.Next = head
           tail = head
       }
       head = head.Next
   }
   tail.Next = nil //设置尾部为空
   return dummy.Next
}

上面的例子中，空间复杂度是O(n),想要是1的话，只能按照课本上的参数传递才行，否者不可实现

func deleteNode(head *ListNode, deleteNode *ListNode) {
   if head == nil || deleteNode == nil {
       return
   }
   if deleteNode.Next != nil {//不是尾节点
       //删除的节点下一个值，替换需要删除的节点，然后删除下一个节点，等同于删除当前节点
       deleteNode.Val = deleteNode.Next.Val
       deleteNode.Next = deleteNode.Next.Next
   }else if head == deleteNode {//删除的是头节点，只有一个节点
       head = nil
   }else{ // 多个节点，删除的是尾节点 第一个if条件难道不包括吗？
       for head.Next != deleteNode {
           head = head.Next
       }
       head.Next = nil
   }
}

面试题14: 调整数组顺序使奇数位于偶数前面

leetcode-cn.com/problems/diao-zhen...
思路：两个指针，一个指向头，一个指向尾部，两边同时向中间移动，如果头指针的值偶数，尾指针是奇数就交换
通用性：判断条件改为函数来判断，分离出来nums[left]&1 == 1和nums[right]&1 == 0换成函数就可以了，很简单，自行添加一下。

func exchange(nums []int) []int {
    if len(nums) == 0 {
        return nil
    }
    var left = 0
    var right = len(nums) - 1

    for left < right {
        for left < right && nums[left]&1 == 1 { //奇数，右移left
            left++
        }
        for left < right && nums[right]&1 == 0 { //偶数，左移right
            right--
        }
        if left < right { //交换
            nums[left], nums[right] = nums[right], nums[left]
        }
    }
    return nums
}

面试题15: 链表中倒数第k个节点

leetcode-cn.com/problems/lian-biao...
思路：两个指针，一个指向头，一个先走k步，简称：快慢指针

func getKthFromEnd(head *ListNode, k int) *ListNode {
   if head != nil {
       return nil
   }
   var first = head
   var second = head
   for i := 0; i < k; i++ {
       second = second.Next
   }
   for second != nil {
       first = first.Next
       second = second.Next
   }
   return first
}

面试题16: 反转链表

leetcode-cn.com/problems/UHnkqh/
这题，如果没有限制返回头节点，仅仅是输出的话，实现方式是N多种，数组也是可以的。但是这里的要求是返回反转后的头节点，所以，需要辅助手段。

//需要把节点保存起来，断开之后防止找不到
func reverseList(head *ListNode) *ListNode {
   var prevHead *ListNode //保存遍历的前一个节点
   var currentNode = head //保存遍历的当前节点
   for currentNode != nil {
       nextNode := currentNode.Next
       currentNode.Next = prevHead
       prevHead = currentNode
       currentNode = nextNode
   }
   return prevHead
}

按照课本上的做法，我临摹过来的代码，但是，这个代码我感觉有点小问题，却又不知道问题在哪，各位朋友知道的还望指出来，并改正一下，不胜感激。

func reverseList(head *ListNode) *ListNode {
    var reversedHead *ListNode //反转后的头节点
    var prev *ListNode
    var node = head
    for node != nil {
        next := node.Next
        if next == nil {
            reversedHead = node
        }
        node.Next = prev
        prev = node
        node = next
    }
    return reversedHead
}

面试题17: 合并两个排序的链表

leetcode-cn.com/problems/he-bing-l...
同样利用了链表的假头和新链表作为辅助

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            tail.Next = l1
            l1 = l1.Next
        } else {
            tail.Next = l2
            l2 = l2.Next
        }
        tail = tail.Next
    }
    if l1 != nil {// 如果l1还有，直接拼接到后面
        tail.Next = l1
        tail = tail.Next
        l1 = l1.Next
    }

    if l2 != nil {//如果l2还有，直接拼接后面
        tail.Next = l2
        tail = tail.Next
        l2 = l2.Next
    }
    return dummy.Next
}

面试题18: 树的子结构

leetcode-cn.com/problems/shu-de-zi...
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
主要和树相关的，就没有简单级别的，当然，和递归相关的也都是没有简单的。不熟悉递归和树的，这题需要点时间去理解。

func isSubStructure(A *TreeNode, B *TreeNode) bool {
    var result = false
    if A != nil && B != nil {
        //先比较根节点，再比较左右子树节点
        if A.Val == B.Val {
            //根节点满足，判断不是子结构
            result = isStructure(A,B) //不用递归，也可写成左右子树的判断
        }
        //比较左子树为根节点，开始遍历比较
        if !result {
            result = isSubStructure(A.Left,B)
        }
        //比较右子树为根节点，开始遍历比较
        if !result {
            result = isSubStructure(A.Right,B)
        }
    }
    return result
}

func isStructure(a *TreeNode, b *TreeNode) bool {
    if b == nil {//说明树 B 已匹配完成（越过叶子节点），因此返回 true
        return true
    }
    if a == nil {//说明已经越过树 A 叶子节点，即匹配失败，返回 false
        return false
    }
    if a.Val != b.Val {//值不同，匹配失败，返回 false
        return false
    }
    return isStructure(a.Left,b.Left) && isStructure(a.Right,b.Right)
}
``````go
func isSubStructure(A *TreeNode, B *TreeNode) bool {
    var result = false
    if A != nil && B != nil {
        //先比较根节点，再比较左右子树节点
        if A.Val == B.Val {
            //根节点满足，判断不是子结构
            result = isStructure(A,B) //不用递归，也可写成左右子树的判断
        }
        //比较左子树为根节点，开始遍历比较
        if !result {
            result = isSubStructure(A.Left,B)
        }
        //比较右子树为根节点，开始遍历比较
        if !result {
            result = isSubStructure(A.Right,B)
        }
    }
    return result
}

func isStructure(a *TreeNode, b *TreeNode) bool {
    if b == nil {//说明树 B 已匹配完成（越过叶子节点），因此返回 true
        return true
    }
    if a == nil {//说明已经越过树 A 叶子节点，即匹配失败，返回 false
        return false
    }
    if a.Val != b.Val {//值不同，匹配失败，返回 false
        return false
    }
    return isStructure(a.Left,b.Left) && isStructure(a.Right,b.Right)
}
``````go
func isSubStructure(A *TreeNode, B *TreeNode) bool {
    var result = false
    if A != nil && B != nil {
        //先比较根节点，再比较左右子树节点
        if A.Val == B.Val {
            //根节点满足，判断不是子结构
            result = isStructure(A,B) //不用递归，也可写成左右子树的判断
        }
        //比较左子树为根节点，开始遍历比较
        if !result {
            result = isSubStructure(A.Left,B)
        }
        //比较右子树为根节点，开始遍历比较
        if !result {
            result = isSubStructure(A.Right,B)
        }
    }
    return result
}

func isStructure(a *TreeNode, b *TreeNode) bool {
    if b == nil {//说明树 B 已匹配完成（越过叶子节点），因此返回 true
        return true
    }
    if a == nil {//说明已经越过树 A 叶子节点，即匹配失败，返回 false
        return false
    }
    if a.Val != b.Val {//值不同，匹配失败，返回 false
        return false
    }
    return isStructure(a.Left,b.Left) && isStructure(a.Right,b.Right)
}

接下来的算法都是非常难的，我也不知道多久能研究透彻，可以确定的是更新时间肯定比第二第三章要晚。

本作品采用《CC 协议》，转载必须注明作者和本文链接