秋招复习计划-算法题1

  |  

前言

开始用JS去刷剑指offer的算法题,一次五道题。这次包括二维数组的查找、替换空格、从尾到头打印链表、重建二叉树、用两个栈实现队列。


28



二维数组的查找

题目描述

在一个有序二维数组中,每一行按照从左到右递增,每一列按照从上到下递增的顺序排序,请完成这样一个函数,输入一个这样的数组和一个整数,判断这个数组中是否包含这个整数

1
2
时间限制: 1s
空间限制: 32768k

题目分析

这道题的限制放的很宽,即使我们使用遍历也能在限制的时间内完成查找。但是这样对于数组是有序这一点并没有利用上,而且对于大数组,遍历的速度显然会很慢。所以我们可以先考虑遍历数组第一列,找到一行,它的开头比这个数小,它的下一行的开头比这个数大,这样我们本质上只用遍历第一列和对应的行,对于大数组将大大减少运行时间。

算法代码

全遍历方法

1
2
3
4
5
6
7
8
9
10
11
let arr = [[1, 2, 3], [4, 5], [6, 7, 8],[9]];
function find(target, array) {
for(let i = 0, lenI = array.length; i < lenI; i++) {
for(let j = 0, lenJ = array[i].length; j < lenJ; j++) {
if(array[i][j] === target) {
console.log('true');
break;
}
}
}
}

有选择的遍历方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function find(target, array) {
let n = array.length;
let row = n - 1;
while(row >= 0) {
if(array[row][0] > target) {
row--;
} else if(array[row][0] < target) {
for(let i = 0, len = array[row].length; i < len; i++) {
if(array[row][i] == target) {
return "true";
break;
}
}
return "false";
}
}
}

这里还有一个是吴神写的,但是我觉的写的并不好,因为它只考虑到了二维数组的每一维都是等长的,所以他用第一维数组的长度作为m,这样对于非等长的二维数组来说,就会存在一定的问题,比如说第一维特别的短,那么就会影响后续的判断。这里我还是把代码给出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function Find(target, array) {
// write code here
const n = array.length,
m = array[0].length;
let row = n - 1,
col = 0;
if (m === 0 && n === 0) {
return false;
}
while (row >= 0 && col <= m - 1) {
if (array[row][col] > target) {
row--;
} else if (array[row][col] < target) {
col++;
} else return true;
}
return false;
}

替换空格

题目描述

请实现一个函数,将一个字符串中的空格替换成”%20”。例如,当字符串”We are happy”经替换后的字符串为

“We%20are%20happy”。

1
2
时间限制: 1s
空间限制: 32768k

题目分析

这个题有两个方法,高效的方法是使用正则表达式,但是正则一直是我并不精通的地方,所以还可以考虑字符串的遍历查找并替换

题目代码

原先我以为可以直接对字符串具体位置直接赋值,试了一下发现不行

1
2
3
4
5
6
7
8
9
10
let str = 'We are happy';
function replaceSpace(s) {
for(let i = 0, len = s.length; i < len; i++) {
if(s[i] === ' ') {
s[i] = '%20';
}
}
return s
}
replaceSpace(str);

这段代码运行后发现字符串并没有任何变化,具体为什么不行,原因还没找到。

后来我改进了一下,将字符串先转换为数组,处理完以后再将数组转换会字符串

1
2
3
4
5
6
7
8
9
10
11
let str = 'We are happy';
function replaceSpace(s) {
let str = s.split('');
for(let i = 0, len = str.length; i < len; i++) {
if(str[i] === ' ') {
str[i] = '%20';
}
}
return str.join('');
}
replaceSpace(str);

这段代码是有效的,但是过于繁琐。所以,会用正则的话还是用正则方便

1
2
3
4
function replaceSpace(str) {
// write code here
return str.replace(/\s/g, '%20');
}

从尾到头打印链表

题目描述

输入一个链表,从尾到头打印链表每个节点的值。

1
2
时间限制: 1s
空间限制: 32768k

题目分析
这道题的做法有很多,用栈先进后出的方法可以做,用递归也可以做(递归的本质也可以理解为栈),而且如果使用JS数组的API来做,会更简单

题目代码

栈方法

1
2
3
4
5
6
7
8
9
function printListFromTailToHead(head) {
const res = [];
let pNode = head;
while(pNode !== Null) {
res.unshift(pNode.value);
pNode = pNode.next;
}
return res;
}

能写出这样的代码我真的很佩服。利用JS数组的API方法unshift,利用数组去模拟一个栈结构,从数组首部添加元素来模拟栈的压入,从而利用栈先进后出的特点实现从尾到头打印链表。

递归方法

1
2
3
4
5
6
7
8
9
let list = new Array();
function printListFromTailToHead(head) {
if(head === null) {
return list;
}
printListFromTailToHead(head.next);
list.push(head.value);
return lsit;
}

要知道递归的本质其实就是一种栈结构,他将每次函数执行压入到栈中,在从栈首开始往下执行。那么这个代码,一直递归下去后,当head === null ,及来到链尾。返回list,这时list还是要给空数组,返回后。执行递归到head === null的上一次,那么list.push进去的就是链尾的那个元素,再return list。重复过程,知道回到第一次递归前。理解了这个过程,就可以理解为什么递归本质来说就是一个栈结构。

重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历结果,请重建出该二叉树。假设输入的前序遍历和中序遍历都不含重复的数字。例如输入的前序序列为{1,2,4,7,3,5,6,8}和中序序列为{4,6,2,1,5,3,8,6},则重建二叉树并返回

1
2
时间限制: 1s
空间限制:32768k

题目分析

这道题涉及到了数据结构的内容,这里稍微复习一下

树是数据结构中最常见的结构之一,而前序遍历和中序遍历以及后续遍历则是树的三种遍历形式。由根节点在遍历过程中的顺序决定。

前序遍历(VLR):

  • 访问根节点
  • 前序遍历左子树
  • 前序遍历右子树

中序遍历(LVR):

  • 中序遍历左子树
  • 访问根节点
  • 中序遍历右子树

后序遍历(LRV):

  • 后序遍历左子树
  • 后续遍历右子树
  • 访问根节点

在做这种有关于数据结构的算法时,一定要注重递归的使用。

对于这道题来说,整个过程大概分为四步:

  • 确定根,确定左子树,确定右子树
  • 在左子树中递归第一步
  • 在右子树中递归第一步
  • 打印当前根

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
let pre = [1, 2, 4, 7, 3, 5, 6, 8],
vin = [4, 7, 2, 1, 5, 3, 8, 6];
function reConstructBinaryTree(pre, vin) {
if(pre.length === 0 || vin.length === 0) {
return null
}
const index = vin.indexOf(pre[0]),
vinleft = vin.slice(0, index),
vinright = vin.slice(index + 1),
preleft = pre.slice(1, index + 1),
preright = pre.slice(index + 1);
return {
val: pre[0],
left: reConstructBinaryTree(preleft, vinleft),
right: reConstructBinaryTree(preright, vinright)
};
}

重建二叉树

恢复出来是这样的一个二叉树

1
2
3
4
         1
2 3
4 5 6
7 8

由于这段程序过于精简,所以较为难理解。这里我们带入这组测试数据来分析一下左子树的递归过程

首先,函数的第一遍执行。根据前序遍历的特点,前序遍历结果的第一个数就是整个数的根,那么根据这个根的值去找它中序遍历中的位置。那么在中序遍历中,在这个位置前的就是左子树的中序遍历结果,后的就是右子树的中序遍历结果。同样的根据这个位置,从前序遍历中也可以分离出左子树和右子树的前序遍历结果。根据我们的测试数据pre = [1, 2, 4, 7, 3, 5, 6, 8], vin = [4, 7, 2, 1, 5, 3, 8, 6]; 可得preleft = [2, 4, 7], vinleft = [4, 7, 2]。这时我们return一个对象,val的值为1,left的值为递归调用的结果reConstructBinaryTree([2, 4, 7], [4, 7, 2])。重复分离的过程,2为左子树的根。preleft = [4, 7], vinleft = [4, 7]。 val 的值为 2,left = reConstructBinaryTree([4, 7], [4, 7])。然后到这里就没有左子树只有右子树了。右子树的递归过程与左子树相同。当一个节点的左右子树都为null是,开始层层往上返回结果,直到输出最后恢复的二叉树。

用两个栈实现队列

题目描述

用两个栈来实现一个队列,完成队列的Push和Pop操作

1
2
时间限制: 1s
空间限制: 32768k

题目分析

这道题我实在想不到其它适合的方法了。大体来说我们只能将一个栈用作输入,一个栈用作输出。压栈的话压入作为输入的栈,当要输出的时候,将作为输入的栈的值逐一输出并压入作为输出的栈,这样通过第二个栈来将原先的栈倒个序,从而实现队列的先进先出

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function Queue() {
this.inStack = [];
this.outStack = [];
}
Queue.prototype.Push = function(node) {
this.inStack.push(node);
}
Queue.prototype.Pop = function() {
if(!this.outStack.length) {
while(this.inStack.length) {
this.outStack.push(this.inStack.pop());
}
}
return this.outStack.pop();
}

这里将队列改写成了类的形式。大佬写的代码是这样的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const outStack = [],
inStack = [];
function push(node) {
// write code here
inStack.push(node);
}
function pop() {
// write code here
if (!outStack.length) {
while (inStack.length) {
outStack.push(inStack.pop());
}
}
return outStack.pop();
}

不得不说大佬还是牛逼,原先我以为这段代码写的是有问题的,但是在改写的过程中越想越觉得这段代码写的精妙。

通过两个数组来模拟栈结构,且只使用push和pop来模拟栈的压入和退出。

其中if和while的判断写的真的是牛逼。显示判断输出的outStack是否是个空数组,是的话开始进行从inStack到outStack的输出输入过程,将inStack的最后一位删除并输入到outStack,知道inStack的长度为0。完成了这个数组的倒序过程。然后返回outStack.pop()的结果。这就是outStack的栈顶也就是inStack栈的栈尾,成功的实现了队列的先进先出。

而且更精妙的是,在outStack彻底输出空之前,压入的数据都先存在inStack中,当outStack输出空后,再执行一次倒序

两个栈实现队列

文章目录
  1. 1. 二维数组的查找
  2. 2. 替换空格
  3. 3. 从尾到头打印链表
  4. 4. 重建二叉树
  5. 5. 用两个栈实现队列
|