牛课网 剑指 Offer 题解
记录刷牛课网 剑指 Offer 的过程。 主要语言 Golang
基本概念
树
…
图
…
题目
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))