为何选择这本书来刷题：

leetcode题目实在太多了，找了半天还是回到这本10年前的书，题目数量不多，但是都比较经典，覆盖知识点比较广。开始参加leetcode周赛，做两题都是很难的，尤其是面对一堆大牛动不动四道题全做出来，很受刺激，真的是自惭形秽。狠下心来，只能自己慢慢研究一波，现在稳定两道题，偶尔还能突破三道题，这时候再重新回顾一遍剑指offer第二版，发现，以前死记硬背应对面试的东西，现在可以自己实现出来了。很多同学也说自己算法很差，有的甚至连数组和链表都分不清楚的，所以就试着分享，用GO语言重新实现一遍，也把涉及到的相关知识点一并讲解。

关于第一章的省略说明：

第一章主要介绍面试的环节和流程，感觉跟国内的实际情况有点不相符，毕竟很多并没有这么专业，所以就不打算深究了，主要以面试题的Go版本实现为主，一起相互刷题吧。途中也有很多自己理解不透彻的地方，毕竟，算法方面，我也是个半桶水。

正式开始第二章

面试题1:赋值运算符函数

实在不知道这题的考点是什么，对于任何一种语言来说，字符串的拼接方式很多种，也不会有哪家公司的面试官脑子不开窍问这种题吧。

面试题2:实现单例模式

书上用的是C++，采用的最好方式是静态内部类实现的。GO语言本身来说并没有类一说，也没有内部类一说，init函数实现一个全局的，就相当于实现一个静态的实例，更多的是用sync.Do函数来做单例，实际上，init函数更受用一点，简单方便，只是可能会增加依赖。

面试题3:二维数组中的查找

先附上leetcode地址：leetcode-cn.com/problems/er-wei-sh...
书中都是其他语言的，想要自己实现不可能直接抄代码改写吧，先自己实现一遍还是有必要的，起码自己动了脑，还可以借助leetcode提供的测试用例来验证，实现方式也不一定就是书上提供的。代码解释看注释。

// 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，
//每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，
//输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
func findNumberIn2DArray(matrix [][]int, target int) bool {
    if len(matrix) == 0 {
        return false
    }
    var col = len(matrix[0])//从每一行的最后一个开始查找，组成矩阵
    var row = 0
    for ; row < len(matrix) && col > 0; {
        if matrix[row][col-1] == target {//相等直接返回
            return true
        } else if matrix[row][col-1] > target {//大于，向左移动一列，缩小矩阵范围
            col--
        } else {//小于就向下移动一行，缩小矩阵范围
            row++
        }
    }
    return false
}

面试题4:替换空格

leetcode-cn.com/problems/ti-huan-k...
这道题考查的是数组从后往前坐替换，减少移动次数。但是，算法比赛讲究的是时间，如果面试的时候面试官有要求，就按照书上说的来实现，但是直接使用库函数，leetcode上是接近双百的，要研究的可以自己去把字符串遍历字符数组，第一字符进行替换操作。

func replaceSpace(s string) string {
    return strings.Replace(s, " ", "%20", -1)
}

面试题5:从尾到头打印链表

leetcode-cn.com/problems/cong-wei-...
这个实现方式就更多了，书上说的很全面，面试官沟通清楚是不是可以破坏结构，是不是可以额外添加存储空间。

func reversePrint(head *ListNode) []int {
    res := make([]int, 0)
    if head == nil {
        return res
    }
    for head != nil {
        res = append(res, head.Val)
        head = head.Next
    }
    for i, j := 0, len(res)-1; i < j; {
        res[i], res[j] = res[j], res[i]
        i++
        j--
    }
    return res
}

这里有更简洁的代码，但是效率很低，就是直接在数组前面插入数字，直接返回数组就可以了，由此可见，数组的插入是多么的耗时间。原因和前面二维数组查找的原因一样，前面每次插入所有的元素都要排序一次。

func reversePrint(head *ListNode) []int {
    res := make([]int, 0)
    if head == nil {
        return res
    }
    for head.Next != nil {
        res = append([]int{head.Val}, res...)
        head = head.Next
    }
    res = append([]int{head.Val}, res...)
    return res
}

面试题6:重建二叉树

leetcode-cn.com/problems/zhong-jia...
可以知道，只要和树关联的都是中等难度起步，没有简单的。前序和中序遍历，构建一棵树。面试中不会问到这种问题的，用笔画出来可能更好理解。不会的不用纠结，过段时间回头看发现这都是基础了。另外，递归也要好好研究下，我也用的不是很溜，有时候知道原理也不一定能实现的出来，所以借助leetcode的测试用例，还是很有用的。当然有人取巧，把每个用例都是手动实现一遍，我们是练习，没必要，大牛才这么搞。

func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 {
        return nil
    }
    var index = 0
    for ;index < len(inorder); index++{// 遍历中序
        if preorder[0] == inorder[index] {//找到根结点的值位置
            break
        }
    }
    root:=&TreeNode{}
    root.Val = preorder[0]
    root.Left = buildTree(preorder[1:index+1],inorder[0:index])//递归左子树
    root.Right = buildTree(preorder[index+1:],inorder[index+1:])//递归右子树
    return root
}

面试题7:用两个栈实现队列

leetcode-cn.com/problems/yong-lian...
这个提，我觉得完全是动嘴的题目，没有考察代码能力，纯粹的思维考察。有时候不要纠结，该跳过跳过，看看实现原理，不动手也可以的。毕竟这个实现也是添加和删除，想不到该分享的技术实现在哪。用了官网的答案：

type CQueue struct {
    stack1, stack2 *list.List
}

func Constructor() CQueue {
    return CQueue{
        stack1: list.New(),
        stack2: list.New(),
    }
}

func (this *CQueue) AppendTail(value int)  {
    this.stack1.PushBack(value)
}

func (this *CQueue) DeleteHead() int {
    // 如果第二个栈为空
    if this.stack2.Len() == 0 {
        for this.stack1.Len() > 0 {
            this.stack2.PushBack(this.stack1.Remove(this.stack1.Back()))
        }
    }
    if this.stack2.Len() != 0 {
        e := this.stack2.Back()
        this.stack2.Remove(e)
        return e.Value.(int)
    }
    return -1
}

面试题8:旋转数组最小数字

leetcode-cn.com/problems/xuan-zhua...
暴力搜索都可以通过

func minArray(numbers []int) int {
    if len(numbers) == 0 {
        return 0
    }
    min := numbers[0]
    for i := 1; i < len(numbers); i++ {
        if numbers[i-1] > numbers[i] {
            if min > numbers[i] {
                min = numbers[i]
            }
            break
        }
    }
    return min
}

当然，人家看差点肯定不是这个，是如果更快的查找到这个值。因为是组多有两部分排序组成的，依然可以使用二分查找。参考官网的，我也是没想到这么多特例的，low逼一个。如果有人不会，看题解吧，比我解释起来好太多太多。leetcode-cn.com/problems/xuan-zhua...

func minArray(numbers []int) int {
    low := 0
    high := len(numbers) - 1
    for low < high {
        pivot := low + (high - low) / 2
        if numbers[pivot] < numbers[high] {
            high = pivot
        } else if numbers[pivot] > numbers[high] {
            low = pivot + 1
        } else {
            high--
        }
    }
    return numbers[low]
}

面试题9:斐波那契数列

leetcode-cn.com/problems/fei-bo-na...
经典的不能再经典的题，递归的经典使用题型。

func fib(n int) int {
if n == 0 {
        return 0
    }
    if n == 1 {
        return 1
    }
    return fib(n-1)+fib(n-2)
}

这是经典写法，完全按照表达式来实现的，结果在leetcode里面是超过时间限制的提示。体会到网站的强大之处吗？

func fib(n int) int {
    const mod int = 1e9 + 7
    if n < 2 {
        return n
    }
    p, q, r := 0, 0, 1
    for i := 2; i <= n; i++ {
        p = q
        q = r
        r = (p + q) % mod
    }
    return r
}

昨天有人跟我反馈说可以使用尾递归也是一种优化方式，这个确实是，但是不符合leetcode的要求，因为尾递归的方式改变了入参个数。如果要使用，只能添加一个新的函数包裹一层。但是，过不了leetcode的测试用例，我也不知道哪里出问题了，知道的朋友还望告知一下。

func fib(n int64) int64 {
    return getFibNum(0, 1, n)
}
func getFibNum(first, second, n int) int {
    const mod int = 1e9 + 7 // leetcode要求
    if n < 2 {
        return n
    }
    if 2 == n {
        return first + second
    }
    return getFibNum(second, first+second, n-1)%mod
}

面试题10:二进制中1的个数

leetcode-cn.com/problems/er-jin-zh...
我这个道题也是按照人家的答案来实现的，想想大学时光的那些知识点全部忘的一干二净。刚好可以补充一下。

func hammingWeight(num uint32) int {
    var count = 0
    for ; num > 0; {
        count++
        num = (num - 1) & num//与操作，直接得出1的个数
    }
    return count
}

这就是第二章的练习题，也是基础的，如果有不会的，绝对要花时间去学习，研究，尤其是算法这个东西，又没有实际业务支撑的肯定很难学习一下的，全靠自律了，没时间也要挤时间。我问过类似的问题，大佬的回答是：少玩抖音，少玩游戏，时间自然就有了。共勉！！
第三章，研究的时间肯定会很长，因为每一道题都是自己敲会，不会就反复敲，十遍不行就二十遍，知道自己完全会了为止。

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