LeetCode刷题笔记 - JavaScript（二）

剑指 Offer 60. n个骰子的点数
面试题67. 把字符串转换成整数
面试题59 - II. 队列的最大值

1.剑指 Offer 60. n个骰子的点数

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

题目大意：求n个投掷n个骰子可能出现的所有和的概率。
解题思路：设dp[i][j]为投掷i个骰子时，点数和为j的概率。当新增加一枚骰子时，dp[i+1][j+1…6] = dp[i][j]/6。因为每轮循环只用到dp[i-1],因此只需要两个一维数组交替计算。

代码：

2.面试题67. 把字符串转换成整数

题目大意：将一个字符串中的数组部分抽取出来。
解题思路：模拟题，考虑好边界问题即可。即字符串是否为空或全空格，去除空格后的首字符是否是有效整数字符，以及是否超出32位整数边界。然后循环取出数字即可。

代码：

3.面试题59 - II. 队列的最大值

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1

题目大意：实现一个求队列最大值的均摊时间复杂度为O(1)的队列。
解题思路：维护一个单调队列。

代码：