面试问题浓缩总结 面试问题浓缩总结
  • Go
  • Java
  • C/C++
  • JavaScript/HTML
  • MySQL
  • Redis
  • MongoDB
  • 操作系统
  • 计算机网络
  • spring全家桶
  • mybatis
  • 中间件
  • 软件相关
  • 系统相关
  • 算法
  • 数据结构
  • 设计模式
  • CMU硕士经典100题
  • 剑指offer
  • 重点手撕代码
  • 程序员面试金典
  • 3月
  • 4月
  • 智力题
  • 业务问题
  • 一些技术
  • 安全相关
APP下载 (opens new window)
GitHub (opens new window)
  • Go
  • Java
  • C/C++
  • JavaScript/HTML
  • MySQL
  • Redis
  • MongoDB
  • 操作系统
  • 计算机网络
  • spring全家桶
  • mybatis
  • 中间件
  • 软件相关
  • 系统相关
  • 算法
  • 数据结构
  • 设计模式
  • CMU硕士经典100题
  • 剑指offer
  • 重点手撕代码
  • 程序员面试金典
  • 3月
  • 4月
  • 智力题
  • 业务问题
  • 一些技术
  • 安全相关
APP下载 (opens new window)
GitHub (opens new window)
  • 算法

  • 数据结构

  • 设计模式

  • CMU硕士经典100题

  • 剑指offer

    • 3-10
      • 03.数组中重复的数字
        • 解法一: 使用map来暂存位置信息
        • 解法二:使用排序
        • 解法三: 原地置换法
      • 04.二维数组中的查找(看)
        • 解法一: 使用类似于数的查找方法
      • 05.替换空格
        • 解法一:使用go的标准库
        • 解法二:直接遍历替换
      • 06.从尾到头打印链表
        • 解法一:使用递归
        • 解法二: 使用栈
      • 07.重建二叉树(看)
        • 解法一: 使用递归
        • 解法二 使用迭代
      • 09.用两个栈实现队列
        • 解法一 双栈法
      • 10. I-斐波那契数列
        • 解法一:动态规划
      • 10.II 青蛙跳台阶问题
        • 解法一 使用动态规划
    • 11-20
    • 21-30
    • 31-40
    • 41-50
    • 51-60
    • 61-70
  • 重点手撕代码

  • 程序员面试

  • CodeTop企业题库

  • 笔试题目

  • 算法和数据结构
  • 剑指offer
小游
2021-03-29

3-10

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

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

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

# 03.数组中重复的数字

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

image-20210329090222691

# 解法一: 使用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
}
1
2
3
4
5
6
7
8
9
10
11
12

# 解法二:使用排序

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

func findRepeatNumber2(nums []int) int {
   sort.Ints(nums)
   for k:=range nums{
      if nums[k]==nums[k+1] {
         return nums[k]
      }
   }
   return -1
}
1
2
3
4
5
6
7
8
9

# 解法三: 原地置换法

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

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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 04.二维数组中的查找(看)

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

image-20210329112127941

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

test

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

实际代码如下:

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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 05.替换空格

image-20210329114101647

# 解法一:使用go的标准库

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

# 解法二:直接遍历替换

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
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 06.从尾到头打印链表

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

image-20210329214000253

# 解法一:使用递归

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

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)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 解法二: 使用栈

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

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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

当然,可以使用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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 07.重建二叉树(看)

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

image-20210330084907631

# 解法一: 使用递归

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

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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 解法二 使用迭代

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

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

我们依次枚举前序遍历中除了第一个节点以外的每个节点。如果 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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

# 09.用两个栈实现队列

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

image-20210330095239838

# 解法一 双栈法

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

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)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

看一下官方给的题解吧,这题其实我完全没有必要把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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# 10. I-斐波那契数列

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

image-20210330144505060

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

# 解法一:动态规划

这题目的状态转移方程题目已经给出来了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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 10.II 青蛙跳台阶问题

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

image-20210330151401474

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

# 解法一 使用动态规划

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]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
编辑 (opens new window)
上次更新: 2021/03/30, 22:01:26
更加复杂的数据结构
11-20

← 更加复杂的数据结构 11-20→

Theme by Vdoing | Copyright © 2021-2021 小游
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式