牛课网 剑指 Offer 题解

记录刷牛课网 剑指 Offer 的过程。 主要语言 Golang

• Markdown 符号
• emoji
• 题目地址

基本概念

树

…

图

…

题目

JC0.Demo

题目描述

Demo

• 难度 Easy
• 考察点 数组 二分查找
• 说明 Demo

案例

输入: x = true
输出: true

约束条件

…

题解 1: 暴力算法

(\sum_{k=1}^N k^2)

• 分析: Demo

• Code

  func Solution(x bool) bool {
  	return x
  }
  

• 复杂度:

  • 时间复杂度: O((1))
  • 空间复杂度: O((1))

JC1.二维数组中的查找

题目描述

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

• 难度 Easy
• 考察点 数组 二分查找
• 说明 这是一道对二维数组进行二分查找的算法，考察对二分查找的灵活运用。

案例

输入:
arr =
    []int{1, 2, 8, 9},
    []int{2, 4, 9, 12},
    []int{4, 7, 10, 13},
    []int{6, 8, 11, 15},

target = 7

输出: true

题解 1: 暴力算法

• 分析: 直接遍历一遍数组，即可判断目标 target 是否存在。

• Code

  func Find(board [][]int, target int) bool {
  	rlen := len(board)
  	clen := len(board[0])
  	//  从右上角的元素找起来
  	for r, c := 0, clen-1; r < rlen && c >= 0; {
  		if board[r][c] == target {
  			return true
  		}
  		if board[r][c] > target {
  			c--
  		} else {
  			r++
  		}
  	}
  	return false
  }
  

• 复杂度:

  • 时间复杂度: O((N^2))
  • 空间复杂度: O((1))

JC2.替换空格

题目描述

请实现一个函数，将一个字符串中的每个空格替换成“%20”。 例如，当字符串为 We Are Happy 则经过替换之后的字符串为 We%20Are%20Happy

• 难度 Easy
• 考察点 字符串
• 说明 简单的字符串操作题目

案例

输入: x = true
输出: true

题解 1: 逆向遍历

• 分析: 由给出的方法可知，函数没有返回值，虽有只能再原来的字符串上操作。遍历一般有由左向右、由右向左 2 种遍历。
  • 由左向右: 发现空格填充的话会将后面的字符覆盖掉，此方法不行。
  • 由右向左: 遇到空格填充 20%, 否则正常填充字符串。

• Code

  func replaceSpace(str []byte) []byte {
  	count, length := 0, len(str)
  	// 遍历一遍字符串， 统计字符出现的数目, 计算替换后的字符串长度
  	for i := 0; i < length; i++ {
  		if str[i] == ' ' {
  			count++
  		}
  	}
  	newLength := length + count*2
  	//	扩容数组
  	str = append(str, make([]byte, count*2)...)
  	// 两个index，一个指向length-1, 另一个指向newLength-1，遍历一遍字符串，完成替换
  	for l, nl := length-1, newLength-1; l >= 0 && nl >= 0; {
  		if str[l] == ' ' {
  			str[nl] = '0'
  			nl--
  			str[nl] = '2'
  			nl--
  			str[nl] = '%'
  			nl--
  		} else {
  			str[nl] = str[l]
  			nl--
      }
      l--
  
  	}
  	return str
  }
  

• 复杂度:

  • 时间复杂度: O((N))
  • 空间复杂度: O((1))

JC3.从头到尾打印链表

题目描述

输入一个链表，按链表从尾到头的顺序返回一个数组

• 难度 Easy
• 考察点 琏表 递归 翻转琏表
• 说明 琏表操作的入门题目

案例

输入: *NodeList{}
输出: []int{3, 2, 1}

题解 1: 递归

• 分析: 借助二叉树的递归遍历可以很容易的写出递归遍历琏表

• Code

  func printListFromTailToHead(head *NodeList) []int {
  	ans := make([]int, 0)
  	if head == nil {
  		return ans
  	}
  	ans = printListFromTailToHead(head.Next)
  	ans = append(ans, head.Val)
  
  	return ans
  }
  

• 复杂度:

  • 时间复杂度: O((N))
  • 空间复杂度: O((N))

题解 2: 多指针遍历

• 分析: 借助多个指针翻转琏表

• Code

  func printListFromTailToHead2(head *NodeList) []int {
  	pre, cur, next, ans := &NodeList{}, head, head.Next, []int{}
  
  	for cur != nil {
  		next = cur.Next
  		cur.Next = pre
  
  		pre = cur
  		cur = next
  	}
  
  	for pre.Next != nil {
  		ans = append(ans, pre.Val)
  		pre = pre.Next
  	}
  
  	return ans
  }
  

• 复杂度:

  • 时间复杂度: O((N))
  • 空间复杂度: O((N))

总结