808. 分汤
# 808. 分汤
有 A 和 B 两种类型 的汤。一开始每种类型的汤有 n 毫升。有四种分配操作：
提供 100ml 的 汤 A 和 0ml 的 汤 B 。
提供 75ml 的 汤 A 和 25ml 的 汤 B 。
提供 50ml 的 汤 A 和 50ml 的 汤 B 。
提供 25ml 的 汤 A 和 75ml 的 汤 B 。
当我们把汤分配给某人之后，汤就没有了。每个回合，我们将从四种概率同为 0.25 的操作中进行分配选择。如果汤的剩余量不足以完成某次操作，我们将尽可能分配。当两种类型的汤都分配完时，停止操作。
注意 不存在先分配 100 ml 汤 B 的操作。
需要返回的值： 汤 A 先分配完的概率 + 汤 A 和汤 B 同时分配完的概率 / 2。返回值在正确答案 10-5 的范围内将被认为是正确的。
示例 1:
输入: n = 50输出: 0.62500解释:如果我们选择前两个操作，A 首先将变为空。对于第三个操作，A 和 B 会同时变为空。对于第四个操作，B 首先将变为空。所以 A 变为空的总概率加上 A 和 B 同时变为空的概率的一半是 0.25 *(1 + 1 + ...
799. 香槟塔
# 799. 香槟塔
我们把玻璃杯摆成金字塔的形状，其中 第一层 有 1 个玻璃杯， 第二层 有 2 个，依次类推到第 100 层，每个玻璃杯 (250ml) 将盛有香槟。
从顶层的第一个玻璃杯开始倾倒一些香槟，当顶层的杯子满了，任何溢出的香槟都会立刻等流量的流向左右两侧的玻璃杯。当左右两边的杯子也满了，就会等流量的流向它们左右两边的杯子，依次类推。（当最底层的玻璃杯满了，香槟会流到地板上）
例如，在倾倒一杯香槟后，最顶层的玻璃杯满了。倾倒了两杯香槟后，第二层的两个玻璃杯各自盛放一半的香槟。在倒三杯香槟后，第二层的香槟满了 - 此时总共有三个满的玻璃杯。在倒第四杯后，第三层中间的玻璃杯盛放了一半的香槟，他两边的玻璃杯各自盛放了四分之一的香槟，如下图所示。
现在当倾倒了非负整数杯香槟后，返回第 i 行 j 个玻璃杯所盛放的香槟占玻璃杯容积的比例（ i 和 j 都从 0 开始）。
示例 1:
输入: poured(倾倒香槟总杯数) = 1, query_glass(杯子的位置数) = 1, query_row(行数) = 1输出: 0.00000解释: 我们在顶层（下标是（0，0））倒了一 ...
1732. 找到最高海拔
# 1732. 找到最高海拔
有一个自行车手打算进行一场公路骑行，这条路线总共由 n + 1 个不同海拔的点组成。自行车手从海拔为 0 的点 0 开始骑行。
给你一个长度为 n 的整数数组 gain ，其中 gain [i] 是点 i 和点 i + 1 的 净海拔高度差（0 <= i < n）。请你返回 最高点的海拔 。
示例 1：
输入：gain = [-5,1,5,0,-7]输出：1解释：海拔高度依次为 [0,-5,-4,1,1,-6] 。最高海拔为 1 。
示例 2：
输入：gain = [-4,-3,-2,-1,4,3,2]输出：0解释：海拔高度依次为 [0,-4,-7,-9,-10,-6,-3,-1] 。最高海拔为 0 。
提示：
n == gain.length
1 <= n <= 100
-100 <= gain[i] <= 100
# 题解
class Solution {public: int largestAltitude(vector<int>& gain) { i ...
891. 子序列宽度之和
# 891. 子序列宽度之和
一个序列的 宽度 定义为该序列中最大元素和最小元素的差值。
给你一个整数数组 nums ，返回 nums 的所有非空 子序列 的 宽度之和 。由于答案可能非常大，请返回对 109 + 7 取余 后的结果。
子序列 定义为从一个数组里删除一些（或者不删除）元素，但不改变剩下元素的顺序得到的数组。例如，[3,6,2,7] 就是数组 [0,3,1,6,2,2,7] 的一个子序列。
示例 1：
输入：nums = [2,1,3]输出：6解释：子序列为 [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3] 。相应的宽度是 0, 0, 0, 1, 1, 2, 2 。宽度之和是 6 。
示例 2：
输入：nums = [2]输出：0
提示：
1 <= nums.length <= $10^5$
1 <= nums[i] <= $10^5$
# 题解
class Solution {public: int sumSubseqWidths(vector<int>& nums) ...
792. 匹配子序列的单词数
# 792. 匹配子序列的单词数
给定字符串 s 和字符串数组 words, 返回 words [i] 中是 s 的子序列的单词个数 。
字符串的 子序列 是从原始字符串中生成的新字符串，可以从中删去一些字符 (可以是 none)，而不改变其余字符的相对顺序。
例如， “ace” 是 “abcde” 的子序列。
示例 1:
输入: s = "abcde", words = ["a","bb","acd","ace"]输出: 3解释: 有三个是 s 的子序列的单词: "a", "acd", "ace"。
示例 2:
输入: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]输出: 2
提示:
1 <= s.length <= 5 ...
775. 全局倒置与局部倒置
# 775. 全局倒置与局部倒置
给你一个长度为 n 的整数数组 nums ，表示由范围 [0, n - 1] 内所有整数组成的一个排列。
全局倒置 的数目等于满足下述条件不同下标对 (i, j) 的数目：
0 <= i < j < n
nums[i] > nums[j]
局部倒置 的数目等于满足下述条件的下标 i 的数目：
0 <= i < n - 1
nums[i] > nums[i + 1]
当数组 nums 中 全局倒置 的数量等于 局部倒置 的数量时，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [1,0,2]输出：true解释：有 1 个全局倒置，和 1 个局部倒置。
示例 2：
输入：nums = [1,2,0]输出：false解释：有 2 个全局倒置，和 1 个局部倒置。
提示：
n == nums.length
1 <= n <= $10^5$
0 <= nums[i] < n
nums 中的所有整数 互不相同
nums 是范围 [0, n - ...
1710. 卡车上的最大单元数
# 1710. 卡车上的最大单元数
请你将一些箱子装在 一辆卡车 上。给你一个二维数组 boxTypes ，其中 boxTypes [i] = [numberOfBoxesi, numberOfUnitsPerBoxi] ：
numberOfBoxesi 是类型 i 的箱子的数量。
numberOfUnitsPerBoxi 是类型 i 每个箱子可以装载的单元数量。
整数 truckSize 表示卡车上可以装载 箱子 的 最大数量 。只要箱子数量不超过 truckSize ，你就可以选择任意箱子装到卡车上。
返回卡车可以装载 单元 的 最大 总数。
示例 1：
输入：boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4输出：8解释：箱子的情况如下：- 1 个第一类的箱子，里面含 3 个单元。- 2 个第二类的箱子，每个里面含 2 个单元。- 3 个第三类的箱子，每个里面含 1 个单元。可以选择第一类和第二类的所有箱子，以及第三类的一个箱子。单元总数 = (1 * 3) + (2 * 2) + (1 * 1) = 8
示例 2：
输入：boxTyp ...
805. 数组的均值分割
# 805. 数组的均值分割
给定你一个整数数组 nums
我们要将 nums 数组中的每个元素移动到 A 数组 或者 B 数组中，使得 A 数组和 B 数组不为空，并且 average (A) == average (B) 。
如果可以完成则返回 true ， 否则返回 false 。
注意：对于数组 arr , average (arr) 是 arr 的所有元素的和除以 arr 长度。
示例 1:
输入: nums = [1,2,3,4,5,6,7,8]输出: true解释: 我们可以将数组分割为 [1,4,5,8] 和 [2,3,6,7], 他们的平均值都是4.5。
示例 2:
输入: nums = [3,1]输出: false
提示:
1 <= nums.length <= 30
0 <= nums[i] <= $10^4$
# 题解
class Solution {public: bool splitArraySameAverage(vector<int>& nums) { int n ...
791. 自定义字符串排序
# 791. 自定义字符串排序
给定两个字符串 order 和 s 。order 的所有单词都是 唯一 的，并且以前按照一些自定义的顺序排序。
对 s 的字符进行置换，使其与排序的 order 相匹配。更具体地说，如果在 order 中的字符 x 出现字符 y 之前，那么在排列后的字符串中， x 也应该出现在 y 之前。
返回 满足这个性质的 s 的任意排列 。
示例 1:
输入: order = "cba", s = "abcd"输出: "cbad"解释: “a”、“b”、“c”是按顺序出现的，所以“a”、“b”、“c”的顺序应该是“c”、“b”、“a”。因为“d”不是按顺序出现的，所以它可以在返回的字符串中的任何位置。“dcba”、“cdba”、“cbda”也是有效的输出。
示例 2:
输入: order = "cbafg", s = "abcd"输出: "cbad"
提示:
1 <= order.length <= 26
1 <= s.len ...
790. 多米诺和托米诺平铺
# 790. 多米诺和托米诺平铺
有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 “L” 的托米诺形。两种形状都可以旋转。
给定整数 n ，返回可以平铺 2 x n 的面板的方法的数量。返回对 $10^9 + 7$ 取模 的值。
平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。
示例 1:
输入: n = 3输出: 5解释: 五种不同的方法如上所示。
示例 2:
输入: n = 1输出: 1
提示：
1 <= n <= 1000
# 题解
const long long mod = 1e9 + 7;class Solution {public: int numTilings(int n) { vector<vector<long long>> dp(n + 1, vector<long long>(4)); dp[0][3] = 1; for (int i ...