这周题目是真的难到有毒。
100144. Find the Peaks
给你一个下标从 0 开始的数组 mountain 。你的任务是找出数组 mountain 中的所有 峰值。
以数组形式返回给定数组中 峰值 的下标，顺序不限 。
注意：
峰值 是指一个严格大于其相邻元素的元素。
数组的第一个和最后一个元素 不 是峰值。测试样例：
输入：mountain = [2,4,4]
输出：[]
解释：mountain[0] 和 mountain[2] 不可能是峰值，因为它们是数组的第一个和最后一个元素。mountain[1] 也不可能是峰值，因为它不严格大于 mountain[2] 。因此，答案为 [] 。
解答：这题难度不大，暴力扫描就行。
class Solution {
public List<Integer> findPeaks(int[] mountain) {
List<Integer> res = new ArrayList<>();
int len = mountain.length - 1;
for (int i = 1; i < len; ++i) {
if (mountain[i] > mountain[i - 1] && mountain[i] > mountain[i + 1]) {
res.add(i);
}
}
return res;
}
}100153. Minimum Number of Coins to be Added
给你一个下标从 0 开始的整数数组 coins，表示可用的硬币的面值，以及一个整数 target 。
如果存在某个 coins 的子序列总和为 x，那么整数 x 就是一个 可取得的金额 。
返回需要添加到数组中的 任意面值 硬币的 最小数量 ，使范围 [1, target] 内的每个整数都属于 可取得的金额 。
数组的 子序列 是通过删除原始数组的一些（可能不删除）元素而形成的新的 非空 数组，删除过程不会改变剩余元素的相对位置。
测试样例：
输入：coins = [1,4,10], target = 19
输出：2
解释：需要添加面值为 2 和 8 的硬币各一枚，得到硬币数组 [1,2,4,8,10] 。可以证明从 1 到 19 的所有整数都可由数组中的硬币组合得到，且需要添加到数组中的硬币数目最小为 2 。
解答：这是一道以前的Hard题目，模版题目。cur是当前满足的最大可取得金额。cur从0开始，如果当前的数字coin <= (cur + 1), 由于小与cur的都能去到，则当前cur + cur + 1范围就都能取得了。否则用递增添加硬币。
class Solution {
public int minimumAddedCoins(int[] coins, int target) {
Arrays.sort(coins);
long cur = 0;
int res = 0;
for (int i : coins) {
int tmp = Math.min(i, target);
while (tmp > cur + 1) {
++res;
cur = cur * 2 + 1;
}
cur += tmp;
}
while (target > cur) {
++res;
cur = cur * 2 + 1;
}
return res;
}
}100145. Count Complete Substrings
给你一个字符串 word 和一个整数 k 。
如果 word 的一个子字符串 s 满足以下条件，我们称它是 完全字符串：
- s 中每个字符 恰好 出现 k 次。
- 相邻字符在字母表中的顺序 至多 相差 2 。也就是说，s 中两个相邻字符 c1 和 c2 ，它们在字母表中的位置相差 至多 为 2 。
请你返回 word 中 完全 子字符串的数目。
子字符串 指的是一个字符串中一段连续 非空 的字符序列。
测试样例：
输入：word = "igigee", k = 2
输出：3
解释：完全子字符串需要满足每个字符恰好出现 2 次，且相邻字符相差至多为 2 ：igigee, igigee, igigee 。
解答：这道题目，关键要理解，任何一个位置只有26个可能形成完全字符串的位置（k, 2k, ... , 26k）。
class Solution {
private static final int[] empty = new int[26];
public int countCompleteSubstrings(String word, int k) {
int[] cur = empty;
int[][] wordCharMem = new int[word.length() + 1][];
wordCharMem[0] = empty;
int res = 0, breakPoint = 0;
for (int i = 0; i < word.length(); ++i) {
if (i >= 1 && Math.abs(word.charAt(i) - word.charAt(i - 1)) > 2) {
breakPoint = i;
}
cur = duplicate(cur);
int o = word.charAt(i) - 'a';
cur[o] = cur[o] + 1;
wordCharMem[i + 1] = cur;
boolean sureBreak = false;
for (int p = i - k + 1; p >= breakPoint; p = p - k) {
boolean isValid = true;
for (int j = 0; j < 26; ++j) {
int d = wordCharMem[i + 1][j] - wordCharMem[p][j];
if (d != 0 && d != k) {
if (d > k) sureBreak = true;
isValid = false;
break;
}
}
if (isValid) {
++res;
}
if (sureBreak) {
break;
}
}
}
return res;
}
private int[] duplicate(int[] arr) {
int[] nextArr = new int[arr.length];
System.arraycopy(arr, 0, nextArr, 0, arr.length);
return nextArr;
}
}100146. Count the Number of Infection Sequences
给你一个整数 n 和一个下标从 0 开始的整数数组 sick ，数组按 升序 排序。
有 n 位小朋友站成一排，按顺序编号为 0 到 n - 1 。数组 sick 包含一开始得了感冒的小朋友的位置。如果位置为 i 的小朋友得了感冒，他会传染给下标为 i - 1 或者 i + 1 的小> 朋友，前提 是被传染的小朋友存在且还没有得感冒。每一秒中， 至多一位 还没感冒的小朋友会被传染。
经过有限的秒数后，队列中所有小朋友都会感冒。感冒序列 指的是 所有 一开始没有感冒的小朋友最后得感冒的顺序序列。请你返回所有感冒序列的数目。
由于答案可能很大，请你将答案对 109 + 7 取余后返回。
注意，感冒序列 不 包含一开始就得了感冒的小朋友的下标。
测试样例：
输入：n = 5, sick = [0,4]
输出：4
解释：一开始，下标为 1 ，2 和 3 的小朋友没有感冒。总共有 4 个可能的感冒序列：
- 一开始，下标为 1 和 3 的小朋友可以被传染，因为他们分别挨着有感冒的小朋友 0 和 4 ，令下标为 1 的小朋友先被传染。
然后，下标为 2 的小朋友挨着感冒的小朋友 1 ，下标为 3 的小朋友挨着感冒的小朋友 4 ，两位小朋友都可以被传染，令下标为 2 的小朋友被传染。
最后，下标为 3 的小朋友被传染，因为他挨着感冒的小朋友 2 和 4 ，感冒序列为 [1,2,3] 。- 一开始，下标为 1 和 3 的小朋友可以被传染，因为他们分别挨着感冒的小朋友 0 和 4 ，令下标为 1 的小朋友先被传染。
然后，下标为 2 的小朋友挨着感冒的小朋友 1 ，下标为 3 的小朋友挨着感冒的小朋友 4 ，两位小朋友都可以被传染，令下标为 3 的小朋友被传染。
最后，下标为 2 的小朋友被传染，因为他挨着感冒的小朋友 1 和 3 ，感冒序列为 [1,3,2] 。- 感冒序列 [3,1,2] ，被传染的顺序：[0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] 。
- 感冒序列 [3,2,1] ，被传染的顺序：[0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] 。
解答：第四题需要很多数学知识。夹在2个感染小朋友之间的感染路线一共有2^(n - 1)种，这个逻辑其实很简单假设0和n感染了，1到n-1之间必然感染的是1或者n-1号，感染之后剩下n - 2个人，这样可以获得公式：f(n) = 2 * f(n - 1)。
剩下的就是各个子序列编织在一起，用组合公式就行了。
class Solution {
private class MulInv {
private int mod;
private HashMap<Integer, Long> mem;
public MulInv(int mod) {
this.mod = mod;
this.mem = new HashMap<>();
}
public long inv(int x) {
if (!mem.containsKey(x)) {
mem.put(x, quickMul(x, mod - 2));
}
return mem.get(x);
}
private long quickMul(int x, int y) {
long res = 1, cur = x;
while (y > 0) {
if (y % 2 == 1) {
res = res * cur % mod;
}
cur = cur * cur % mod;
y /= 2;
}
return res;
}
}
private static final int mod = 1_000_000_007;
private static HashMap<Integer, Long> mul = new HashMap<>();
private MulInv inv = new MulInv(mod);
public int numberOfSequence(int n, int[] sick) {
long res = 1;
int total = n - sick.length;
for (int i = 1; i < sick.length; ++i) {
int diff = (sick[i] - sick[i - 1] - 1);
long c = combine(diff, total);
long totalPos = quickMul(diff - 1);
long curPos = (c * totalPos) % mod;
res = (res * curPos) % mod;
total -= diff;
}
if (sick[0] != 0) {
int diff = (sick[0]);
long c = combine(diff, total);
res = (res * c) % mod;
total -= diff;
}
if (sick[sick.length - 1] < n - 1) {
int diff = n - sick[sick.length - 1] - 1;
long c = combine(diff, total);
res = (res * c) % mod;
}
return (int) res;
}
public int combine(int x, int y) {
long tmp = 1;
for (int i = 0; i < x; ++i) {
tmp = (tmp * (y - i)) % mod;
tmp = (tmp * inv.inv(i + 1)) % mod;
}
return (int) tmp;
}
private long quickMul(int x) {
if (x == 1) {
return 2;
} else if (x == 0) {
return 1;
} else if (!mul.containsKey(x)) {
long tmp = quickMul(x / 2);
long res = tmp * tmp % mod;
if (x % 2 == 1) {
res = (res * 2) % mod;
}
mul.put(x, res);
}
return mul.get(x);
}
}