前面那个CMU硕士100题大概知道了大致的算法和套路，目前还没时间去完善，下面的这个剑指offer我打算每道题都认真总结一下。。

题目链接：《剑指 Offer（第 2 版）》 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这里为了避免一页太长，所以就分为多个文件

03.数组中重复的数字

剑指 Offer 03. 数组中重复的数字 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

解法一： 使用map来暂存位置信息

第一个就是简单的，我们map来暂存位置信息

func findRepeatNumber1(nums []int) int {
   // 直接使用map
   count:=make(map[int]int)
   for _,v:=range nums{
      if _,ok:=count[v];ok {
         return v
      } else {
         count[v] = 1
      }
   }
   return -1
}

解法二：使用排序

我们可以使用排序，如果相邻位置相同，那么我们就知道是否重复了

func findRepeatNumber2(nums []int) int {
   sort.Ints(nums)
   for k:=range nums{
      if nums[k]==nums[k+1] {
         return nums[k]
      }
   }
   return -1
}

解法三： 原地置换法

最后一个就是使用原地置换方法

func findRepeatNumber(nums []int) int {
   // 特殊判断,这里我们要保证满足条件
   if nums == nil || len(nums) == 0 {
      return -1
   }
   for _, num := range nums {
      if num < 0 || num > len(nums)-1 {
         return -1
      }
   }
   // 遍历数组
   for i := 0; i < len(nums); i++ {
      if i != nums[i] {
         if nums[i] == nums[nums[i]] {
            return nums[i]
         }
         // 交换这两个元素的位置，这个地方是关键，我们可以这样理解，就是如果数组里面有重复的元素
         // 那么nums[i]就必然会有多个相同的值，这里我们交换是为了判断
         nums[i], nums[nums[i]] = nums[nums[i]], nums[i]
      }
   }
   return -1
}

04.二维数组中的查找（看）

剑指 Offer 04. 二维数组中的查找 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这题可以巧妙的看成树的查找

解法一： 使用类似于数的查找方法

实际代码如下：

func findNumberIn2DArray(matrix [][]int, target int) bool {
	// 简单过滤特殊情况
	if len(matrix)==0 || len(matrix[0])==0 {
		return false
	}
	n:=len(matrix[0])
	// i和j分别表示两个下标
	i:=len(matrix)-1;j:=0
	// for循环遍历
	for	i>=0 && j<n{
		// 判断当前这个点是否大于目标值，如果大于我们就需要缩小i
		if matrix[i][j] > target {
			i--
		} else if matrix[i][j] == target{
			return true
		} else {
			// 否则我们就需要增加j的值
			j++
		}
	}
	return false
}

05.替换空格

解法一：使用go的标准库

func replaceSpace(s string) string {
	return strings.ReplaceAll(s," ","%20")
}

解法二：直接遍历替换

func replaceSpace(s string) string {
   // 遍历所有字符串
   for i:=0;i<len(s);i++{
      // 如果字符串为空，那么我们就进行替换
      if string(s[i]) ==" " {
         // 我们简单对字符串进行切片拼接
         s=s[:i]+"%20"+s[i+1:]
         //
         i+=2
      }
   }
   return s
}

06.从尾到头打印链表

剑指 Offer 06. 从尾到头打印链表 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

解法一：使用递归

（注意这个顺序很重要，我们需要先进度递归，然后再放值，如果反了的话就是顺序遍历了）

func reversePrint(head *ListNode) []int {
   data:=new([]int)
   reverse(data,head)
   return *data
}
// 使用辅助函数进行递归
func reverse(data *[]int,head *ListNode) {
   // 当头部为空时直接返回即可
   if head==nil {
      return
   }
   // 这里就是关键了，因为我们是需要反过来遍历的
   // 所以其实我们这里就是先递归到链表终点
   reverse(data,head.Next)
   // 然后我们再把当前值放入数组中
   *data=append(*data,head.Val)
}

解法二： 使用栈

思路就是把数据压入栈中，然后我们不断从栈顶弹出数据

func reversePrint(head *ListNode) []int {
   // 新建一个栈
   stack:=Stack{}
   // 遍历这个链表，把数据压入栈中
   for head!=nil {
      stack.Push(head.Val)
      head=head.Next
   }
   // 遍历栈，把所有的数据弹出，并放入数组
   data:=make([]int, len(stack.data))
   i:=0
   for !stack.Empty() {
       data[i] = stack.Pop()
       i++
   }
   // 返回数据
   return data
}
type Stack struct {
   i   int
   data []int
}
func (s *Stack) Push(k int)  {
   s.data = append(s.data, k)
   s.i = len(s.data)
}
func (s *Stack) Pop() (x int){
   x = s.data[s.i-1]
   s.i--
   return
}
func (s *Stack) Empty() bool {
   return s.i <= 0
}

当然，可以使用go的容器类，下面这个就简化了好多

func reversePrint(head *ListNode) []int {
   // 新建一个栈
   stack:=list.New()
   // 遍历这个链表，把数据压入栈中
   for head!=nil {
      stack.PushFront(head.Val)
      head=head.Next
   }
   // 遍历栈，把所有的数据弹出，并放入数组
   var data []int
   for e := stack.Front(); e != nil; e = e.Next() {
      data = append(data, e.Value.(int))
   }
   // 返回数据
   return data
}

07.重建二叉树（看）

剑指 Offer 07. 重建二叉树 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

解法一： 使用递归

巧妙利用二叉树遍历的性质，因为前序遍历的第一个值一定是根节点，然后后序遍历是左子树，中子树，然后再是右子树，所以我们知道根节点的话，就知道左右子树分别是那些了，然后根据这个规律进行递归，代码如下

func buildTree(preorder []int, inorder []int) *TreeNode {
   if len(preorder) == 0 {
      return nil
   }
   // 创建根节点，注意前序遍历的第一个一定是根节点
   root := &TreeNode{preorder[0], nil, nil}
   i := 0
   // 从前序序列中去找，找到后序遍历的根节点
   for ; i < len(inorder); i++ {
      if inorder[i] == preorder[0] {
         break
      }
   }
   // 前面我们找到了后续遍历的根节点，那么根节点前面的都是左子树，后面的是右子树
   // 这样我们就可以重建这棵二叉树了
   root.Left = buildTree(preorder[1:i+1],inorder[:i])
   root.Right = buildTree(preorder[i+1:],inorder[i+1:])
   return root
}

解法二 使用迭代

这个比较难理解，所以我直接贴上官方的题解：

我们用一个栈和一个指针辅助进行二叉树的构造。初始时栈中存放了根节点（前序遍历的第一个节点），指针指向中序遍历的第一个节点；

我们依次枚举前序遍历中除了第一个节点以外的每个节点。如果 index 恰好指向栈顶节点，那么我们不断地弹出栈顶节点并向右移动 index，并将当前节点作为最后一个弹出的节点的右儿子；如果 index 和栈顶节点不同，我们将当前节点作为栈顶节点的左儿子；无论是哪一种情况，我们最后都将当前的节点入栈。

func buildTree(preorder []int, inorder []int) *TreeNode {
   if len(preorder) == 0 {
      return nil
   }
   // 创建一个根节点
   root := &TreeNode{preorder[0], nil, nil}
   // 初始化一个栈
   stack := []*TreeNode{}
   // 先把根节点放入栈中
   stack = append(stack, root)
   var inorderIndex int
   // 遍历一下前序遍历的节点
   for i := 1; i < len(preorder); i++ {
      // 获取前序遍历节点的值
      preorderVal := preorder[i]
      // 然后我们也获取一下栈顶的元素
      node := stack[len(stack)-1]
      // 当我们当前节点的值不等于中序遍历的节点时（此时节点是左子树）
      if node.Val != inorder[inorderIndex] {
         node.Left = &TreeNode{preorderVal, nil, nil}
         stack = append(stack, node.Left)
      } else {
         // 这里就是当前节点的值等于中序遍历节点的值
         // 此时当前节点就是根节点，但是我们不需要根节点，我们需要右子树
         // 所以这里我们就是在不断出栈，找到不等于根节点的值，此时这个节点就是右节点
         for len(stack) != 0 && stack[len(stack)-1].Val == inorder[inorderIndex] {
            node = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            inorderIndex++
         }
         node.Right = &TreeNode{preorderVal, nil, nil}
         stack = append(stack, node.Right)
      }
   }
   return root
}

09.用两个栈实现队列

剑指 Offer 09. 用两个栈实现队列 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

解法一 双栈法

下面这个是个人解法，感觉不够优雅。。

type CQueue struct {
   // stack表示队尾
   stack1 list.List
   // stack表示队头
   stack2 list.List
}


func Constructor() CQueue {
   return CQueue{}
}


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


func (this *CQueue) DeleteHead() int {
   // 先判断栈是否为空
   if this.stack1.Len() == 0 {
      return -1
   }
   // 先把stack1里的元素全部移动到stack2
   for this.stack1.Len() !=0 {
      this.stack2.PushBack(this.stack1.Back().Value)
      // 然后我们移除顶部元素
      this.stack1.Remove(this.stack1.Back())
   }
   // 移除顶部元素
   element:=this.stack2.Back().Value
   this.stack2.Remove(this.stack2.Back())
   // 此时我们完成了删除操作,把stack2的元素全部放入stack1
   for this.stack2.Len() !=0 {
      this.stack1.PushBack(this.stack2.Back().Value)
      // 然后我们移除顶部元素
      this.stack2.Remove(this.stack2.Back())
   }
   return element.(int)
}

看一下官方给的题解吧，这题其实我完全没有必要把stack1的元素放入stack2后再重新放进去的。

其实我们只需要一批一批的放入stack2中即可（我们加直接放入stack1，然后删除的话就删除stack2的），因为stack2的顺序是队头顺序，所以我们必须要先把stack2中的元素删除完，才能从stack1中重新获取一次

type CQueue struct {
   // stack表示队尾
   stack1 *list.List
   // stack表示队头
   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 {
      return this.stack2.Remove(this.stack2.Back()).(int)
   }
   return -1
}

10. I-斐波那契数列

剑指 Offer 10- I. 斐波那契数列 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

注意这题目不能用递归，一用递归就会超时，所以我们只能用动态规划

解法一：动态规划

这题目的状态转移方程题目已经给出来了F(N) = F(N - 1) + F(N - 2), 其中 N > 1，同时为了节省空间，可以直接使用两位来进行简单替代

func fib(n int) int {
   // 这题使用动态规划
   // 我们让a为n-2，然后b表示n-1
   //(其实一开始a表示0 b表示1，所以我们最后计算的时候直接输出a就可以了)
   a:=0;b:=1;sum:=0
   for i := 0; i < n; i++ {
      // 因为题目规定要取模计算，所以我们进行取模
      sum = (a+b)%(1e9+7)
      // 然后更新一下(n-2 和 n-1)
      a = b
      b = sum
   }
   // 因为我们要计算第n项，一开始我们a表示0，所以最后我们只需要输出a即可
   return a
}

10.II 青蛙跳台阶问题

剑指 Offer 10- II. 青蛙跳台阶问题 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这题就是爬楼梯问题，使用动态规划求解，而且这题，和上面的基本上是一样的，就是换一下初始条件就行

解法一 使用动态规划

func numWays(n int) int{
   if n <= 1 {
      return 1
   }
   // 为了简单直观，先用dp数组
   dp:=make([]int,n+1)
   // 因为我们需要两个初始条件，所以需要先初始化
   dp[1]=1
   dp[2]=2
   // 这个题目用动态规划来做，所以我们只需要实现状态转移方程就行了
   for i := 3; i <= n; i++ {
      dp[i] = (dp[i-1] + dp[i-2])%(1e9+7)
   }
   return dp[n]
}

一般像这种题目根本不需要这么多空间的，我们完全可以进行优化。使用两个空间就可以完成计算了

func numWays(n int) int{
   if n <= 1 {
      return 1
   }
   // 我们使用a代表第0级，b代表第1级,sum表示总可能数
   a:=1;b:=1;sum:=0
   // 下面我们就可以计算各级的情况了
   for i := 2; i <= n; i++ {
      // 下面这部分没啥好说的，其实就是当前情况等于n-2+n-1这两个和
      sum = (a+b)%(1e9+7)
      a = b
      b = sum

   }
   return sum
}