牛课网 剑指 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))

总结