秋招复习计划-算法题4

  |  

前言

合并两个排序的链表、树的子结构、二叉树的镜像、顺时针打印举证、包含Min函数的栈


35



合并两个排序的链表

题目描述

输入两个单调递增的链表,输出两个链表合并后的链表,合并后的链表要满足单调不减。

题目分析

从两个链表的单调递增的特点出发,我们只需要比较两个链表的头节点,将较小的取出,放到第三个链表,然后将去除的那个链表的头节点往后移,重复过程,直到两个链表遍历完成。

从这个过程的重复性来看,可以使用递归来做

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
function Merge(pHead1, pHead2) {
let pMergeHead = null;
if(pHead1 == null) return pHead2;
if(pHead2 == null) return pHead1;
if(pHead1.value < pHead2.value) {
pMergeHead = pHead1;
pMergeHead.next = Merge(pHead1.next, pHead2);
} else {
pMergeHead = pHead2;
pMergeHead.next = Merge(pHead1, pHead2.next);
}
return pMergeHead;
}

递归方法,当任意链表到尾,然后另一链表的当前节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function Merge(pHead1, pHead2) {
let midHead = null;
let pMergeHead = midHead;
while(pHead1.next !== null || pHead2 !== null) {
if(pHead1.value < pHead2.value) {
midHead = pHead1;
pHead1 = pHead1.next;
} else {
midHead = pHead2;
pHead2 =pHead2.next;
}
midHead = midHead.next;
}
return pMergeHead;
}

非递归的版本,由于不知道链表节点产生的方式,所以并不知道pMergeHead = midHead是否为浅引用,如果是浅引用的话,那么这一步是多余的,且最后返回的就是合成链表的最后一个节点。

树的子结构

题目描述

输入两颗二叉树A,B,判断B是不是A的子结构。这里约定,空树不是任何树的子树

题目分析

树的操作离不开递归的思想,这道题也是用递归解的。分析判断的过程,无非是:

  • 在树A中找到和B树根节点的值一样的节点R
  • 取A树R节点的左子树根节点,判断是否和B树根节点左子树的根节点的值相等
  • 判断右子树
  • 递归

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//递归遍历A树,查找与B树根节点值相等的节点
function HasSubtree(pRoot1, pRoot2) {
let res = false;
//判断A树是否到底,到底后说明A树中并不存在与B根节点相同值的节点,同时判断B树是否为空树
if(pRoot1 === null || pRoot2 === null) return false;
if(pRoot1.val === pRoot2.val) res = doesTree1HasTree2(pRoot1, pRoot2);
if(!res) res === HasSubtree(pRoot1.left, pRoot2);
if(!res) res === HasSubtree(pRoot1.right, pRoot2);
return res;
}

function doesTree1HasTree2(pRoot1, pRoot2) {
//A树到底,但是并没有判断完,说明A树包含部分B树,但是包含不完全
if(pRoot1 === null) return false;
//B树到底,没有退出递归,说明子树存在
if(pRoot2 === null) return true;
if(pRoot1.val !== pRoot2.val) return false;
//递归遍历A树与B树的左右子树,递归判断
return doesTree1HasTree2(pRoot1.left, pRoot2.left) && doesTree1HasTree2(pRoot1.right, pRoot2.right)
}

二叉树的镜像

题目描述

操作给定的二叉树,以根节点为中心,对称反转。

例如

1
2
3
		8                               8
6 10 10 6
5 7 9 11 11 9 7 5

题目分析

简单的递归交换左右节点

1
2
3
4
5
6
7
function Mirror(root) {
if(root === null) return;
Mirror(root.left);
Mirror(root.right);
[root.left, root.right] = [root.right, root.left];
return root;
}

顺时针打印矩阵

题目描述

输入要给矩阵按照从外向内以顺时针顺序一次打印每一个数字

例如

1
2
3
4
1 2 3
4 5 6
7 8 9
的打印结果为1 2 3 6 9 8 7 4 5

题目分析

方法一:常规循环

首先我们需要知道每一次循环需要打印什么。顺时针的话先横,arr[0][0]arr[0][col-1]再从arr[0][col-1]arr[row-1][col-1]再到arr[row-1][0]最后回到arr[1][0],这样一圈的循环结束了。而且观察每次循环圈的开始,可以看到它的下标行号和列号是相等的。那么最后在什么时候退出循环呢。就是在其实点的下标a,乘2后大于行或列。

方法二:模拟魔方逆时针解法

我们每次只输出矩阵的第一行,但是,每次输出后我们都对矩阵进行一次逆时针旋转,这样我们就能确保每次输出的都是顺时针的下一列或者下一行

例如

1
2
3
1 2 3   输出第一行后逆时针旋转   6 9 
4 5 6 5 8
7 8 9 4 7

算法代码

方法一的代码

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
function printMatrix(matrix) {
if(matrix == null) return null;
const rows = matrix.length, // 行数
cols = matrix[0].length; //列数
let start = 0,
res = [];
while(rows > start * 2 && cols > start * 2) {
res = res.concat(printMatrixInCircle(matrix, rows, cols, start));
start++; //加1进入下层循环
}
return res;
}

function printMatrixInCircle(matrix, rows, cols, start) {
const endX = cols - 1 - start, //算对角的列号
endY = rows - 1 - start,//算对角的行号
res = [];
//输入上边
for(let i = start; i <= endX; i++) {
res.push(matrix[start][i]);
}
//输入右列
for(let i = start + 1; i <= endY; i++) {
res.push(matrix[i][endY]);
}
//输入下边
for(let i = endX -1; i >= start && endY > start; i--) {
res.push(matrix[endY][i]);
}
//输入左列
for(let i = endY -1; i >= start + 1 && endX > start; i--) {
res.push(matrix[i][start]);
}
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
function printMatrix2(matrix) {
if(!matrix) return null;
let res = [];
const firstRow = matrix.shift();
res = res.concat(firstRow);
while(matrix.length) {
matrix = rotateMatrix(matrix);
res = res.concat(matrix.shift());
}
return res;
}

function rotateMatrix(matrix) {
if(matrix[0].length === undefined) return matrix;
const rows = matrix.length,
cols = matrix[0].length,
newMatrix = [];
for(let j = cols - 1; j >= 0; j--) {
const tempMatrix = [];
for(let i = 0; i < rows; i++) {
tempMatrix.push(matrix[i][j]);
}
newMatrix.push(tempMatrix);
}
return newMatrix;
}

包含Min函数的栈

题目描述

定义栈的数据结构,在该类型中实现一个能找到栈最小值的min函数

题目分析

最简单的方法就是逐一比较,但是这种方法虽然思路上简单,但是实现起来较为麻烦。我们需要引入一个辅助栈,将原先栈中的元素先注意弹出,压入辅助栈,在这个过程中找到最小值。再将辅助栈的内容逐一弹出,压入原栈,从而恢复原栈的存储顺序。

另一种方法实现起来更为简单,既然已经引入了辅助栈,那么我们考虑在数据压入栈之前,先和目前的最小值做比较。比较过后将值压入原栈,但是对于辅助栈,我们只压入当前最小值,这样始终保证辅助栈的栈顶是当前最小值。举例来说

1
2
数据栈: 5,4,3,8,10,11,12,1
辅助栈: 5,4,3,3,3,3,3,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
class Mystack {
constructor() {
this.stack = [];
this.minstack = [];
}
push(node) {
this.stack.push(node);
}
pop() {
return stack.pop();
}
min() {
let min = this.stack[this.stack.length - 1];
while(this.stack.length) {
let temp = this.stack.pop();
if(temp < min) min = temp;
this.minstack.push(temp);
}
while(this.minstack.length) {
this.stack.push(this.minstack.pop());
}
return min
}
}

方法二:辅助栈压入

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
class Mystack {
constructor() {
this.stack = [];
this.tempstack = [];
this.temp = null;
}
push(node) {
if(this.temp !== null) {
if(this.temp > node) {
this.temp = node;
}
this.stack.push(node);
this.tempstack.push(this.temp);
} else {
this.temp = node;
this.stack.push(node);
this.tempstack.push(this.temp);
}
}
pop() {
return this.stack.pop();
}
min() {
return this.tempstack[this.tempstack.length - 1];
}
}
文章目录
  1. 1. 合并两个排序的链表
  2. 2. 树的子结构
  3. 3. 二叉树的镜像
  4. 4. 顺时针打印矩阵
  5. 5. 包含Min函数的栈
|