面试问题浓缩总结
小游
2021-03-29

11-20

# 11.旋转数组最小的数字（看）

剑指 Offer 11. 旋转数组的最小数字 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210330153515237

# 解法一 二分查找

这题目主要还是考理解，下面简单介绍一下原理，旋转数组如下图所示，我们可以把旋转数组简单的分为左排序数组和右排序数组，我们要找的最小值其实就是右排序数组的第一个，也就是旋转点

Picture1.png

那么我们怎么找这个点呢？首先找中间值，然后进行比较，我们可以得出下面这样的结论（可以自己画图证明）

image-20210330161401610

然后就是为什么 j =j - 1 是正确的（缩小区间安全性），证明如下

image-20210330161622781

当然，为了方便，我们可以直接把这个结论背下来就行了~

func minArray(numbers []int) int {
   // 获取high和low两个指针
   low := 0
   high := len(numbers) - 1
   // 当low等于high时，我们退出循环，并且返回low指针
   // 注意推荐使用这种解法
   for low < high {
      // 尽量不要使用 (high+low)/2
      // 下面这种方法可以避免溢出的问题
      mid := low + (high - low) / 2
      // 当mid小于high时，旋转点一定会在 [low,mid] 这个区间内（关键）
      if numbers[mid] < numbers[high] {
         high = mid
      } else if numbers[mid] > numbers[high] {
          // 当mid大于high 时，旋转点一定在 [mid+1,high]区间内(关键)
         low = mid + 1
      } else {
         // 如果发现相等，那么缩小high指针
         high--
      }
   }
   // 最后我们的low即为计算结果
   return numbers[low]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 12.矩阵中的路径（看）

剑指 Offer 12. 矩阵中的路径 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210330162205754

# 解法一 使用DFS加回溯

这题我差点做对了，唉~我没有考虑到路径走过后不能再走一遍，而且还巨傻不用递归，而是一个一个遍历，看了别人的答案后恍然大悟

func exist(board [][]byte, word string) bool {
   if len(board) == 0 || len(board[0]) == 0 || len(word) == 0 {
      return false
   }
   // 判断大小
   m,n:=len(board),len(board[0])
   for i:=0;i<m;i++ {
      for j:=0;j<n;j++ {
         if dfs(board,i,j,0,word) {
            return true
         }
      }
   }
   return false
}

func dfs(board [][]byte,i int,j int,k int,word string) bool  {
   // 判断i，j是否合法
   if i>=len(board) || i<0 || j>=len(board[0]) || j<0 || board[i][j]!=word[k]{
      return false
   }
   // 判断当前位数是否等于字符串的位数
   if k == len(word)-1 {
      return true
   }
   // 我们把当前这位置为0表示我们访问过了
   board[i][j] = 0
   // 然后我们进行上下左右遍历
   res:=dfs(board,i-1,j,k+1,word) || dfs(board,i,j-1,k+1,word) || dfs(board,i+1,j,k+1,word) || dfs(board,i,j+1,k+1,word)
   // 没有的话，我们在进行回溯
   board[i][j] = word[k]
   return res
}
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

# 13.机器人运动范围（看）

剑指 Offer 13. 机器人的运动范围 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210330194801322

唉，我以为我会做，然而还是不行。。看来自己还得多学习学习。。。先说一下数位之和的计算

可以使用循环求和的方法

int sums(int x){
	int s = 0;
    while(x != 0) {
        s += x % 10;
        x = x / 10;
    }
    return s;
}
1
2
3
4
5
6
7
8

也可以通过数位和的增量公式

image-20210330203203947

此题可以证明机器人只需要向右或者向下移动就可以访问所有的可达解

# 解法一 DFS

// 定义全局变量
var n1, m1, k1 int
var visited [][]bool

func movingCount(m int, n int, k int) int {
   m1 = m
   n1 = n
   k1 = k
   // 初始化访问数组
   visited = make([][]bool, m)
   for i := 0; i < len(visited); i++ {
      visited[i] = make([]bool, n)
   }
   // dfs遍历
   return dfs(0, 0, 0, 0)
}

// si和sj分别表示位数之和
func dfs(i int, j int, si int, sj int) int {
   if i >= m1 || j >= n1 || si+sj > k1 || visited[i][j] {
      return 0
   }
   // 标记为访问状态
   visited[i][j] = true
   // sj1表示往右走
   sj1 := sj + 1
   // sj1表示往下走
   si1 := si + 1
   // 这个是一个增量公式，可以快速计算位数和
   if (j+1)%10 == 0 {
      sj1 = sj - 8
   }
   if (i+1)%10 == 0 {
      si1 = si - 8
   }
   // 然后把所有的情况都加起来就是机器人能到达的范围了
   return 1 + dfs(i, j+1, si, sj1) + dfs(i+1, j, si1, sj)
}
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

# 解法二 BFS

BFS也叫广度优先遍历，前面我们的深度优先遍历使用递归的方式来实现，这里我们的BFS则使用栈来实现，不过效率没有深度优先那么高。实际代码如下

func movingCount(m int, n int, k int) int {
   // 初始化一个队列
   queue := list.List{}
   // 初始化访问数组
   visited := make([][]bool, m)
   // 数据开辟空间
   for i := 0; i < len(visited); i++ {
      visited[i] = make([]bool, n)
   }
   // 队列里面放入四个初始值（分别代表i j si sj这四个位置）
   queue.PushBack([]int{0, 0, 0, 0})
   res := 0
   // 当我们队列长度等于0时退出循环
   for queue.Len() > 0 {
      // 获取队列顶的元素
      bfs := queue.Remove(queue.Back()).([]int)
      // 赋值
      i := bfs[0]
      j := bfs[1]
      si := bfs[2]
      sj := bfs[3]
      // 先判断当前值是否符合条件
      if i >= m || j >= n || si+sj > k || visited[i][j] {
         continue
      }
      // 步数+1，设置当前位置访问
      res++
      visited[i][j] = true
      // 计算右下两个位置
      sj1 := cal(j,sj)
      si1 := cal(i,si)
      // 把我们遍历的点放入栈中
      queue.PushBack([]int{i + 1, j, si1, sj})
      queue.PushBack([]int{i, j + 1, si, sj1})
   }
   return res
}
// 计算数位和
func cal(i int, n int) int {
	if (i+1)%10 == 0 {
		return n - 8
	} else {
		return n + 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
35
36
37
38
39
40
41
42
43
44
45

# 14.I 剪绳子（看）

剑指 Offer 14- I. 剪绳子 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210331085703934

害，我太难了，我想用递归，一直在找递归条件，但就是找不到，我吐了啊。。。。直接看大佬的题解

# 解法一 数学推导（贪心思想）

这解法我是真的没想到。。。。，至于原理看大佬证明吧，我懒得解释了

面试题14- I. 剪绳子（数学推导 / 贪心思想，清晰图解） - 剪绳子 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210331092635083

func cuttingRope(n int) int {
   if n <= 3 {
      return n-1
   }
   a:=n/3
   b:=n%3
   if b == 0 {
      return int(math.Pow(3,float64(a)))
   }
   if b == 1 {
      return int(math.Pow(3,float64(a-1)))*4
   }
   return int(math.Pow(3,float64(a)))*2
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 解法二 递归

。。。。。服了，我一直都在想怎么用递归，结果一看大佬的解答，我感觉自己就是个菜鸡

这题其实是有规律的，当 n>6 时，ans(n) = ans(n-3) x 3，其余情况我们直接返回对应的值即可。。。

func cuttingRope(n int) int {
   switch n {
   case 2:
      return 1
   case 3:
      return 2
   case 4:
      return 4
   case 5:
      return 6
   case 6:
      return 9
   default:
      return cuttingRope(n-3) * 3 % 1000000007
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 解法三 动态规划

还是动态规划最清晰明了，具体的题解如下所示

func cuttingRope(n int) int {
   dp:=make([]int,n+1)
   // 设置dp的初始条件
   dp[2] = 1
   // 我们从3开始进行遍历计算
   for i := 3; i <= n; i++ {
      // 因为我们需要找出一个最大值，所以我们需要遍历dp数组，找出最大的值
      for j := 2; j < i; j++ {
         // 最大的值可能有下面三种情况
         // 1是自己本身就是最大的
         // 2是j*(i-j) 这两段相乘最大
         // 3是j*dp[i-j] 达到最大（i-j这段继续分的最大值）
         dp[i] = max(dp[i],max(j*(i-j),j*dp[i-j]))
      }
   }
   return dp[n]
}

func max(i, j int) int {
   if i > j {
      return i
   }
   return j
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 14.II 剪绳子II (看)

剑指 Offer 14- II. 剪绳子 II - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210331110020574

这题乍一看好像和上题一样，但是注意，不能使用动态规划，因为答案要取模，取模之后我们就无法进行比较大小了，所以需要使用其他的方法，这里就不写了

# 15.二进制中1的个数

剑指 Offer 15. 二进制中1的个数 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210331110928389

哈哈，这题居然被我做出来了，其实思路不难，就是进行简单的位运算，如果了解位运算的就很简单，这里我就不解释了

# 解法一 使用位运算

func hammingWeight(num uint32) int {
   res:=0
   // 这题其实
   for num > 0 {
      // 使用位运算，如果最低位为1那么和1相与后就为1，否则就为0
      res += int(num & 1)
      // 把数字往左移
      num>>=1
   }
   return res
}
1
2
3
4
5
6
7
8
9
10
11

# 16.数的整数次方（看）

剑指 Offer 16. 数值的整数次方 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210331112428236

这题我本来想暴力的，没想到时间超限了QAQ。。没办法只能看大佬的题解了

# 解法一 快速幂

Picture1.png

这东西就是数学规律，太难了。。。

func myPow(x float64, n int) float64 {
   if x == 0 {
      return 0
   }
   var res = float64(1)
   // 当n为负数时,我们就翻转一下
   if n < 0 {
      x = 1/x
      n=-n
   }
   // 进行位运算操作
   for n > 0 {
      if n & 1 == 1 {
         res *= x
      }
      x*=x
      n>>=1
   }
   return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 17.打印从1到最大的n位数

剑指 Offer 17. 打印从1到最大的n位数 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210331150549417

。。。我就说怎么可能这么简单，这道题目需要考虑大数问题，即需要考虑数组越界的问题。。所以实际情况下我们需要返回字符串而不是int数组，这里先发一下最简单的暴力算法

func printNumbers(n int) []int {
   // 先获取对应容量
   target:=int(math.Pow(10,float64(n)))
   data:=make([]int,target-1)
   for i := 0; i < target-1; i++ {
      data[i] = i+1
   }
   return data
}
1
2
3
4
5
6
7
8
9

# 解法一： 分治递归思想

// 解法二 分治递归法
var nine = 0
var start,n1 int
var num []byte
var loop = []byte{'0','1','2','3','4','5','6','7','8','9'}
var res  []byte
func printNumbers(n int) string{
   n1 = n
   // 为了避免字符串出现0的问题，我们需要使用start来进行截取
   start = n-1
   // 初始化num数组，用于存放数据
   num=make([]byte,n)
   // 从第0位开始进行遍历
   dfs(0)
   // 最后返回的时候记得把逗号去掉
   return string(res[:len(res)-1])
}

func dfs(x int) {
   // 当x等于n1的时候我们就打印完毕，可以跳出循环了
   if x == n1 {
      // 转换的时候注意字符串截取
      s:=string(num[start:])
      // 当我们的s不为0时才把数据加进去
      if s != "0" {
         res = append(res,s...)
         res = append(res,',')
      }
      // 这里表示我们的数字进了一位
      if n1-start == nine {
         start --
      }
      return
   }
   // 遍历一下loop数组
   for _,v:=range loop{
      // 当v为9时，我们就需要进一位
      if v == '9' {
         nine++
      }
      // 设置当前位数（因为前面几位都是固定的，所以我们只需要设置x位）
      num[x] = v
      // 计算下一位
      // 这里我们需要遍历9次
      dfs(x+1)
   }
   nine --
}
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
41
42
43
44
45
46
47
48

# 18.删除链表的节点

剑指 Offer 18. 删除链表的节点 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210331155822103

# 解法一 遍历法

这个方法就是简单进行遍历，然后找到待删除节点的前一个节点即可，找到后我们删除这个节点就可以了

func deleteNode(head *ListNode, val int) *ListNode {
   root:=head
   pre:=head
   // 找到要删除节点的前一个节点
   for head !=nil && head.Val != val {
      pre = head
      head = head.Next
   }
   // 判断是否为根节点
   if root.Val == val {
      return root.Next
   }
   // 如果不是那么就把节点删除即可
   if head != nil {
      pre.Next = pre.Next.Next
   }
   return root
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 19.正则表达式匹配（跳过）

剑指 Offer 19. 正则表达式匹配 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210331160403614

这题我只想说一句，打扰了。。。。先暂时跳过吧。。。

# 解法一： 动态规划

func isMatch(s string, p string) bool {
    m, n := len(s), len(p)
    matches := func(i, j int) bool {
        if i == 0 {
            return false
        }
        if p[j-1] == '.' {
            return true
        }
        return s[i-1] == p[j-1]
    }

    f := make([][]bool, m + 1)
    for i := 0; i < len(f); i++ {
        f[i] = make([]bool, n + 1)
    }
    f[0][0] = true
    for i := 0; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if p[j-1] == '*' {
                f[i][j] = f[i][j] || f[i][j-2]
                if matches(i, j - 1) {
                    f[i][j] = f[i][j] || f[i-1][j]
                }
            } else if matches(i, j) {
                f[i][j] = f[i][j] || f[i-1][j-1]
            }
        }
    }
    return f[m][n]
}
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

# 20.表示数值的字符串

剑指 Offer 20. 表示数值的字符串 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210404160904601

# 解法一：有限状态机

这题涉及到知识盲区了。。不过呢，这题还是很有意思的，非常巧妙的使用到了状态转移这个东西，可惜唯一的问题就是这个转移方程太难了写吧。。。。。

Picture1.png

func isNumber(s string) bool {
   // 状态值
   states:=[]map[byte]int{
      {' ':0,'s':1,'d':2,'.':4},
      {'d':2,'.':4},
      {'d':2,'.':3,'e':5,' ':8},
      {'d':3,'e':5,' ':8},
      {'d':3},
      {'s':6,'d':7},
      {'d':7},
      {'d':7,' ':8},
      {' ':8},
   }
   p:=0
   var t byte
   for _,c:=range s{
      // 这里是判断当前字符串是属于什么类型
      if c >= '0' && c<='9' {
         t = 'd'
      } else if c=='+' || c=='-' {
         t = 's'
      } else if c=='e' || c=='E' {
         t = 'e'
      } else if c=='.' || c == ' '{
         t = byte(c)
      } else {
         t = '?'
      }
      // 如果当前状态不存在，那么就返回false
      if _,ok:=states[p][t];!ok {
         return false
      }
      // 进行状态转移
      p = states[p][t]
   }
   return p==2 || p==3 || p==7 || p==8
}
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
编辑 (opens new window)
上次更新: 2021/04/06, 22:01:45
3-10
21-30

← 21-30→

Theme by Vdoing | Copyright © 2021-2021 小游