- H 1157.子数组中占绝大多数的元素 4.16
- E 2409.统计共同度过的日子数 4.17
- M 1026.节点与其祖先之间的最大差值 4.18
- M 1043.分隔数组以得到最大和 4.19
- H 1187.使数组严格递增 4.20
- E 2413.最小偶倍数 4.21
- M 1027.最长等差数列
https://leetcode-cn.com/problems/online-majority-element-in-subarray
设计一个数据结构，有效地找到给定子数组的 多数元素 。
子数组的 多数元素 是在子数组中出现 threshold 次数或次数以上的元素。
实现 MajorityChecker 类:
MajorityChecker(int[] arr) 会用给定的数组 arr 对 MajorityChecker 初始化。int query(int left, int right, int threshold) 返回子数组中的元素 arr[left...right] 至少出现 threshold 次数，如果不存在这样的元素则返回 -1 。示例 1：
输入:
["MajorityChecker", "query", "query", "query"]
[[[1, 1, 2, 2, 1, 1]], [0, 5, 4], [0, 3, 3], [2, 3, 2]]
输出：
[null, 1, -1, 2]
解释：
MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]);
majorityChecker.query(0,5,4); // 返回 1
majorityChecker.query(0,3,3); // 返回 -1
majorityChecker.query(2,3,2); // 返回 2
提示：
1 <= arr.length <= 2 * 10^41 <= arr[i] <= 2 * 10^40 <= left <= right < arr.lengththreshold <= right - left + 12 * threshold > right - left + 1query 的次数最多为 10^4标签
设计 树状数组 线段树 数组 二分查找
https://leetcode-cn.com/problems/count-days-spent-together
Alice 和 Bob 计划分别去罗马开会。
给你四个字符串 arriveAlice ， leaveAlice ， arriveBob 和 leaveBob 。Alice 会在日期 arriveAlice 到 leaveAlice 之间在城市里（ 日期为闭区间 ），而 Bob 在日期 arriveBob 到 leaveBob 之间在城市里（ 日期为闭区间 ）。每个字符串都包含 5 个字符，格式为 "MM-DD" ，对应着一个日期的月和日。
请你返回 Alice和 Bob 同时在罗马的天数。
你可以假设所有日期都在 同一个 自然年，而且 不是 闰年。每个月份的天数分别为： [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] 。
示例 1：
输入：arriveAlice = "08-15", leaveAlice = "08-18", arriveBob = "08-16", leaveBob = "08-19"
输出：3
解释：Alice 从 8 月 15 号到 8 月 18 号在罗马。Bob 从 8 月 16 号到 8 月 19 号在罗马，他们同时在罗马的日期为 8 月 16、17 和 18 号。所以答案为 3 。
示例 2：
输入：arriveAlice = "10-01", leaveAlice = "10-31", arriveBob = "11-01", leaveBob = "12-31"
输出：0
解释：Alice 和 Bob 没有同时在罗马的日子，所以我们返回 0 。
提示：
"MM-DD" 。标签
数学 字符串
https://leetcode-cn.com/problems/maximum-difference-between-node-and-ancestor
给定二叉树的根节点 root ，找出存在于 不同 节点 A 和 B 之间的最大值 V ，其中 V = |A.val - B.val| ，且 A 是 B 的祖先。
（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）
示例 1：
输入：root = [8,3,10,1,6,null,14,null,null,4,7,13]
输出：7
解释：
我们有大量的节点与其祖先的差值，其中一些如下：
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。
示例 2：
输入：root = [1,null,2,null,0,3]
输出：3
提示：
2 到 5000 之间。0 <= Node.val <= 10^5标签
树 深度优先搜索 二叉树
https://leetcode-cn.com/problems/partition-array-for-maximum-sum
给你一个整数数组 arr ，请你将该数组分隔为长度 最多 为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。
返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。
示例 1：
输入：arr = [1,15,7,9,2,5,10], k = 3
输出：84
解释：数组变为 [15,15,15,9,10,10,10]
示例 2：
输入：arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
输出：83
示例 3：
输入：arr = [1], k = 1
输出：1
提示：
1 <= arr.length <= 5000 <= arr[i] <= 10^91 <= k <= arr.length标签
数组 动态规划
https://leetcode-cn.com/problems/make-array-strictly-increasing
给你两个整数数组 arr1 和 arr2 ，返回使 arr1 严格递增所需要的最小「操作」数（可能为 0）。
每一步「操作」中，你可以分别从 arr1 和 arr2 中各选出一个索引，分别为 i 和 j ， 0 <= i < arr1.length 和 0 <= j < arr2.length ，然后进行赋值运算 arr1[i] = arr2[j] 。
如果无法让 arr1 严格递增，请返回 -1 。
示例 1：
输入：arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
输出：1
解释：用 2 来替换 5，之后 arr1 = [1, 2, 3, 6, 7]。
示例 2：
输入：arr1 = [1,5,3,6,7], arr2 = [4,3,1]
输出：2
解释：用 3 来替换 5，然后用 4 来替换 3，得到 arr1 = [1, 3, 4, 6, 7]。
示例 3：
输入：arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
输出：-1
解释：无法使 arr1 严格递增。
提示：
1 <= arr1.length, arr2.length <= 20000 <= arr1[i], arr2[i] <= 10^9标签
数组 二分查找 动态规划 排序
https://leetcode-cn.com/problems/smallest-even-multiple
给你一个正整数 n ，返回 2 和 n 的最小公倍数（正整数）。
示例 1：
输入：n = 5
输出：10
解释：5 和 2 的最小公倍数是 10 。
示例 2：
输入：n = 6
输出：6
解释：6 和 2 的最小公倍数是 6 。注意数字会是它自身的倍数。
提示：
1 <= n <= 150标签
数学 数论
https://leetcode-cn.com/problems/longest-arithmetic-subsequence
给你一个整数数组 nums ，返回 nums 中最长等差子序列的 长度 。
回想一下， nums 的子序列是一个列表 nums[i<sub>1</sub>], nums[i<sub>2</sub>], ..., nums[i<sub>k</sub>] ，且 0 <= i<sub>1</sub> < i<sub>2</sub> < ... < i<sub>k</sub> <= nums.length - 1 。并且如果 seq[i+1] - seq[i] ( 0 <= i < seq.length - 1 ) 的值都相同，那么序列 seq 是等差的。
示例 1：
输入：nums = [3,6,9,12]
输出：4
解释：
整个数组是公差为 3 的等差数列。
示例 2：
输入：nums = [9,4,7,2,10]
输出：3
解释：
最长的等差子序列是 [4,7,10]。
示例 3：
输入：nums = [20,1,15,3,10,5,8]
输出：4
解释：
最长的等差子序列是 [20,15,10,5]。
提示：
2 <= nums.length <= 10000 <= nums[i] <= 500标签
数组 哈希表 二分查找 动态规划