秋招复习计划-算法题7

  |  

前言

继续刷leetcode


66



删除链表的倒数第N个节点

题目内容

删除节点

解题过程

两次遍历的方法,首先我们要找倒数第N个,就得知道链表总长L。那么我们要找到倒数第N个,就是正数L-N+1个。为了应对特殊的情况,譬如链表只有一个节点,或者我们要删除的正好是第一个节点。我们在原有头节点前再加一个我们的节点,那么我们现在要删除的节点就是整数L-N+2个,而要删除第L-N+2个节点,我们需要将L-N+1个节点的next属性指向L-N+3,那么从第一个节点到第L-N+1个节点之间有L-N个间隔,所以我们的代码是这样的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var removeNthFromEnd = function(head, n) {
let newHead = {};
newHead.next = head;
let length = 0;
let first = head;
while(first !== null) {
length++;
first = first.next;
}
length -= n;
first = newHead;
while(length > 0) {
length--;
first = first.next;
}
first.next = first.next.next;
return newHead.next;
}

删除节点结果1

因为要遍历两遍链表,所以执行时间很慢。那么有没有只遍历一次就解决的办法。有

我们利用两个指针,要知道,倒数第N个节点和最后一个节点之间差N-1个间隔,那我们让第一个指针指向头节点,第二个指针指向整数N+1(N-1+1+1)个节点,然后同时向后遍历,当第二个指针指向最后一个节点时,第一个指针正好指向需要删除的节点的前一个节点。同样为了避免特殊情况,我们让需要加一个空的头节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var removeNthFromEnd = function(head, n) {
let dump = {};
dump.next = head;
let first = dump,
second = dump;
for(let i = 0; i < n + 1; i++) {
first = first.next;
}
while(first !== null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dump.next;
}

删除节点结果2

N叉树的前序遍历

题目内容

前序遍历

解题过程

这道题还是很简单的。递归的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var preorder = function(root) {
let result = [];
function order(node) {
if(!node) return;
result.push(node.val);
if(node.children) {
for(let item of node.children) {
order(item);
}
}
}
order(root);
return result;
}

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var preorder = function(root) {
if (!root) return [];

var res = [], arr = [root];
while(arr.length){
var current = arr.pop();
res.push(current.val);

for(var i = current.children.length - 1; i >= 0; i--){
arr.push(current.children[i]);
}
}
return res;
};

这里数组children之所以要从后往前遍历,是因为这个题目的输入很弱智,如果子树是从左往右的顺序是[3,2,4],它的children数组确实[4,2,3]。

灯泡开关

题目内容

灯泡开关

解题过程

这道题目乍一看感觉很难,其实我们只要仔细看他的要求,所有开着的灯都变成蓝色。拿什么情况下所有的灯会变蓝,就是所有亮着的灯是从1开始的顺序排序。那么如果是顺序排序的话,那所有亮着的灯的序号的最大值应该等于当前light数组的下标+1。我们选个例子来分析,light = [2,1,3,5,4]。当第0时刻,也就是light[0],2号灯亮,这个时候亮着的灯的最大序号是2,当light[1]时,下标+1等于2,1号灯亮,这个时候, 亮灯最大的下标还是2,等于下标加一,这个时候刚好所有的亮灯都是蓝灯

所以我们只要根据这个判断条件来写就行了

1
2
3
4
5
6
7
8
9
var numTimesAllBlue = function(light) {
let time = 0,
maxNum = 0;
for(let i = 0, length = light.length; i < length; i++) {
maxNum = Math.max(maxNum, light[i]);
if(maxNum === i+1) time++;
}
return time;
}

灯泡开关结果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
25
26
27
28
29
30
31
32
33
34
35
36
var getMaximumGold = function(grid) {
let result = 0;
if(grid.length === 0) return result;
let rowLimit = grid.length,
colLimit = grid[0].length;
let ways = [
[-1, 0],
[1, 0],
[0, -1],
[0, 1]
];
function dps(count, row, col) {
result = Math.max(count, result);
for(let i = 0; i < 4; i++) {
let crow = row + ways[i][0],
ccol = col + ways[i][1];
if(crow < 0 || ccol < 0 || crow >= rowLimit || ccol >= colLimit || grid[crow][ccol] === 0) {
continue;
}
let temp = grid[crow][ccol];
grid[crow][ccol] = 0;
dps(count + temp, crow, ccol);
grid[crow][ccol] = temp; // 回退
}
}
for(let i = 0; i < rowLimit; i++) {
for(let j = 0; j < colLimit; j++) {
if(grid[i][j] === 0) continue;
let remeber = grid[i][j];
grid[i][j] = 0;
dps(remeber, i, j);
grid[i][j] = remeber;
}
}
return result;
}

黄金矿工提交结果

每日温度

题目内容

每日温度

解题过程

最简单的方法,循环嵌套

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var dailyTemperatures = function(T) {
let nextDays = [];
T.forEach((item, index) => {
let nextDay = 0;
for(let x = index + 1; x < T.length; x++) {
if (T[x] > item) {
nextDay = x - index;
break;
}
}
nextDays.push(nextDay);
})
return nextDays;
}

巨慢无比

每日温度提交结果1

单调栈的方法

先说单调栈,

单调栈就是栈内元素保持一定单调性(单调递增或单调递减)的栈。这里的单调递增或递减是指的从栈顶栈底单调递增或递减。既然是栈,就满足后进先出的特点。

例如,现在有一个数组 [3, 4, 2, 6, 4, 5, 2, 3],从左到右依次入栈,单调递增栈的实现。

1
2
3
4
5
6
7
8
9
10
11
// 单调递增栈的实现
let arr = [3, 4, 2, 6, 4, 5, 2, 3]
let res = []

for (let i = 0; i < arr.length; i++) {
while (res.length && res[res.length - 1] < arr[i]) {
res.pop()
}
res.push(arr[i])
}
console.log(res) // [6, 5, 3]

将破坏栈单调性的元素都出栈,结果从栈顶到栈底单调递增或者递减。

了解了单调栈之后,再来看这道题。

  1. 维护一个单调递增栈,栈内存储气温数组 T 的 index
  2. 查看当前元素是否大于栈顶元素所对应的 T 的值,也就是 T[stack[stack.length - 1]]
  3. 如果大于,那说明找到需要等待的天数。如果不大于那说明还没到找到比这天高的温度。同时继续维护这个单调栈
  4. 如果大于,需要等待的天数就是当前数组 T 的下标减去单调栈顶对应的下标,然后出栈
  5. 循环完毕,还没有找到需要等待的天数,为0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @param {number[]} T
* @return {number[]}
*/
var dailyTemperatures = function(T) {
let { length } = T
let res = new Array(length).fill(0)
let stack = []
for(let i = 0; i < length; i++) {

while(stack.length && T[i] > T[stack[stack.length - 1]]) {
let index = stack.pop()
res[index] = i - index
}
stack.push(i)

}
return res
};
文章目录
  1. 1. 删除链表的倒数第N个节点
    1. 1.1. 题目内容
    2. 1.2. 解题过程
  2. 2. N叉树的前序遍历
    1. 2.1. 题目内容
    2. 2.2. 解题过程
  3. 3. 灯泡开关
    1. 3.1. 题目内容
    2. 3.2. 解题过程
  4. 4. 黄金矿工
    1. 4.1. 题目内容
    2. 4.2. 解题过程
  5. 5. 每日温度
    1. 5.1. 题目内容
    2. 5.2. 解题过程