🌟欢迎来到 我的博客 —— 探索技术的无限可能！
23.最佳观光组合
题目链接：1014. 最佳观光组合
给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。
一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。
返回一对观光景点能取得的最高分。
示例 1：
输入：values = [8,1,5,2,6]
输出：11
解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11
示例 2：
输入：values = [1,2]
输出：2
提示：
2 <= values.length <= 5 * 104
1 <= values[i] <= 1000
题解：
方法：枚举
class Solution { public int maxScoreSightseeingPair(int[] values) { int ans = 0; int mx = values[0]; // j 左边的 values[i] + i 的最大值 for (int j = 1; j < values.length; j++) { ans = Math.max(ans, mx + values[j] - j); mx = Math.max(mx, values[j] + j); } return ans; } }
24.字符串中最多数目的子序列
题目链接：2207. 字符串中最多数目的子序列
给你一个下标从 0 开始的字符串 text 和另一个下标从 0 开始且长度为 2 的字符串 pattern ，两者都只包含小写英文字母。
你可以在 text 中任意位置插入 一个 字符，这个插入的字符必须是 pattern[0] 或者 pattern[1] 。注意，这个字符可以插入在 text 开头或者结尾的位置。
请你返回插入一个字符后，text 中最多包含多少个等于 pattern 的 子序列 。
子序列 指的是将一个字符串删除若干个字符后（也可以不删除），剩余字符保持原本顺序得到的字符串。
示例 1：
输入：text = “abdcdbc”, pattern = “ac”
输出：4
解释：
如果我们在 text[1] 和 text[2] 之间添加 pattern[0] = ‘a’ ，那么我们得到 “abadcdbc” 。那么
“ac” 作为子序列出现 4 次。
其他得到 4 个 “ac” 子序列的方案还有 “aabdcdbc” 和 “abdacdbc” 。
但是，“abdcadbc” ，“abdccdbc” 和 “abdcdbcc” 这些字符串虽然是可行的插入方案，但是只出现了 3 次 “ac”
子序列，所以不是最优解。
可以证明插入一个字符后，无法得到超过 4 个 “ac” 子序列。
示例 2：
输入：text = “aabb”, pattern = “ab”
输出：6
解释： 可以得到 6 个 “ab” 子序列的部分方案为 “aaabb” ，“aaabb” 和 “aabbb” 。
提示：
1 <= text.length <= 105
pattern.length == 2
text 和 pattern 都只包含小写英文字母。
题解：
方法：贪心
class Solution { public long maximumSubsequenceCount(String text, String pattern) { char x = pattern.charAt(0); char y = pattern.charAt(1); long ans = 0; int cntX = 0; int cntY = 0; for (char c : text.toCharArray()) { if (c == y) { ans += cntX; cntY++; } if (c == x) { cntX++; } } return ans + Math.max(cntX, cntY); } }
25.公司命名
题目链接：2306. 公司命名
给你一个字符串数组 ideas 表示在公司命名过程中使用的名字列表。公司命名流程如下：
从 ideas 中选择 2 个 不同 名字，称为 ideaA 和 ideaB 。
交换 ideaA 和 ideaB 的首字母。
如果得到的两个新名字 都 不在 ideas 中，那么 ideaA ideaB（串联 ideaA 和 ideaB ，中间用一个空格分隔）是一个有效的公司名字。
否则，不是一个有效的名字。
返回 不同 且有效的公司名字的数目。
示例 1：
输入：ideas = [“coffee”,“donuts”,“time”,“toffee”]
输出：6
解释：下面列出一些有效的选择方案：
- (“coffee”, “donuts”)：对应的公司名字是 “doffee conuts” 。
- (“donuts”, “coffee”)：对应的公司名字是 “conuts doffee” 。
- (“donuts”, “time”)：对应的公司名字是 “tonuts dime” 。
- (“donuts”, “toffee”)：对应的公司名字是 “tonuts doffee” 。
- (“time”, “donuts”)：对应的公司名字是 “dime tonuts” 。
- (“toffee”, “donuts”)：对应的公司名字是 “doffee tonuts” 。 因此，总共有 6 个不同的公司名字。
下面列出一些无效的选择方案：
- (“coffee”, “time”)：在原数组中存在交换后形成的名字 “toffee” 。
- (“time”, “toffee”)：在原数组中存在交换后形成的两个名字。
- (“coffee”, “toffee”)：在原数组中存在交换后形成的两个名字。
示例 2：
输入：ideas = [“lack”,“back”]
输出：0
解释：不存在有效的选择方案。因此，返回 0 。
提示：
2 <= ideas.length <= 5 * 104
1 <= ideas[i].length <= 10
ideas[i] 由小写英文字母组成
ideas 中的所有字符串 互不相同
题解：
方法：按照首字母分组
class Solution { public long distinctNames(String[] ideas) { Set<String>[] groups = new HashSet[26]; Arrays.setAll(groups, i -> new HashSet<>()); for (String s : ideas) { groups[s.charAt(0) - 'a'].add(s.substring(1)); // 按照首字母分组 } long ans = 0; for (int a = 1; a < 26; a++) { // 枚举所有组对 for (int b = 0; b < a; b++) { int m = 0; // 交集的大小 for (String s : groups[a]) { if (groups[b].contains(s)) { m++; } } ans += (long) (groups[a].size() - m) * (groups[b].size() - m); } } return ans * 2; // 乘 2 放到最后 } }
26.数组元素和与数字和的绝对差
题目链接：2535. 数组元素和与数字和的绝对差
给你一个正整数数组 nums 。
元素和 是 nums 中的所有元素相加求和。
数字和 是 nums 中每一个元素的每一数位（重复数位需多次求和）相加求和。
返回 元素和 与 数字和 的绝对差。
注意：两个整数 x 和 y 的绝对差定义为 |x - y| 。
示例 1：
输入：nums = [1,15,6,3]
输出：9
解释：
nums 的元素和是 1 + 15 + 6 + 3 = 25 。
nums 的数字和是 1 + 1 + 5 + 6 + 3 = 16 。
元素和与数字和的绝对差是 |25 - 16| = 9 。
示例 2：
输入：nums = [1,2,3,4]
输出：0
解释：
nums 的元素和是 1 + 2 + 3 + 4 = 10 。
nums 的数字和是 1 + 2 + 3 + 4 = 10 。
元素和与数字和的绝对差是 |10 - 10| = 0 。
提示：
1 <= nums.length <= 2000
1 <= nums[i] <= 2000
题解：
方法：数学
class Solution { public int differenceOfSum(int[] nums) { int ans = 0; for (int x : nums) { ans += x; // 累加元素和 while (x > 0) { ans -= x % 10; // 减去数位和 x /= 10; } } return ans; } }
27.每种字符至少取 K 个
题目链接：2516. 每种字符至少取 K 个
给你一个由字符 ‘a’、‘b’、‘c’ 组成的字符串 s 和一个非负整数 k 。每分钟，你可以选择取走 s 最左侧 还是 最右侧 的那个字符。
你必须取走每种字符 至少 k 个，返回需要的 最少 分钟数；如果无法取到，则返回 -1 。
示例 1：
输入：s = “aabaaaacaabc”, k = 2
输出：8
解释：
从 s 的左侧取三个字符，现在共取到两个字符 ‘a’ 、一个字符 ‘b’ 。
从 s 的右侧取五个字符，现在共取到四个字符 ‘a’ 、两个字符 ‘b’ 和两个字符 ‘c’ 。
共需要 3 + 5 = 8 分钟。
可以证明需要的最少分钟数是 8 。
示例 2：
输入：s = “a”, k = 1
输出：-1
解释：无法取到一个字符 ‘b’ 或者 ‘c’，所以返回 -1 。
提示：
1 <= s.length <= 105
s 仅由字母 ‘a’、‘b’、‘c’ 组成
0 <= k <= s.length
题解：
方法：滑动窗口
class Solution { public int takeCharacters(String s, int k) { int[] cnt = new int[3]; int n = s.length(); for (int i = 0; i < n; ++i) { ++cnt[s.charAt(i) - 'a']; } for (int x : cnt) { if (x < k) { return -1; } } int mx = 0, j = 0; for (int i = 0; i < n; ++i) { int c = s.charAt(i) - 'a'; --cnt[c]; while (cnt[c] < k) { ++cnt[s.charAt(j++) - 'a']; } mx = Math.max(mx, i - j + 1); } return n - mx; } }
28.以组为单位订音乐会的门票
题目链接：2286. 以组为单位订音乐会的门票
一个音乐会总共有 n 排座位，编号从 0 到 n - 1 ，每一排有 m 个座椅，编号为 0 到 m - 1 。你需要设计一个买票系统，针对以下情况进行座位安排：
同一组的 k 位观众坐在 同一排座位，且座位连续 。
k 位观众中 每一位 都有座位坐，但他们 不一定 坐在一起。
由于观众非常挑剔，所以：
只有当一个组里所有成员座位的排数都 小于等于 maxRow ，这个组才能订座位。每一组的 maxRow 可能 不同 。
如果有多排座位可以选择，优先选择 最小 的排数。如果同一排中有多个座位可以坐，优先选择号码 最小 的。
请你实现 BookMyShow 类：
BookMyShow(int n, int m) ，初始化对象，n 是排数，m 是每一排的座位数。
int[] gather(int k, int maxRow) 返回长度为 2 的数组，表示 k 个成员中 第一个座位 的排数和座位编号，这 k 位成员必须坐在 同一排座位，且座位连续 。换言之，返回最小可能的 r 和 c 满足第 r 排中 [c, c + k - 1] 的座位都是空的，且 r <= maxRow 。如果 无法 安排座位，返回 [] 。
boolean scatter(int k, int maxRow) 如果组里所有 k 个成员 不一定 要坐在一起的前提下，都能在第 0 排到第 maxRow 排之间找到座位，那么请返回 true 。这种情况下，每个成员都优先找排数 最小 ，然后是座位编号最小的座位。如果不能安排所有 k 个成员的座位，请返回 false 。
示例 1：
输入：
[“BookMyShow”, “gather”, “gather”, “scatter”, “scatter”]
[[2, 5], [4, 0], [2, 0], [5, 1], [5, 1]]
输出：
[null, [0, 0], [], true, false]
解释：
BookMyShow bms = new BookMyShow(2, 5); // 总共有 2 排，每排 5 个座位。
bms.gather(4, 0); // 返回 [0, 0]
// 这一组安排第 0 排 [0, 3] 的座位。
bms.gather(2, 0); // 返回 []
// 第 0 排只剩下 1 个座位。 // 所以无法安排 2 个连续座位。
bms.scatter(5, 1); // 返回 True
// 这一组安排第 0 排第 4 个座位和第 1 排 [0, 3] 的座位。
bms.scatter(5, 1); // 返回 False
// 总共只剩下 1 个座位。
提示：
1 <= n <= 5 * 104
1 <= m, k <= 109
0 <= maxRow <= n - 1
gather 和 scatter 总 调用次数不超过 5 * 104 次。
题解：
方法：线段树二分
class BookMyShow { private int n; private int m; private int[] min; private long[] sum; public BookMyShow(int n, int m) { this.n = n; this.m = m; int size = 2 << (32 - Integer.numberOfLeadingZeros(n)); // 比 4n 更小 min = new int[size]; sum = new long[size]; } public int[] gather(int k, int maxRow) { // 找第一个能倒入 k 升水的水桶 int r = findFirst(1, 0, n - 1, maxRow, m - k); if (r < 0) { // 没有这样的水桶 return new int[]{}; } int c = (int) querySum(1, 0, n - 1, r, r); update(1, 0, n - 1, r, k); // 倒水 return new int[]{r, c}; } public boolean scatter(int k, int maxRow) { // [0,maxRow] 的接水量之和 long s = querySum(1, 0, n - 1, 0, maxRow); if (s > (long) m * (maxRow + 1) - k) { return false; // 水桶已经装了太多的水 } // 从第一个没有装满的水桶开始 int i = findFirst(1, 0, n - 1, maxRow, m - 1); while (k > 0) { int left = Math.min(m - (int) querySum(1, 0, n - 1, i, i), k); update(1, 0, n - 1, i, left); // 倒水 k -= left; i++; } return true; } // 把下标 i 上的元素值增加 val private void update(int o, int l, int r, int i, int val) { if (l == r) { min[o] += val; sum[o] += val; return; } int m = (l + r) / 2; if (i <= m) { update(o * 2, l, m, i, val); } else { update(o * 2 + 1, m + 1, r, i, val); } min[o] = Math.min(min[o * 2], min[o * 2 + 1]); sum[o] = sum[o * 2] + sum[o * 2 + 1]; } // 返回区间 [L,R] 内的元素和 private long querySum(int o, int l, int r, int L, int R) { if (L <= l && r <= R) { return sum[o]; } long res = 0; int m = (l + r) / 2; if (L <= m) { res = querySum(o * 2, l, m, L, R); } if (R > m) { res += querySum(o * 2 + 1, m + 1, r, L, R); } return res; } // 返回区间 [0,R] 中 <= val 的最靠左的位置，不存在时返回 -1 private int findFirst(int o, int l, int r, int R, int val) { if (min[o] > val) { return -1; // 整个区间的元素值都大于 val } if (l == r) { return l; } int m = (l + r) / 2; if (min[o * 2] <= val) { return findFirst(o * 2, l, m, R, val); } if (R > m) { return findFirst(o * 2 + 1, m + 1, r, R, val); } return -1; } } /** * Your BookMyShow object will be instantiated and called as such: * BookMyShow obj = new BookMyShow(n, m); * int[] param_1 = obj.gather(k,maxRow); * boolean param_2 = obj.scatter(k,maxRow); */
29.买票需要的时间
题目链接：2073. 买票需要的时间
有 n 个人前来排队买票，其中第 0 人站在队伍 最前方 ，第 (n - 1) 人站在队伍 最后方 。
给你一个下标从 0 开始的整数数组 tickets ，数组长度为 n ，其中第 i 人想要购买的票数为 tickets[i] 。
每个人买票都需要用掉 恰好 1 秒 。一个人 一次只能买一张票 ，如果需要购买更多票，他必须走到 队尾 重新排队（瞬间 发生，不计时间）。如果一个人没有剩下需要买的票，那他将会 离开 队伍。
返回位于位置 k（下标从 0 开始）的人完成买票需要的时间（以秒为单位）。
示例 1：
输入：tickets = [2,3,2], k = 2
输出：6
解释：
队伍一开始为 [2,3,2]，第 k 个人以下划线标识。
在最前面的人买完票后，队伍在第 1 秒变成 [3,2,1]。
继续这个过程，队伍在第 2 秒变为[2,1,2]。
继续这个过程，队伍在第 3 秒变为[1,2,1]。
继续这个过程，队伍在第 4 秒变为[2,1]。
继续这个过程，队伍在第 5 秒变为[1,1]。
继续这个过程，队伍在第 6 秒变为[1]。第 k 个人完成买票，所以返回 6。
示例 2：
输入：tickets = [5,1,1,1], k = 0
输出：8
解释：
队伍一开始为 [5,1,1,1]，第 k 个人以下划线标识。
在最前面的人买完票后，队伍在第 1 秒变成 [1,1,1,4]。
继续这个过程 3 秒，队伍在第 4 秒变为[4]。
继续这个过程 4 秒，队伍在第 8 秒变为[]。第 k 个人完成买票，所以返回 8。
提示：
n == tickets.length
1 <= n <= 100
1 <= tickets[i] <= 100
0 <= k < n
题解：
方法：数学
class Solution { public int timeRequiredToBuy(int[] tickets, int k) { int ans = 0; int tk = tickets[k]; for (int i = 0; i < tickets.length; i++) { ans += Math.min(tickets[i], (i <= k ? tk : tk - 1)); } return ans; } }
