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

总结