栈与队列
栈的概念：
栈是一种遵循先入后出逻辑的线性数据结构。
栈的常用操作：
| 方法 | 描述 | 时间复杂度 |
|---|---|---|
| push() | 元素如栈 | O(1) |
| pop() | 栈顶元素出战 | O(1) |
| peek | 访问栈顶元素 | O(1) |
队列的概念
队列是一种遵循先入先出规则的线性数据结构。顾命思义，队列模拟了排队现象，即新来的人不断加入队列尾部，而位于队列头部的人逐个离开。
我们将队列的头部称为“队首”，尾部称为“队尾”，将把元素加入队列的操作称为“入队”，删除队首元素的操作称为“出队”。
| 方法名 | 描述 | 时间复杂度 |
|---|---|---|
| push() | 元素入队 | O(1) |
| pop() | 队首元素出队 | O(1) |
| peek() | 访问队首元素 | O(1) |
第一部分 练习题
INFO
用队列实现栈
使用栈实现队列的下列操作：
push(x) -- 将一个元素放入队列的尾部。 pop() -- 从队列首部移除元素。 peek() -- 返回队列首部的元素。 empty() -- 返回队列是否为空。
代码示例：
typescript
class MyQueue {
private stackIn: number[]
private stackOut: number[]
constructor() {
this.stackIn = [];
this.stackOut = [];
}
push(x: number): void {
this.stackIn.push(x);
}
pop(): number {
if (this.stackOut.length === 0) {
while (this.stackIn.length > 0) {
this.stackOut.push(this.stackIn.pop()!);
}
}
return this.stackOut.pop()!;
}
peek(): number {
let temp: number = this.pop();
this.stackOut.push(temp);
return temp;
}
empty(): boolean {
return this.stackIn.length === 0 && this.stackOut.length === 0;
}
}INFO
用队列实现栈
使用队列实现栈的下列操作：
- push(x) -- 元素 x 入栈
- pop() -- 移除栈顶元素
- top() -- 获取栈顶元素
- empty() -- 返回栈是否为空
代码示例：
typescript
class MyStack {
private queue: number[];
private tempQueue: number[];
constructor() {
this.queue = [];
this.tempQueue = [];
}
push(x: number): void {
this.queue.push(x);
}
pop(): number {
for (let i = 0, length = this.queue.length - 1; i < length; i++) {
this.tempQueue.push(this.queue.shift()!);
}
let res: number = this.queue.pop()!;
let temp: number[] = this.queue;
this.queue = this.tempQueue;
this.tempQueue = temp;
return res;
}
top(): number {
let res: number = this.pop();
this.push(res);
return res;
}
empty(): boolean {
return this.queue.length === 0;
}
}INFO
有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 注意空字符串可被认为是有效字符串。
代码示例：
typescript
function isValid(s: string): boolean {
if (s.length % 2 != 0) return false;
const stack = [];
const map = {
'(': ')',
'{': '}',
'[': ']',
};
for (let i = 0, len = s.length; i < len; i++) {
const item = s[i] as keyof typeof map;
//遇到左括号
if (map[item]) stack.push(map[item]);
//遇到右括号
else {
if (stack.length == 0) return false;
if (item != stack.pop()) return false;
}
}
return !(stack.length >= 1);
}INFO
删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
- 输入："abbaca"
- 输出："ca"
- 解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
代码示例:
typescript
function removeDuplicates(s: string): string {
const helperStack: string[] = [];
let i: number = 0;
while (i < s.length) {
let top: string = helperStack[helperStack.length - 1];
if (top === s[i]) {
helperStack.pop();
} else {
helperStack.push(s[i]);
}
i++;
}
let res: string = '';
while (helperStack.length > 0) {
res = helperStack.pop() + res;
}
return res;
};第二部分 练习题
INFO
逆波兰表达式求值
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
- 有效的算符为
'+'、'-'、'*'和'/'。 - 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
代码示例：
typescript
function evalRPN(tokens: string[]): number {
const stack = [];
const opratioSymbolMap = {
'+': '+',
'-': '-',
'*': '*',
'/': '/',
};
const calcMap = {
'+': (_num_1: number, _num_2: number) => _num_1 + _num_2,
'-': (_num_1: number, _num_2: number) => _num_1 - _num_2,
'*': (_num_1: number, _num_2: number) => _num_1 * _num_2,
'/': (_num_1: number, _num_2: number) => {
const compare = _num_1 < _num_2 ? _num_2 / _num_1 : _num_1 / _num_2;
return compare > 0 ? Math.floor(compare) : Math.ceil(compare);
},
};
for (let i = 0, len = tokens.length; i < len; i++) {
const item = tokens[i] as keyof typeof opratioSymbolMap;
if (opratioSymbolMap[item]) {
let _num_1 = Number(stack.pop()),_num_2 = Number(stack.pop());
const result = calcMap[item](_num_1, _num_2) as number;
stack.push(result);
} else stack.push(item);
}
return Number(stack.pop())
}INFO
滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7] 解释： 滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
代码实现：
typescript
/** 单调递减队列 */
class MonoQueue {
constructor(private queue: number[] = []) {}
/** 入队：value如果大于队尾元素，则将队尾元素删除，直至队尾元素大于value，或者队列为空 */
public enqueue(value: number): void {
let back: number | undefined = this.queue[this.queue.length - 1];
while (back !== undefined && back < value) {
this.queue.pop();
back = this.queue[this.queue.length - 1];
}
this.queue.push(value);
}
/** 出队：只有当队头元素等于value，才出队 */
public dequeue(value: number): void {
let top: number | undefined = this.top();
if (top !== undefined && top === value) {
this.queue.shift();
}
}
public top(): number | undefined {
return this.queue[0];
}
}
function maxSlidingWindow(nums: number[], k: number): number[] {
const helperQueue: MonoQueue = new MonoQueue();
let i: number = 0,
j: number = 0;
let resArr: number[] = [];
while (j < k) {
helperQueue.enqueue(nums[j++]);
}
resArr.push(helperQueue.top()!);
while (j < nums.length) {
helperQueue.enqueue(nums[j]);
helperQueue.dequeue(nums[i]);
resArr.push(helperQueue.top()!);
j++, i++;
}
return resArr;
}INFO
滑动窗口最大值
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
示例2:
输入: nums = [1], k = 1 输出: [1]
代码实现：
typescript
function topKFrequent(nums: number[], k: number): number[] {
const countMap: Map<number, number> = new Map();
for (let num of nums) {
countMap.set(num, (countMap.get(num) || 0) + 1);
}
// tS没有最小堆的数据结构，所以直接对整个数组进行排序，取前k个元素
return [...countMap.entries()]
.sort((a, b) => b[1] - a[1])
.slice(0, k)
.map((i) => i[0]);
}