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

51-60

# 51.数组中的逆序对

剑指 Offer 51. 数组中的逆序对 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210409085738057

这困难题先跳过吧，实在是把我刷累了

# 52.两个链表的第一个公共节点、

剑指 Offer 52. 两个链表的第一个公共节点 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210409085910052

害，看来我果然只会做简单题。。。

# 解法一：使用map暂存数据

这个方法比较简单，这里就不详细解释了

func getIntersectionNode(headA, headB *ListNode) *ListNode {
   dic:=make(map[*ListNode] bool)
   // 首先我们遍历第一个节点，把节点所有的值全部放入map中
   for headA!=nil {
      dic[headA] = true
      headA=headA.Next
   }
   // 第二次遍历headB
   for headB!=nil {
      if _,ok:=dic[headB];ok{
         return headB
      }
      headB=headB.Next
   }
   return nil
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 解法二： 双指针

这个解法就很巧妙了，两个指针分别从头开始进行遍历，然后两个节点走到头时会从另一个节点开始继续遍历。

可以这样理解：两个链表长度分别为L1+C、L2+C， C为公共部分的长度，按照楼主的做法： 第一个人走了L1+C步后，回到第二个人起点走L2步；第2个人走了L2+C步后，回到第一个人起点走L1步。 当两个人走的步数都为L1+L2+C时就会相遇，如果没有公共的点，那么两个链表各走完一轮后就都为空，然后退出循环

func getIntersectionNode(headA, headB *ListNode) *ListNode {
   a:=headA;b:=headB
   for a != b {
      if a != nil { a=a.Next } else { a=headB }
      if b != nil { b=b.Next } else { b=headA }
   }
   return a
}
1
2
3
4
5
6
7
8

# 53 I.在排序数组中查找数字 I

剑指 Offer 53 - I. 在排序数组中查找数字 I - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210409091432966

# 解法一： 二分查找

因为我们的数组是有序的，所以我们就可以可以使用二分查找来加快查找速度，当然因为我们需要统计一下出现的次数，所以我们还需要向前和向后遍历

func search(nums []int, target int) int {
   // 我们使用二分查找查找数据
   low:=0;high:=len(nums)-1;count:=0
   // 当low大于high时退出循环
   for low <= high {
      // 计算中点
      mid:=low+(high-low)/2
      // 下面这个是二分查找的步骤，我这里就不多说了
      if nums[mid] > target {
         high = mid-1
      } else if nums[mid] < target {
         low = mid+1
      } else {
         // 当我们找到是，因为我们要统计出现的次数
         t:=mid
         count=1
         // 所以我们需要向前和向后遍历
         t++
         mid--
         for t<len(nums) && nums[t] == target { count++;t++ }
         for mid>=0 && nums[mid] == target { count++;mid-- }
         return count
      }
   }
   return count
}
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

# 53 II.0~n-1中缺失的数字

剑指 Offer 53 - II. 0～n-1中缺失的数字 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210409093028502

# 解法一： 二分查找

func missingNumber(nums []int) int {
   low:=0;high:=len(nums)-1
   for low <= high {
      mid:=low+(high-low)/2
      if nums[mid] == mid {
         low = mid+1
      } else if nums[mid] > mid {
         // 如果前一个是相等的，那么缺失的就是当前这个啦
         if mid!=0 && nums[mid-1] == mid - 1 {
            return mid
         }
         // 否则我们再缩小一下范围
         high = mid-1
      }
   }
   // 如果没找到，那么要么是缺失首部，要么是缺失尾部
   if nums[0] != 0 {
      return 0
   } else {
      return len(nums)
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

哈哈，虽然测试通过了，但是看了一下大佬的，发现自己的代码不够优雅，大佬的解法果然牛逼

func missingNumber(nums []int) int {
   low:=0;high:=len(nums)-1
   for low <= high {
      mid:=low+(high-low)/2
      if nums[mid]==mid {
         low = mid+1
      } else {
         high = mid-1
      }
   }
   return low
}
1
2
3
4
5
6
7
8
9
10
11
12

# 54.二叉搜索树的最K大节点

剑指 Offer 54. 二叉搜索树的第k大节点 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210409100208021

害，只有一些简单的思路，这题说到底还是自己对递归的不熟悉

# 解法一： 反向中序遍历

根据我们二叉搜索树的定义，右边的会比根节点大，左边的比根节点小我们是找第K大的节点，所以我们可以先进行方向中序遍历，然后找出那个值。具体代码如下

var res = 0
var n int

func kthLargest(root *TreeNode, k int) int {
   n = k
   // 开始遍历dfs
   dfs(root)
   return res
}

// dfs深度遍历
func dfs(root *TreeNode)  {
   // 如果节点为空，那么就直接返回
   if root == nil {
      return
   }
   // 从右节点开始遍历
   dfs(root.Right)
   // n--操作，这里相当于在统计
   n--
   // 如果n变成0了，说明我们找到第k个最大的数了，这个时候我们直接设置结果
   if n==0 { res = root.Val }
   // 然后遍历左子树
   dfs(root.Left)
}
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

# 55.I 二叉树的深度

剑指 Offer 55 - I. 二叉树的深度 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210409105011205

# 解法一： 递归

哈哈哈，瞥了一眼大佬的题解，发现居然这么简单。。。

func maxDepth(root *TreeNode) int {
   if root == nil {
      return 0
   }
   return max(maxDepth(root.Left),maxDepth(root.Right))+1
}

func max(a int,b int) int {
   if a > b {
      return a
   } else {
      return b
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 解法二：BFS

我们可以使用BFS来进行层次遍历

func maxDepth(root *TreeNode) int {
   if root==nil {
      return 0
   }
   queue:=list.New()
   count:=0
   // 先把根节点放入到队列中
   queue.PushBack(root)
   // 不断遍历队列直到出队
   for queue.Len() != 0 {
      // 不断遍历让队列出队
      size:=queue.Len()
      for size > 0 {
         // 每遍历一次 size就减一
         size--
         // 获取队头元素
         node:=queue.Remove(queue.Front()).(*TreeNode)
         // 判断头尾
         if node.Right != nil { queue.PushBack(node.Right) }
         if node.Left != nil { queue.PushBack(node.Left) }
      }
      count++
   }
   return count
}
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

# 55.II 平衡二叉树

剑指 Offer 55 - II. 平衡二叉树 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210409103947968

这题我觉得应该用二叉树的层次遍历来做，但是我没思路啊。。呜呜呜

# 解法一： 后序遍历+剪枝

看了一大佬的解法，这题其实不算特别难，我们要注意的地方就是在于怎么理解递归做了什么以及左右子树的高度差怎么计算

func isBalanced(root *TreeNode) bool {
   // 我们-1表示这棵树不是平衡二叉树
   return recur(root) != -1
}

// 声明一个辅助函数
func recur(root *TreeNode) int {
   if root == nil {
      return 0
   }
   // 分别遍历左右子树，获取左右子树的高度差
   left:=recur(root.Left)
   // 如果发现左子树的高度差为-1，说明不是平衡二叉树直接返回
   if left == -1 { return -1 }
   // 遍历右子树
   right:=recur(root.Right)
   // 如果发现左子树的高度差为-1，说明不是平衡二叉树直接返回
   if right == -1 { return -1 }
   // 然后我们判断一下左右子树的高度差
   if math.Abs(float64(left-right)) < 2 {
      // 小于2就说明在范围内，此时我们返回最深的数的高度
      return max(left,right)+1
   } else {
      return -1
   }
}

func max(a int,b int) int {
   if a > b {
      return a
   } else {
      return b
   }
}
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

# 解法二 ：先序遍历+判断深度

这个和上面的顺序是相反的，上面那个是自底向上进行遍历，而下面这个是从上往下进行遍历

func max(a int,b int) int {
   if a > b {
      return a
   } else {
      return b
   }
}

// 解法二 先序遍历
func isBalanced(root *TreeNode) bool {
   if root == nil {
      return true
   }
   // 首先我们要确保当前树的左右子树深度不超过2
   // 并且我们还要确保左右子树也是平衡二叉树
   return math.Abs(float64(depth(root.Left)-depth(root.Right)))<2 && isBalanced(root.Left) && isBalanced(root.Right)
}

// 判断二叉树的深度
func depth(root *TreeNode) int {
   if root == nil {
      return 0
   }
   // 递归左右子树，返回最大值
   left:=depth(root.Left)
   right:=depth(root.Right)
   // 返回最大深度
   return max(left,right)+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

# 56-I.数组中数字出现的次数

剑指 Offer 56 - I. 数组中数字出现的次数 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210409135011871

# 解法一： 暴力

这个是我能想到的最简单的方法了

func singleNumbers(nums []int) []int {
   // 最终结果
   var res []int
   data:=make(map[int]int)
   // 第一遍，统计出现的次数
   for _,v:=range nums{
      data[v]++
   }
   // 第二遍找出只出现一次的数
   for k,v:=range data{
      if v==1 {
         res = append(res, k)
      }
   }
   return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 解法二：分组异或

这种解法我觉得面试问题意义不大，纯粹属于数学技巧

func singleNumbers(nums []int) []int {
   ret:=0
   for _,v:=range nums{
      ret^=v
   }
   div:=1
   for div&ret == 0 {
      div<<=1
   }
   a,b:=0,0
   for _,v:=range nums{
      if (div & v) != 0 {
         a^=v
      } else {
         b^=v
      }
   }
   return []int{a,b}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 56-II.数组中数字出现的次数II（重）

剑指 Offer 56 - II. 数组中数字出现的次数 II - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210409141101655

这题我还是想着用暴力哈哈，不过这题目肯定是不能用暴力的，先暂时跳过。。。

# 方法一： 有限状态自动机

# 方法二：遍历统计

# 57.和为s的两个数组

剑指 Offer 57. 和为s的两个数字 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210409142040520

# 解法一： 双指针

func twoSum(nums []int, target int) []int {
   low,high:=0,len(nums)-1
   for low <= high {
      if nums[low]+nums[high] < target {
         low++
      } else if nums[low]+nums[high] > target  {
         high--
      } else {
         return []int{nums[low],nums[high]}
      }
   }
   return []int{}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 解法二：哈希表

这方法有是有用，但是效率太低，不如go的方法。。。。

func twoSum(nums []int, target int) []int {
   // 我们使用hash来暂存数据
   data:=make(map[int]int)
   // 遍历数组求值
   for i := 0; i < len(nums); i++ {
      a:=target-nums[i]
      // 判断在map中是否存在
      if _, ok := data[a]; ok {
         return []int{a,nums[i]}
      }
      // 把值存储进map中
      data[nums[i]] = i
   }
   return []int{}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 57-II.和为s的连续正数序列

剑指 Offer 57 - II. 和为s的连续正数序列 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210409142830800

这题虽然说是简单，但是我没思路。。。无奈只能看官方题解了

# 解法一： 暴力

暴力的思想很简单，就是我们从每个点开始往后遍历，找出所有符合条件的结果并放入到数组中

func findContinuousSequence(target int) [][]int {
   // res表示最最终结果
   var res [][]int
   // sum表示总数，然后limit表示我们从哪里结束（因为答案是至少两个连续序列，所以我们这里取一半就可以了）
   sum,limit:=0,(target)/2
   // 遍历
   for i := 1; i <= limit; i++ {
      for j := i; ; j++ {
         sum+=j
         // 当总和大于我们的目标值时，退出循环
         if sum > target {
            sum = 0
            break
         } else if sum == target{
            // 当sum等于我们的目标时，我们把结果加入数组中
            tmp:=make([]int,j-i+1)
            for k := i; k <= j; k++ {
               tmp[k-i] = k
            }
            // 我们添加当前结果
            res = append(res,tmp)
            sum = 0
            break
         }
      }
   }
   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

# 解法二： 双指针

我们可通过两个指针来指示位置，这样就不需要我们重复计算了

func findContinuousSequence(target int) [][]int{
   var res [][]int
   r:=2
   for l:=1;l<r; {
      // 区间求和公式
      sum:=(l+r)*(r-l+1)/2
      // 当sum等于target时，此时返回结果
      if sum == target {
         tmp:=make([]int,r-l+1)
         for i := l; i <= r; i++ {
            tmp[i-l] = i
         }
         res = append(res, tmp)
         l++
      } else if sum < target {
         r++
      } else {
         l++
      }
   }
   return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 解法三： 滑动窗口

思路如下

Picture2.png

func findContinuousSequence(target int) [][]int {
   low :=1;high :=2;s:=3
   var res [][]int
   for low < high {
      if s == target {
         tmp:=make([]int, high-low+1)
         for k := low; k <= high; k++ {
            tmp[k-low] = k
         }
         res = append(res, tmp)
      }
      if s >= target {
         s-= low
         low++
      }else{
         high++
         s+= high
      }
   }
   return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 58-I.翻转单词顺序

剑指 Offer 58 - I. 翻转单词顺序 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210409165023627

# 解法一：双指针

func reverseWords(s string) string {
   // 我们使用数组来暂存单词
   var words []string
   // 开始进行查找
   for i := 0; i < len(s); i++ {
      // 当不为空格时我们开始进行遍历
      if s[i] != ' ' {
         // 我们开始进行查找,直到遇到空格为止
         j:=i
         for j < len(s) && s[j] != ' ' { j++ }
         // 找到后我们把单词放入数组中
         words=append(words,s[i:j])
         i=j
      }
   }
   // 拼接字符串
   var ans bytes.Buffer
   for i:=len(words)-1;i>=0;i--{
      ans.Write([]byte(words[i] + " "))
   }
   var data = ans.String()
   // 去除最后的空格
   if len(data) != 0{
      data = data[:len(data)-1]
   }
   return data
}
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

不过我这个解法不够优雅，下面贴一下大佬的简化版

func reverseWords(s string) string {
   // 首先去除空格
   s=strings.TrimSpace(s)
   // 我们使用两个指针来暂存数据
   i:=len(s)-1
   j:=i
   // 使用bytes.Buffer加快拼接速度
   res:=bytes.Buffer{}
   for i >= 0 {
      // 首先找到第一个空格
      for i >= 0 && s[i] != ' ' { i-- }
      // 这个时候我们i和j之间就为一个单词
      res.Write([]byte(s[i+1:j+1]+" "))
      // 下面我们进行下一轮查找，我们这里跳过所有的空格
      for i >= 0 && s[i] == ' ' { i-- }
      // 更新一下j的位置，用于下一轮查找
      j=i
   }
   return strings.TrimSpace(res.String())
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 58-II. 左旋转字符串

剑指 Offer 58 - II. 左旋转字符串 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210409184326470

# 解法一： go字符串拼接

第一次看到用go的轻松解法了。。。不容易啊，不过呢，真正面试的时候肯定不能这样做的，咳咳

func reverseLeftWords(s string, n int) string {
   return s[n:]+s[:n]
}
1
2
3

# 解法二：列表遍历拼接

这里我们使用求余运算来进行简化，不过效果还是不咋地哈哈，还是go的切片好用

func reverseLeftWords(s string, n int) string {
   buffer:=bytes.Buffer{}
   for i := n; i < n+len(s); i++ {
      buffer.Write([]byte{s[i%len(s)]})
   }
   return buffer.String()
}
1
2
3
4
5
6
7

# 59.II 队列的最大值

剑指 Offer 59 - II. 队列的最大值 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210409185714180

# 解法一： 双向队列

这个理解起来可能有点困难，因为我们所有的操作的时间复杂度必须是1，所以我们考虑维护一个递减的队列（这个队列的头部其实就是我们队列中的最大值，然后后面就依次递减），然后有下面两种情况

  1. 当我们入队时： 我们只需从队尾开始，把所有小于当前值的全部移除（因为我们的队列是先进先出的，所以我们可以保证所有移除的元不可能是当前队列的最大值）

  2. 当我们出队时：如果当前元素时最大值，我们把递减队列的也移除，具体参考下面这个gif。如果图片失效，那么就看下面升解答

    如何解决 O(1) 复杂度的 API 设计题 - 队列的最大值 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

    fig3.gif

type MaxQueue struct {
   // 这里我们维护了一个正常的队列
   q []int
   // 这里我们则维护了一个递减的队列
   p []int
}

func Constructor() MaxQueue {
   return MaxQueue{}
}

func (this *MaxQueue) Max_value() int {
   // 当我们想获取最大值时
   if len(this.q) == 0 {
      return -1
   }
   // 这里我们可以直接返回递减的队列的第一个元素
   return this.p[0]
}

func (this *MaxQueue) Push_back(value int)  {
   // 正常队列我们可以直接加入
   this.q = append(this.q, value)
   // 这里我们把队尾小于v的元素全部弹出
   for len(this.p) > 0 && value > this.p[len(this.p) - 1] {
      this.p = this.p[: len(this.p) - 1]
   }
   // 然后把value插进来
   this.p = append(this.p, value)
}

func (this *MaxQueue) Pop_front() int {
   if len(this.q) == 0 {
      return -1
   }
   // 当我们出队是需要判断最大值是否为递减队列的最大致，如果是那么递减队列也移出
   if this.q[0] == this.p[0] {
      this.p = this.p[1:]
   }
   value := this.q[0]
   this.q = this.q[1:]
   return value
}
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

# 60.n个骰子的点数

剑指 Offer 60. n个骰子的点数 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210409195817384

我太难了，每次看到这种题目就头疼。。。

# 解法一：动态规划

首先我们根据公式可得，n个骰子所对应的和为5n+1种，然后我们动态规划的递推公式如下

image-20210409201403618

func dicesProbability(n int) []float64 {
   dp:=make([]float64,6)
   for i := 0; i < 6; i++ {
      dp[i] = 1.0/6.0
   }
   for i := 2; i <= n; i++ {
      tmp:=make([]float64,5*i+1)
      for j := 0; j < len(dp); j++ {
         for k := 0; k < 6; k++ {
            tmp[j+k]+=dp[j]/6.0
         }
      }
      dp = tmp
   }
   return dp
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
编辑 (opens new window)
上次更新: 2021/04/10, 14:27:26
41-50
61-70

← 61-70→

Theme by Vdoing | Copyright © 2021-2021 小游