剑指offer60 n个骰子的点数【DP】
题目描述
把n个骰子扔在地上,所有骰子朝上一面的点数之和为s。输入n,打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
示例 1:
1 | 输入: 1 |
示例 2:
1 | 输入: 2 |
限制:
1 | 1 <= n <= 11 |
把n个骰子扔在地上,所有骰子朝上一面的点数之和为s。输入n,打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
示例 1:
1 | 输入: 1 |
示例 2:
1 | 输入: 2 |
限制:
1 | 1 <= n <= 11 |
请定义一个队列并实现函数 max_value
得到队列里的最大值,要求函数max_value
、push_back
和 pop_front
的均摊时间复杂度都是O(1)。
若队列为空,pop_front
和 max_value
需要返回 -1
示例 1:
1 | 输入: |
示例 2:
1 | 输入: |
限制:
1 <= push_back,pop_front,max_value的总操作数 <= 10000
1 <= value <= 10^5
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如,输入字符串”abcdefg”和数字2,该函数将返回左旋转两位得到的结果”cdefgab”。
示例 1:
1 | 输入: s = "abcdefg", k = 2 |
示例 2:
1 | 输入: s = "lrloseumgh", k = 6 |
限制:
1 <= k < s.length <= 10000
输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。为简单起见,标点符号和普通字母一样处理。例如输入字符串”I am a student. “,则输出”student. a am I”。
示例 1:
1 | 输入: "the sky is blue" |
示例 2:
1 | 输入: " hello world! " |
示例 3:
1 | 输入: "a good example" |
说明:
输入一个正整数 target
,输出所有和为 target
的连续正整数序列(至少含有两个数)。
序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。
示例 1:
1 | 输入:target = 9 |
示例 2:
1 | 输入:target = 15 |
限制:
1 <= target <= 10^5
输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。
示例 1:
1 | 输入:nums = [2,7,11,15], target = 9 |
示例 2:
1 | 输入:nums = [10,26,30,31,47,60], target = 40 |
限制:
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
在一个数组 nums
中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1:
1 | 输入:nums = [3,4,3,3] |
示例 2:
1 | 输入:nums = [9,1,7,9,7,9,7] |
限制:
1 <= nums.length <= 10000
1 <= nums[i] < 2^31
一个整型数组 nums
里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是**O(n),空间复杂度是O(1)**。
示例 1:
1 | 输入:nums = [4,1,4,6] |
示例 2:
1 | 输入:nums = [1,2,10,4,1,4,3,3] |
限制:
2 <= nums.length <= 10000
输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
1 | 3 |
返回 true
。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1 | 1 |
返回 false
。
限制:
0 <= 树的结点个数 <= 10000