数据结构

# 数组

# 找到所有数组中消失的数字

这题目想法可以借鉴一下，就是我们让数组作为数组的下标，然后根据当前数字的正负来判断数字是否出现。

func findDisappearedNumbers(nums []int) []int {
   var ans []int
   // 遍历nums数组
   for _,v:=range nums{
      // 首先我们计算当前数字所在的位置（数组从0开始，所以我们需要-1）
      pos:=int(math.Abs(float64(v))-1)
      // 如果当前位置的数字大于0，我们就取反
      // 这里如果为负数，就说明我们这个数字出现过了
      if nums[pos] > 0 {
         nums[pos] = - nums[pos]
      }
   }
   // 下面我们只需要判断当前位置的数字是否为0就可以了
   for i := 0; i < len(nums); i++ {
      if nums[i] > 0 {
         ans = append(ans, i+1)
      }
   }
   return ans
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 栈和队列

自己可以简单定义一个栈

type Stack struct {
	data []int
}
func (s *Stack) Push(k int)  {
	s.data = append(s.data, k)
}
func (s *Stack) Pop() (x int) {
	x = s.data[len(s.data)-1]
	s.data = s.data[:len(s.data)-1]
	return
}
func (s *Stack) Empty() bool {
	return len(s.data) == 0
}
func (s *Stack) Top() int {
	return s.data[len(s.data)-1]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 用栈来实现队列

232. 用栈实现队列 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这题目只能使用两个栈来实现，那么我们就可以定义两个栈，一个为in，一个为out，当我们入队时，我们可以让所有的数push到in栈里去，然后当我们想出队时，我们就需要把in栈里的数据pop到out栈里，这样先进去的会出现在栈顶，然后我们只需要让out栈pop就行了

type Stack struct {
   data []int
}
func (s *Stack) Push(k int)  {
   s.data = append(s.data, k)
}
func (s *Stack) Pop() (x int) {
   x = s.data[len(s.data)-1]
   s.data = s.data[:len(s.data)-1]
   return
}
func (s *Stack) Empty() bool {
   return len(s.data) == 0
}
func (s *Stack) Top() int {
   return s.data[len(s.data)-1]
}

type MyQueue struct {
   // 我们需要定义一个in，一个out两个栈
   in Stack
   out Stack
}
/** Initialize your data structure here. */
func Constructor() MyQueue {
   return MyQueue{}
}
/** Push element x to the back of queue. */
func (this *MyQueue) Push(x int)  {
   // 把当前数据放入in的栈中
   this.in.Push(x)
}
/** Removes the element from in front of queue and returns that element. */
func (this *MyQueue) Pop() int {
   // 当我们进行pop操作时，我们把in栈里面的数据全部pop到out栈里
   this.in2Out()
   return this.out.Pop()
}
/** Get the front element. */
func (this *MyQueue) Peek() int {
   this.in2Out()
   // 此时out就是我们队列的结尾了
   return this.out.Top()
}
func (this *MyQueue) in2Out() {
   // 这里是
   if this.out.Empty() {
      for !this.in.Empty() {
         x:= this.in.Pop()
         this.out.Push(x)
      }
   }
}
/** Returns whether the queue is empty. */
func (this *MyQueue) Empty() bool {
   return this.in.Empty() && this.out.Empty()
}

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
49
50
51
52
53
54
55
56
57

# 最小栈

155. 最小栈 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

# 有效括号

20. 有效的括号 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

# 单调栈

单调栈通过维持栈内值的单调递增（递减）性，在整体 O(n) 的时间内处理需要大小比较的问题。

# 每日温度

739. 每日温度 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这题目不好理解，主要还是这个栈比较难理解，我们为了求当天要等待的天数肯定不能直接求的，所以我们可以把当天放到栈里面去，然后往后遍历，每次遍历时，我们都把遍历所在的天数和栈里的进行比较如果气温比栈里的大，那么我们就可以得到栈里这一天的结果了。然后出栈，继续遍历栈，直到栈里的气温比遍历所在天数的气温大就进行下一轮的遍历

type Stack struct {
   data []int
}
func (s *Stack) Push(k int)  {
   s.data = append(s.data, k)
}
func (s *Stack) Pop() (x int) {
   x = s.data[len(s.data)-1]
   s.data = s.data[:len(s.data)-1]
   return
}
func (s *Stack) Empty() bool {
   return len(s.data) == 0
}
func (s *Stack) Top() int {
   return s.data[len(s.data)-1]
}
func dailyTemperatures(T []int) []int {
   n:=len(T)
   ans:=make([]int,n)
   // 维护一个单调栈来表示每天的温度
   indices:=Stack{}
   // 遍历
   for i := 0; i < n; i++ {
      // 判断indices是否为空
      for !indices.Empty() {
         // 获取栈顶为第几天
         pre:=indices.Top()
         // 判断一下当天的温度是否比栈顶的高
         if T[i] <= T[pre] {
            break
         }
         // 如果当天气温比栈顶的高，那么我们就可以知道要等多少天数可以观察到更高温的天气了                
         indices.Pop()
         // 这里我们就知道结果了
         ans[pre]= i-pre
         // 注意这里，我们已经知道栈顶的结果了，我们可以继续遍历，直到遇到栈里的气温比当天高为止
      }
      // 把当天放入栈中
      indices.Push(i)
   }
   return ans
}

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

# 优先队列

优先队列（priority queue）可以在 O(1) 时间内获得最大值，并且可以在 O(log n) 时间内取出最大值或插入任意值。优先队列常常用堆（heap）来实现。堆是一个完全二叉树，其每个节点的值总是大于等于子节点的值。实际实现堆时，我们通常用一个数组而不是用指针建立一个树。这是因为堆是完全二叉树，所以用数组表示时，位置 i 的节点的父节点位置一定为 i/2，而它的两个子节点的位置又一定分别为 2i 和 2i+1。以下是堆的实现方法，其中最核心的两个操作是上浮和下沉：如果一个节点比父节点大，那么需要交换这个两个节点；交换后还可能比它新的父节点大，因此需要不断地进行比较和交换操作，我们称之为上浮；类似地，如果一个节点比父节小，也需要不断地向下进行比较和交换操作，我们称之为下沉。如果一个节点有两个子节点，我们总是交换最大的子节点。

# 合并K的有序列表

23. 合并K个升序链表 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这题有点看不懂。。。后面有时间再研究

# 天际线问题

218. 天际线问题 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

# 双端队列

# 滑动窗口最大值

239. 滑动窗口最大值 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

# 哈希表

# 两数之和

1. 两数之和 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

func twoSum(nums []int, target int) []int {
   // 创建map并遍历数组
   arr:=map[int]int{}
   for k,v:=range nums{
      arr[v] = k
   }
   // 求解
   for k,v:=range nums{
      a:=target - v
      if index, ok := arr[a];ok && index!=k{
         return []int{k,index}
      }
   }
   return []int{}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 最长连续序列

128. 最长连续序列 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

# 直线上最多的点数

149. 直线上最多的点数 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

# 多重集合和映射

这题。。。源代码有些地方没看懂，先放一放

# 前缀与积分图

一维的前缀和，二维的积分图，都是把每个位置之前的一维线段或二维矩形预先存储，方便加速计算。如果需要对前缀和或积分图的值做寻址，则要存在哈希表里；如果要对每个位置记录前缀和或积分图的值，则可以储存到一维或二维数组里，也常常伴随着动态规划。

# 区域和检索，数组不可变

注意这题目并不是要我们每次计算时都用for循环遍历计算，而是我们提前算好前面各位的和，最后计算时直接两个和相减就能得出最后结果。

type NumArray struct {
   nums []int
}


func Constructor(nums []int) NumArray {
   // 在我们开始阶段我分别统计前n位和并放入第n位数组上
   n:=len(nums)
   sum:=make([]int,n+1)
   sum[1] = nums[0]
   for i := 2; i <= n; i++ {
      sum[i] = sum[i-1]+nums[i-1]
   }
   return NumArray{sum}
}


func (this *NumArray) SumRange(left int, right int) int {
   // 因为我们前面是已经计算好了的，所以我们这里直接两个和相减就是最终范围了
   return this.nums[right+1]-this.nums[left]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 二维区域和检索-矩阵不可变

304. 二维区域和检索 - 矩阵不可变 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

# 和为K的字数组

560. 和为K的子数组 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

编辑

上次更新: 2021/03/25, 23:10:37

← 位运算字符串→