# 第2章线性结构算法题

2-1 括号匹配问题-读题
2-2 括号匹配问题-解题
2-3 使用栈实现队列-读题
2-4 使用栈实现队列-实现一个标准栈
2-5 使用栈实现队列-实现一个标准队列
2-6 使用栈实现队列-分析及解题
2-7 单链表反转-读题
2-8 单链表反转-构建单元测试
2-9 单链表反转-常规解
2-10 单链表反转-递归解
2-12 二分法

# 2-1 括号匹配问题-读题

题目：

来源：LeetCode (opens new window)

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例：

示例 1:

输入: "()" 输出: true

示例 2:

输入: "()[]{}" 输出: true

示例 3:

输入: "(]" 输出: false

示例 4:

输入: "([)]" 输出: false

示例 5:

输入: "{[]}" 输出: true

示例 6:

输入: "{" 输出: false

准备用例：

创建文件 isBracketsValid.ts
实现函数的主体结构
创建文件 isBracketsValid.test.ts
实现测试用例1

# 2-2 括号匹配问题-解题

题目：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

分析：

借助栈的结构来解决！

st=>start: 开始
e=>end: 结束
op1=>operation: 将字符串拆分为数组(可省略)
op2=>operation: 取出一个元素 item
op3=>operation: 取出栈顶元素 stackItem
cond1=>condition: item 与 stackItem 匹配
op4=>operation: stackItem 出栈
op5=>operation: item 入栈
cond2=>condition: 遍历完所有元素


st->op1->op2->op3->cond1
cond1(yes)->op4->cond2
cond1(no)->op5->cond2
cond2(no)->op2
cond2(yes)->e

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

验证：

输入: “ "

栈：

输出: true

示例 2:

输入: “”

栈：

栈：输出: true

示例 3:

输入: "”

栈：(]

栈：输出: false

操作：

准备
1. 将字符串拆分成数组
2. 创建一个空的栈
3. 创建括号匹配规则
4. 创建获取栈顶元素的方法
核心逻辑
1. 逐个将栈顶元素和数组中的元素匹配
2. 根据匹配结果执行不同的操作
3. 检查栈是否为空。
测试
优化

# 2-3 使用栈实现队列-读题

题目：

来源：LeetCode (opens new window)

使用栈实现队列的下列操作：

push(x) -- 将一个元素放入队列的尾部。 pop() -- 从队列首部移除元素。 peek() -- 返回队列首部的元素。 empty() -- 返回队列是否为空。

示例:

MyQueue queue = new MyQueue();
queue.push(10);
queue.push(11);  
queue.peek();  // 返回 10
queue.pop();   // 返回 10
queue.empty(); // 返回 false
queue.pop();   // 返回 11
queue.empty(); // 返回 true

1
2
3
4
5
6
7
8

说明:

你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 empty 操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）。

步骤：

实现一个标准栈
实现一个标准队列
使用栈实现队列

# 2-4 使用栈实现队列-实现一个标准栈

问题：

实现一个标准栈

分析：

标准栈方法

empty
size
peak
push
pop

测试用例

  const stack = new Stack();
  expect(stack.empty()).toBe(true);

  stack.push(10);
  expect(stack.empty()).toBe(false);
  expect(stack.size()).toBe(1);
  expect(stack.peak()).toBe(10);
  expect(stack.size()).toBe(1);

  stack.push(11);
  expect(stack.empty()).toBe(false);
  expect(stack.size()).toBe(2);
  expect(stack.peak()).toBe(11);
  expect(stack.size()).toBe(2);

  expect(stack.pop()).toBe(11);
  expect(stack.empty()).toBe(false);
  expect(stack.size()).toBe(1);
  expect(stack.peak()).toBe(10);
  expect(stack.size()).toBe(1);

  expect(stack.pop()).toBe(10);
  expect(stack.empty()).toBe(true);
  expect(stack.size()).toBe(0);
  expect(stack.peak()).toBe(undefined);

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

步骤：

新建文件 Stack.ts
实现 Stack 的基本结构并导出
新建文件 Stack.test.ts
实现测试用例
完善Stack 代码细节

# 2-5 使用栈实现队列-实现一个标准队列

问题：

实现一个标准队列

分析：

标准队列方法

empty
size
peak
push
pop

测试用例

  const queue = new Queue();
  expect(queue.empty()).toBe(true);

  queue.push(10);
  expect(queue.empty()).toBe(false);
  expect(queue.size()).toBe(1);
  expect(queue.peak()).toBe(10);
  expect(queue.size()).toBe(1);

  queue.push(11);
  expect(queue.empty()).toBe(false);
  expect(queue.size()).toBe(2);
  expect(queue.peak()).toBe(10);
  expect(queue.size()).toBe(2);

  expect(queue.pop()).toBe(10);
  expect(queue.empty()).toBe(false);
  expect(queue.size()).toBe(1);
  expect(queue.peak()).toBe(11);
  expect(queue.size()).toBe(1);

  expect(queue.pop()).toBe(11);
  expect(queue.empty()).toBe(true);
  expect(queue.size()).toBe(0);
  expect(queue.peak()).toBe(undefined);

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

步骤：

新建文件 Queue.ts
实现 Queue 的基本结构并导出
新建文件 Queue.test.ts
实现测试用例
完善 Queue 代码细节

# 2-6 使用栈实现队列-分析及解题

问题：

使用栈实现队列。

分析：

1，2，3 入队后出队的顺序为 1，2，3
1，2，3 入栈后出栈的顺序为 3，2，1

如果入两次出入栈是不是就和一次出入队列的顺序一样了

详细步骤：

push 直接使用 A 栈
pop/peak 使用 B 栈
1. 当 B 栈为空时，将 A 栈所有内容移动到 B栈
队列的长度等于两个栈长度之和

步骤：

新建文件 MyQueue.ts
在 MyQueue.ts 中使用 Queue.ts 的代码
新建文件 MyQueue.test.ts
在 MyQueue.test.ts 中使用 Queue.test.ts 的代码(略修改)
完善 MyQueue 代码细节

# 2-7 单链表反转-读题

题目：

来源：LeetCode (opens new window)

反转一个单链表。

示例:

输入: 1->2->3->4->5->null 输出: 5->4->3->2->1->null

输入：1->null

输出：1->null

输入：null

输出：null

回顾：

单链表节点：

class ListNode<T> {
  val: T;
  next: null | ListNode<T>;
  constructor(val: T) {
    this.val = val;
    this.next = null;
  }
}

//构建链表 1->2->null
//const node1 = new ListNode(1);
//const node2 = new ListNode(2);
//node1.next = node2;

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

步骤：

创建文件 ListNode.ts
粘贴代码

# 2-8 单链表反转-构建单元测试

问题：

构建单链表反转的单元测试。

分析：

使用示例测试

输入: 1->2->3->4->5->null

输出: 5->4->3->2->1->null

输入：1->null

输出：1->null

输入：null

输出：null

步骤：

新建文件 reverseList.ts
实现函数基本结构并导出
新建文件 reverseList.test.ts
完善 reverseList.test.ts 代码细节
1. 测试 null
2. 测试单节点链表
3. 测试多节点链表
  1. 构建多节点
  2. 测试已构建的多节点链表
  3. 反转多节点链表
  4. 测试已反转的多节点链表

# 2-9 单链表反转-常规解

问题：

反转一个单链表。

分析：

单独处理 null 的情况
声明一个null（做为第一个元素）
将链表从头到尾逐个指向前一个元素

步骤：

处理 head 为 null 的情况
声明变量 cur，next，result
当 next 不为 null 执行以下操作
1. cur.next=result
2. moveNext (cur, next,result)
cur.next=result
返回 cur

扩展：

这里我使用3个变量，cur，next，result。防止指针丢失使用2个变量就够了。如何实现？

# 2-10 单链表反转-递归解

问题：

反转一个单链表。

分析：

使用递归的方式实现单链表反转。

步骤：

复制代码文件和测试用例代码文件
修改测试用例代码
修改文件代码
1. 处理 head 为null 或者单节点的情况
2. 处理递归
3. 修正指向 head 的指针
4. 修正 head 的指针

# 2-12 二分法

← 第1章简介第3章非线性结构算法题 →

# 第2章 线性结构算法题

# 2-1 括号匹配问题-读题

# 2-2 括号匹配问题-解题

# 2-3 使用栈实现队列-读题

# 2-4 使用栈实现队列-实现一个标准栈

# 2-5 使用栈实现队列-实现一个标准队列

# 2-6 使用栈实现队列-分析及解题

# 2-7 单链表反转-读题

# 2-8 单链表反转-构建单元测试

# 2-9 单链表反转-常规解

# 2-10 单链表反转-递归解

# 2-12 二分法

# 第2章线性结构算法题