秋招复习计划-算法题6

  |  

前言

为了让每次编程都能获得结果,开始刷LeetCode上面的题,一次五道


57



两数之和

题目内容

两数之和

解题过程

这道题很简单,我们一下子就能想到使用双层循环嵌套

1
2
3
4
5
6
7
8
9
var twoSum = function(nums, target) {
for(let i = 0, length = nums.length; i < length; i++) {
for(let j = i + 1; j < length; j++) {
if(nums[i] + nums[j] == target) {
return [i, j];
}
}
}
}

这么写没有任何问题,但是特定就是慢而且占用内存也比较大

两数之和提交结果1

那么接下来我们就需要考虑如何优化。这里我又想到了一个办法,利用indexOf函数。但不知道能不能更快,我们试一下

1
2
3
4
5
6
7
8
var twoSum = function(nums, target) {
for(let i = 0, length = nums.length; i < length; i++) {
let j = nums.indexOf(target - nums[i], i+1);
if(j !== -1) {
return [i,j]
}
}
}

很遗憾的是不仅没有变快,反而变慢了,但是由于降低了循环层数,所以消耗的内存减少了

两数之和提交结果2

那么有没有快的方法呢,有!

大佬写法,我们用数组去实现HashMap,先上代码

1
2
3
4
5
6
7
8
9
10
var twoSum = function(nums, target) {
var temp = [];
for(var i = 0; i < nums.length; i++) {
var dif = target - nums[i];
if(temp[dif] != undefined) {
return[temp[dif], i];
}
temp[nums[i]] = i;
}
}

我们构造一个以nums数组中值为下标,下标为值的数组,这样我们相减以后,可以直接以相减结果作为下标去搜索新数组,如果存在值,就说明存在结果,将数组中对应下标的值去除就是这个数在nums数组中的下标。大佬思路清晰

两数之和提交结果

腐烂的橘子

解题过程

腐烂的橘子

解题过程

这道简单的题,我一开始还真没想到解法。只想到了一个腐烂的橘子腐烂周围的过程怎么写,但是没想到怎么切入,也就是如何开始。后来看来一下评论,基础的BFS,瞬间明白过来了。如果不懂什么是BFS,我就简单的介绍一下。BFS,及广度优先遍历算法。首先创建一个队列,然后将满足要求的点放入队列,然后再从队列中注意提取点,在将点周围满足要求的点放入队列,直到遍历完成。写不出来这道题,最主要的就是我对BFS掌握的不够,我之前一直以为BFS是只能应用于树的算法。现在看来,这种所谓会传播的方式,也可利用BFS来解。

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
var orangesRotting = function(grid) {
var queue = [],
freshNum = 0;
row = grid.length,
col = grid[0].length;
// 遍历矩阵,获得新鲜橘子的数量,生成队列,存放腐烂橘子的左边和时间
for(let i = 0; i < row; i++) {
for(let j = 0; j < col; j++) {
if(grid[i][j] == 1) freshNum++;
if(grid[i][j] == 2) queue.push([i,j,0]);
}
}
if(freshNum == 0) return 0;
// 四个方向
var way = [[-1, 0], [0, 1], [1, 0], [0, -1]];
while(queue.length > 0) {
// 当前腐烂的橘子
var orange = queue.shift();
var time = orange[2];
// 朝四个方向开始腐烂
for(let i = 0; i < 4; i++) {
var r = orange[0] + way[i][0],
c = orange[1] + way[i][1];
// 判断是否越界以及是否是新鲜橘子
if(r < 0 || r >= row || c < 0 || c >= col || grid[r][c] != 1) continue;
grid[r][c] = 2;
if(--freshNum == 0) return time + 1;
queue.push([r, c, time + 1]);
}
}
if(freshNum != 0) {
return -1;
}
}

腐烂的橘子提交结果

独特的电子邮件地址

题目描述

独特的电子邮件地址

解题过程

首先我们考虑数组中的每个邮箱地址的特点,那就是需要处理的只有本地名称部分,域名不需要处理。所以我们可以把每个邮箱地址用@符号拆开,然后删掉本地名称中第一个加号及后面的内容,再删掉剩余字符串中的.号,最后将剩余字符串和域名用@拼接回去。

1
2
3
4
5
6
7
8
9
10
11
12
13
var numUniqueEmails = function(emailes) {
var result = [];
for(let i = 0,length = emailes.length; i < length; i++) {
var strArr = emailes[i].split('@');
var local = strArr[0]
if(local.includes('+'))
local = local.substring(0, local.indexOf('+'))
local = local.replace(/\./g, "");
var final = local + '@' + strArr[1]
if(!result.includes(final)) result.push(final);
}
return result.length;
}

电子邮件提交结果1

从结果来看,我们的代码质量还是可以的,直到我看到了一个大佬的写法

1
2
3
4
5
6
7
var numUniqueEmails = function(emails) {
return [...new Set(emails.map(item => {
let list = item.split('@')
list[0] = list[0].replace(/\./g,'').split('+')[0]
return list.join('@')
}))].length
};

写的相当精简,用map去遍历邮箱数组,用@分隔每个邮箱地址,删掉本地里的.号,再用+分隔,只取第一个,重新拼接后存入Set结构,然后解构赋值。刚开始我还在考虑这里的先Set结构再解构是不是有点多此一举,毕竟map方法返回的就是数组。仔细一想才明白,Set结构是为了防止重复。不过跑出来的结果也不太理想

电子邮箱提交结果2

由此可见写的精简不一定运行结果快,而且不太容易懂。

不过大佬写的代码还是有值得借鉴的地方的,至少在字符的处理上的代码比我们的精简,所以我改良了一下原有的代码

1
2
3
4
5
6
7
8
9
10
var numUniqueEmails = function(emailes) {
var result = [];
for(let i = 0,length = emailes.length; i < length; i++) {
let list = emailes[i].split('@');
list[0] = list[0].replace(/\./g, '').split('+')[0];
let final = list.join('@');
if(!result.includes(final)) result.push(final);
}
return result.length;
}

在D天内送达包裹的能力

题目描述

在D天内送达包裹的能力

解题过程

首先我们必须清楚船舶运载量的范围,那就是单个包裹的最大质量到所有包裹的质量总和。

既然有了个范围那么我们就可以暴力破解。循环遍历整个范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var shipWithinDays = function(weights, D){
let maxWeight = sumWeight = weights[0],
length = weights.length;
for(let i = 1;i < length; i++) {
if(weights[i] > maxWeight) maxWeight = weights[i];
sumWeight += weights[i];
}
for(let i = maxWeight; i <= sumWeight; i++){
let cur = i,
day = D;
for(let j = 0; j < length; j++){
if(weights[j] > cur) day--, cur = i;
cur = cur - weights[j]
}
if(day > 0) return i
}
}

这里我们是怎么判断一天能运多少的?我们定义一个变量cur,表示当前船舶还剩余多少载重量,如果包裹比当前的载重量大,那么就只能等明天,那么天数减一,再重置cur。如果最后day大于0,那么就说明当前的船舶载重量可行,由于我们是从小到大的递增,所以第一个满足条件的i就是我们最小的载重量。不过这种便利的破解方法他的时间复杂度是O(n),所以显然,跑起来很慢

送达包裹提交结果1

那么对于这种左右边界清晰的,我们是否有一种快速的查找方式了。答案就是二分法。

取左右边界的向下中值,如果中值满足送达条件,那么说明他可能不是最小的,将中值作为新的有边界。如果不满足送达条件,说明中值还太小了,那么将中值加1作为新的左边界。直到左右边界相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var shipWithinDays = function(weights, D) {
let left = 0, right = 0;
for(w of weights) {
left = Math.max(left, w);
right += w;
}
while(left < right) {
let mid = left + right >> 1;
canShip(weights, D, mid) ? right = mid : left = mid + 1;
}
return left;
function canShip(weights,D,M) {
let cur = M;
for(w of weights) {
if(w > cur) D--, cur = M;
cur -= w;
}
return D > 0;
}
}

二分查找,就是快

送达包裹提交结果2

跳跃游戏2

题目描述

跳跃游戏2

解题思路

首先就是想到了递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var jump = function(nums) {
var minStep = nums.length;
function canJump(position, nums, step) {
if(position == nums.length - 1){
minStep = Math.min(step,minStep);
}
var further = Math.min(position+nums[position], nums.length - 1);
for(var nextPosition = position + 1; nextPosition <= further; nextPosition++) {
canJump(nextPosition, nums, step+1);
}
}
canJump(0, nums, 0);
return minStep;
}

我们维护一个最小跳跃的次数。当跳跃到终点,我们就比较这次的跳跃次数和当前的最小次数,取最小值。每次可以跳跃的最长步数,我们取当前下标加该下标的值和数组长度比较后相对较小的值,防止越界。然后遍历递归可以跳跃的步数。最后返回最小步数。但是这种递归,太消耗计算资源了。所以不出意外的

跳跃游戏2提交结果1

超时了。

既然递归行不通,那就得另想办法了。再重新来看一眼题目,它特意说明了,假设你总是可以达到数组的最后一个位置。及在确定可达性的情况下,我们可以采用贪心算法。

及从初始位置开始,找到当前能跳跃范围内,下一跳能跳到最远的位置。举例说明。

数组是这样的

1
[2,3,1,1,4,2,1]

那么初始位置是下标0,值为2,及它可以跳到下标为1或为2的地方。那么我们到底是跳到下标1还是下标2呢,这就取决于我跳到的位置下一跳能跳到多远了。下标1的下一跳可以跳到1+3=下标4.而下标2的下一跳只能跳到2+1=下标3,所以我们就取最远的结果。这就是贪心算法,及在确保可达性的情况下, 我们什么都不考虑,只取最远的(或者也可以叫做目前最优的),因为不管我们怎么跳,一定能跳到终点。同理我们跳到下标1以后,我们跳到哪呢,那就是下标4.下标4的跳跃范围已经超过了数组长度了,所以在这里我们已经获得结果了,要提前退出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var jump = function(nums) {
var step = 0,
len = nums.length,
curCanJumpMax = 0,
lastCanJumpMax = 0;
for(var i = 0; i < len - 1; i++) {
// 当前能跳到的最远下标位置
curCanJumpMax = Math.max(curCanJumpMax, nums[i] + i);
// 如果已经到达上一条可以到达的最远下标,则更新上一跳可以跳到的最远下标 // 并增加步数
if(lastCanJumpMax == i) {
lastCanJumpMax = curCanJumpMax;
step++;
}
// 如果上一跳能到达的最远下标已经超过数组最大下标,则没有继续寻找下一跳最远能 // 跳多远的意义了,直接跳到重点就行了
if(lastCanJumpMax >= len - 1) break;
}
// 记得加上最后跳到终点的一跳
return step;
}

贪心算法一般就是这类问题的最优解了,因为根本就不需要考虑可达性

跳跃游戏2提交结果2

文章目录
  1. 1. 两数之和
    1. 1.1. 题目内容
    2. 1.2. 解题过程
  2. 2. 腐烂的橘子
    1. 2.1. 解题过程
    2. 2.2. 解题过程
  3. 3. 独特的电子邮件地址
    1. 3.1. 题目描述
    2. 3.2. 解题过程
  4. 4. 在D天内送达包裹的能力
    1. 4.1. 题目描述
    2. 4.2. 解题过程
  5. 5. 跳跃游戏2
    1. 5.1. 题目描述
    2. 5.2. 解题思路