发表更新数据结构与算法 / LeetCode75学习计划15 分钟读完 (大约2235个字)

LeetCode75学习计划-栈/队列

算法解题思路很多会借鉴于题解区，如果侵权请联系删除。

本章节知识点为栈/队列。

从字符串中移除星号

题目标签：

  • 栈
  • 字符串

题目难度： Medium

题目描述：

给你一个包含若干星号 * 的字符串 s 。

在一步操作中，你可以：

选中 s 中的一个星号。
移除星号 左侧 最近的那个 非星号 字符，并移除该星号自身。
返回移除 所有 星号之后的字符串。

注意：

生成的输入保证总是可以执行题面中描述的操作。
可以证明结果字符串是唯一的。

解题思路：

  • 遍历字符串，非星号则入栈，遇到星号则将栈顶元素移除。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
func removeStars(s string) string {
  stack := make([]byte, 0)
  for i, _ := range s {
    if s[i] != '*' {
      stack = append(stack, s[i])
    } else {
      stack = stack[:len(stack)-1]
    }
  }
  return string(stack)
}

行星碰撞

题目标签：

  • 栈
  • 数组

题目难度： Medium

题目描述：

给定一个整数数组 asteroids，表示在同一行的行星。

对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。

找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞

解题思路：

  • 从左往右遍历数组，当遍历到行星 a时，此时该行星存在。判断栈顶元素是否与当前行星互相向对方移动，如果是则至少有一个会爆炸，如果当前行星未爆炸则继续判断栈顶元素，直到栈内无其他行星或移动方向相同，此时将该行星加入到栈中。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func asteroidCollision(asteroids []int) []int {
  stack := []int{}
  for _, aster := range asteroids {
    // 行星初始状态是未爆炸的
    alive := true
    // 行星未爆炸 且 向左移动 且 栈内有行星 且 栈顶的行星向右移动
    for alive && aster < 0 && len(stack) > 0 && stack[len(stack) - 1] > 0 {
      // 栈顶元素比当前小，则行星依然存在
      alive = stack[len(stack) - 1] < -aster
      // 如果栈顶元素比当前小或者相同大小，那么栈顶元素都会爆炸
      if stack[len(stack) - 1] <= -aster {
        stack = stack[:len(stack) - 1]
      }
    }
    // 如果当前行星仍然存活则加入到栈中
    if alive {
      stack = append(stack, aster)
    }
  }
  return stack
}

字符串解码

题目标签：

  • 栈
  • 递归
  • 字符串

题目难度： Medium

题目描述：

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

解题思路：

  • 遍历字符串，碰到数字、字母、[直接进栈，碰到]开始出栈，知道[出栈，中间弹出的内容就是要重复的字符串，此时栈顶的数字，就是其该重复的次数，构造新的字符串后再进栈，知道遍历完整个字符串

代码实现：

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
58
59
func decodeString(s string) string {
  stack := []string{}
  ptr := 0
  for ptr < len(s) {
    // 当前元素
    cur := s[ptr]
    // 处理数字
    if cur >= '0' && cur <= '9' {
      // 取出完整的数字
      digits := getDigits(s, &ptr)
      stack = append(stack, digits)
    // 处理字母和左括号
    } else if (cur >= 'a' && cur <= 'z' || cur >= 'A' && cur <= 'Z') || cur == '[' {
      stack = append(stack, string(cur))
      ptr++
    } else {
      // 右括号
      ptr++
      // 因为括号可以嵌套，我们处理当前部分的字符串
      sub := []string{}
      // 取出字母的部分
      for stack[len(stack) - 1] != "[" {
        sub = append(sub, stack[len(stack) - 1])
        stack = stack[:len(stack) - 1]
      }
      // 取出的字母顺序是反的，需要调换reverse一下
      for i := 0; i < len(sub)/2; i++ {
        sub[i], sub[len(sub) - i - 1] = sub[len(sub) - i - 1], sub[i]
      }
      // 取出左括号
      stack = stack[:len(stack) - 1]
      // 重复次数
      repeatTime, _ := strconv.Atoi(stack[len(stack) - 1])
      stack = stack[:len(stack) - 1]
      // 计算重复后的字符串
      t := strings.Repeat(getString(sub), repeatTime)
      // 加入到栈中
      stack = append(stack, t)
    }
  }
  // 返回最终的结果
  return getString(stack)
}
// 取出完整数字
func getDigits(s string, ptr *int) string {
  res := ""
  for ; s[*ptr] >= '0' && s[*ptr] <= '9'; *ptr ++ {
    res += string(s[*ptr])
  }
  return res
}
// []string => string
func getString(v []string) string {
  res := ""
  for _, s := range v {
    res += s
  }
  return res
}

最近的请求次数

题目标签：

  • 队列
  • 设计
  • 数据流

题目难度： Easy

题目描述：

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请你实现 RecentCounter 类：

RecentCounter() 初始化计数器，请求数为 0 。
int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。
保证 每次对 ping 的调用都使用比之前更大的 t 值。

解题思路：

  • 遍历字符串，碰到数字、字母、[直接进栈，碰到]开始出栈，知道[出栈，中间弹出的内容就是要重复的字符串，此时栈顶的数字，就是其该重复的次数，构造新的字符串后再进栈，知道遍历完整个字符串

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type RecentCounter struct {
  requests []int;
}
func Constructor() RecentCounter {
  return RecentCounter{}
}
func (this *RecentCounter) Ping(t int) int {
  // 只保留[t-3000, t]之间的请求
  for len(this.requests) > 0 && this.requests[0] < t - 3000 {
    this.requests = this.requests[1:]
  }
  this.requests = append(this.requests, t)
  return len(this.requests)
}

Dota2 参议院

题目标签：

  • 队列
  • 贪心
  • 字符串

题目难度： Medium

题目描述：

Dota2 的世界里有两个阵营：Radiant（天辉）和 Dire（夜魇）

Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的 一 项：

  • 禁止一名参议员的权利：参议员可以让另一位参议员在这一轮和随后的几轮中丧失 所有的权利 。
  • 宣布胜利：如果参议员发现有权利投票的参议员都是 同一个阵营的 ，他可以宣布胜利并决定在游戏中的有关变化。

给你一个字符串 senate 代表每个参议员的阵营。字母 'R' 和 'D'分别代表了 Radiant（天辉）和 Dire（夜魇）。然后，如果有 n 个参议员，给定字符串的大小将是 n。

以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。

假设每一位参议员都足够聪明，会为自己的政党做出最好的策略，你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。输出应该是 "Radiant" 或 "Dire" 。

解题思路：

  • 如果当前的所有议员都是同一方的，那么可以直接宣布胜利，否则应该让另一方第一个行使权力的议员失去权力才是最有效的方式
  • 我们维护两个队列，分别是两方的议员，按照行使权力的顺序存入队列中，所以可以存储其下标。
  • 假设天辉阵容的议员先行使权利，那么将夜魇队首的元素从队列中移除，然后将天辉阵容队首议员的下标增加议员数量的值后移动到队尾，依次可以实现一个轮的循环。

代码实现：

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 predictPartyVictory(senate string) string {
  radiant := []int{}
  dire := []int{}
  for i := 0; i < len(senate); i ++ {
    if senate[i] == 'R' {
      radiant = append(radiant, i)
    } else {
      dire = append(dire, i)
    }
  }
  // 开始按顺序行使权力
  for len(radiant) > 0 && len(dire) > 0 {
    // 天辉阵容行使权力
    if (radiant[0] < dire[0]) {
      radiant = append(radiant, radiant[0]+len(senate))
    // 夜魇阵容行使权利
    } else {
      dire = append(dire, dire[0] + len(senate))
    }
    // 两阵容队首的元素移除
    radiant = radiant[1:]
    dire = dire[1:]
  }
  if len(radiant) > 0 {
    return "Radiant"
  }
  return "Dire"
}

LeetCode75学习计划-栈/队列

https://zhaolei-hu.github.io/2023/07/09/LeetCode75学习计划-栈-队列/

作者

胡兆磊

发布于

2023-07-09

更新于

2023-07-09

许可协议

#
关注我

分类

最新文章

归档

标签

BFS2
CSS5
DFS2
Dart1
Database1
Decorator1
EggJs3
EggJss1
ElementUI1
EventEmitter1
Flutter1
GetX1
Gin1
Go2
HarmonyOS1
IndexedDB1
JavaScript1
Javascript13
LeetCode12
Mongodb1
Mysql1
NestJs20
NodeJs28
Promise1
Proxy2
Python1
Reflect2
Sass3
Scss3
TypeScript1
Vue10
Vue-Router1
Web Storage1
axios7
canvas1
cli1
cron表达式1
hexo1
log4js1
lunarvim1
monorepo1
mustache1
neovim1
pinia1
typescript2
yarn1
二分查找1
二叉搜索树1
二叉树1
前缀和1
前缀树1
动态规划2
双指针1
哈希表1
哈希集合1
图1
字符串1
排序算法3
数组1
文件上传1
栈1
源码1
滑动窗口1
背包问题1
装饰器1
链表1
队列1

目录

×