【笔记】JavaScript版数据结构与算法——数据结构之“栈”(682. 棒球比赛)
2023-09-27 14:26:51 时间
682. 棒球比赛
1.题目
你现在是棒球比赛记录员。
给定一个字符串列表,每个字符串可以是以下四种类型之一:
- 整数(一轮的得分):直接表示您在本轮中获得的积分数。
- “+”(一轮的得分):表示本轮获得的得分是前两轮有效 回合得分的总和。
- “D”(一轮的得分):表示本轮获得的得分是前一轮有效 回合得分的两倍。
- “C”(一个操作,这不是一个回合的分数):表示您获得的最后一个有效 回合的分数是无效的,应该被移除。
每一轮的操作都是永久性的,可能会对前一轮和后一轮产生影响。
你需要返回你在所有回合中得分的总和。
示例 1:
- 输入: [“5”,“2”,“C”,“D”,"+"]
- 输出: 30
- 解释:
第1轮:你可以得到5分。总和是:5。
第2轮:你可以得到2分。总和是:7。
操作1:第2轮的数据无效。总和是:5。
第3轮:你可以得到10分(第2轮的数据已被删除)。总数是:15。
第4轮:你可以得到5 + 10 = 15分。总数是:30。
示例 2:
- 输入: [“5”,"-2",“4”,“C”,“D”,“9”,"+","+"]
- 输出: 27
- 解释:
第1轮:你可以得到5分。总和是:5。
第2轮:你可以得到-2分。总数是:3。
第3轮:你可以得到4分。总和是:7。
操作1:第3轮的数据无效。总数是:3。
第4轮:你可以得到-4分(第三轮的数据已被删除)。总和是:-1。
第5轮:你可以得到9分。总数是:8。
第6轮:你可以得到-4 + 9 = 5分。总数是13。
第7轮:你可以得到9 + 5 = 14分。总数是27。
注意:
- 输入列表的大小将介于1和1000之间。
- 列表中的每个整数都将介于-30000和30000之间。
题目模板
/**
* @param {string[]} ops
* @return {number}
*/
var calPoints = function(ops) {
};
2.思路分析
细节详见题解
3.所用到的方法
方法 | 描述 |
---|---|
forEach() | 数组每个元素都执行一次回调函数。 |
map() | 通过指定函数处理数组的每个元素,并返回处理后的数组。 |
pop() | 删除数组的最后一个元素并返回删除的元素。 |
push() | 向数组的末尾添加一个或更多元素,并返回新的长度。 |
reduce() | 将数组元素计算为一个值(从左到右)。 参数: ① total 必需。初始值, 或者计算结束后的返回值。 ② currentValue 必需。当前元素 ③ currentIndex 可选。当前元素的索引 ④ arr 可选。当前元素所属的数组对象。 |
shift() | 删除并返回数组的第一个元素。 |
unshift() | 向数组的开头添加一个或更多元素,并返回新的长度。 |
4.题解及优化
我的题解
let calPoints = ops => {
let score = [0]
ops.map(item => {
switch (item) {
case '+':
score.push(score[score.length - 1] + score[score.length - 2])
break
case 'C':
score.pop()
break
case 'D':
score.push(score[score.length - 1] * 2)
break
default:
score.push(item * 1)
break
}
})
return score.reduce((pre, cur) => pre + cur) // 有效分数求和返回
}
console.log('结果:', calPoints(['5', '-2', '4', 'C', 'D', '9', '+', '+'])) // 27
console.log('结果:', calPoints(['5', '2', 'C', 'D', '+'])) // 30
使用堆栈的思想:
let calPoints = ops => {
let score = []
// 上一轮的数据
let pre1
// 上上轮的数据
let pre2
ops.forEach(item => {
switch (item) {
case 'C':
if (score.length) {
score.pop()
}
break
case 'D':
pre1 = score.pop()
score.push(pre1, pre1 * 2)
break
case '+':
pre1 = score.pop()
pre2 = score.pop()
score.push(pre2, pre1, pre2 + pre1)
break
default:
score.push(item * 1)
}
})
return score.reduce((pre, cur) => pre + cur) // 有效分数求和返回
}
console.log('结果:', calPoints(['5', '-2', '4', 'C', 'D', '9', '+', '+'])) // 27
console.log('结果:', calPoints(['5', '2', 'C', 'D', '+'])) // 30
其他小伙伴的解法
var calPoints = function(ops) {
for (let i = 0; i < ops.length; i++) {
if (ops[i] === 'C') {
ops.splice(i - 1, 2)
i -= 2
}
}
let res = 0
for(let i = 0; i < ops.length; i++){
if(ops[i] === 'D'){
ops[i] = +(ops[i - 1] || 0) * 2
} else if(ops[i] === '+') {
ops[i] = +(ops[i - 1] || 0) + +(ops[i - 2] || 0)
}
res += +ops[i]
}
return res
};
相关文章
- JavaScript语言基础3
- 【JS】JavaScript的循环命令示例(for/for each/do while)
- 前端基础 - JavaScript之innerHTML方法
- JavaScript - 数组排序 6 种常见算法
- 《JavaScript设计模式》——9.2 Module(模块)模式
- 《HTML、CSS、JavaScript 网页制作从入门到精通》——1.3 使用浏览器浏览HTML文件
- 《第三方JavaScript编程》——7.4 发布者漏洞
- 《JavaScript精粹(修订版)》——1.2 JavaScript的限制
- JavaScript中unicode编码与String互转(三种方法)
- 三张图搞懂JavaScript的原型对象与原型链
- 华为OD机试 - 打印文件(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 投篮大赛(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - Excel单元格数值统计(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 自动曝光(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 -路灯照明(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 重组字符串(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 最优调度策略(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 跳格子(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 密室逃生游戏(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 -预订酒店(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 交换字符(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 找单词(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 新学校选址(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- 如何进行高效JavaScript单元测试
- javascript中的原型和闭包
- javascript中不存在块级作用域,所以要小心使用在块级作用域中的函数声明所带来的作用域混乱.
- JavaScript SVG分叉树