欢迎大家加QQ群：623375442，可以方便群里面交流。
100452. Minimum Element After Replacement With Digit Sum
给你一个整数数组 nums 。
请你将 nums 中每一个元素都替换为它的各个数位之 和 。
请你返回替换所有元素以后 nums 中的 最小 元素。
测试样例：
输入：nums = [10,12,13,14]
输出：1
解释：nums 替换后变为 [1, 3, 4, 5] ，最小元素为 1 。
解答：按照题意暴力计算。
class Solution {
public int minElement(int[] nums) {
int res = Integer.MAX_VALUE;
for (int n : nums) {
int digit = 0;
while (n > 0) {
digit += n % 10;
n /= 10;
}
res = Math.min(res, digit);
}
return res;
}
}100374. Maximize the Total Height of Unique Towers
给你一个数组 maximumHeight ，其中 maximumHeight[i] 表示第 i 座塔可以达到的 最大 高度。
你的任务是给每一座塔分别设置一个高度，使得：
- 第 i 座塔的高度是一个正整数，且不超过 maximumHeight[i] 。
- 所有塔的高度互不相同。
请你返回设置完所有塔的高度后，可以达到的 最大 总高度。如果没有合法的设置，返回 -1 。返回 result 。
测试样例：
输入：maximumHeight = [2,3,4,3]
输出：10
解释：
我们可以将塔的高度设置为：[1, 2, 4, 3] 。
解答：利用贪婪计算。
class Solution {
public long maximumTotalSum(int[] maximumHeight) {
Arrays.sort(maximumHeight);
long res = 0, cur = Long.MAX_VALUE;
for (int i = maximumHeight.length - 1; i >= 0; --i) {
if (maximumHeight[i] <= cur) {
res += maximumHeight[i];
cur = maximumHeight[i] - 1;
} else {
if (cur <= 0) {
return -1;
}
res += cur;
cur -= 1;
}
}
return res;
}
}100437. Find the Lexicographically Smallest Valid Sequence
给你两个字符串 word1 和 word2 。
如果一个字符串 x 修改 至多 一个字符会变成 y ，那么我们称它与 y 几乎相等 。
如果一个下标序列 seq 满足以下条件，我们称它是 合法的 ：
- 下标序列是 升序 的。
- 将 word1 中这些下标对应的字符 按顺序 连接，得到一个与 word2 几乎相等 的字符串。
请你返回一个长度为 word2.length 的数组，表示一个 字典序最小 的 合法 下标序列。如果不存在这样的序列，请你返回一个 空 数组。
注意 ，答案数组必须是字典序最小的下标数组，而 不是 由这些下标连接形成的字符串。
测试样例：
输入：word1 = "vbcca", word2 = "abc"
输出：[0,1,2]
解释：字典序最小的合法下标序列为 [0, 1, 2] ：
- 将 word1[0] 变为 'a' 。
- word1[1] 已经是 'b' 。
- word1[2] 已经是 'c' 。
解答：我觉得这周最难的就是这题。我们先从后遍历word2，寻找能满足word2后缀匹配的最大word1距离。然后正向计算最小的更换一次的结果。
class Solution {
private static final int[] failed = {};
public int[] validSequence(String word1, String word2) {
TreeSet<Integer>[] sets = new TreeSet[26];
for (int i = 0; i < 26; ++i) {
sets[i] = new TreeSet<>();
}
for (int i = 0; i < word1.length(); ++i) {
sets[word1.charAt(i) - 'a'].add(i);
}
int[] minLeft = new int[word2.length() + 1];
Arrays.fill(minLeft, -1);
minLeft[word2.length()] = word1.length();
for (int i = word2.length() - 1; i >= 0; --i) {
// 从后向前寻找能够匹配word2后缀的最大word1的位置
int o = word2.charAt(i) - 'a';
Integer tmp = sets[o].lower(minLeft[i + 1]);
if (tmp == null) {
break;
}
minLeft[i] = tmp;
}
int last = -1;
int[] res = new int[word2.length()];
// 正向计算
for (int i = 0; i < word2.length(); ++i) {
Integer tmp = sets[word2.charAt(i) - 'a'].higher(last);
// 如果当前位置就是可以匹配的，直接继续。
if (tmp != null && tmp == last + 1) {
res[i] = tmp;
last = tmp;
} else if (minLeft[i + 1] > i && minLeft[i + 1] > last + 1) {
for (int j = i; j < word2.length(); ++j) {
if (j != i) {
res[j] = sets[word2.charAt(j) - 'a'].higher(res[j - 1]);
} else {
res[j] = last + 1;
}
}
return res;
} else {
if (tmp == null) {
break;
}
res[i] = tmp;
last = tmp;
}
}
if (word1.startsWith(word2)) {
return res;
}
return failed;
}
}100433. Find the Occurrence of First Almost Equal Substring
给你两个字符串 s 和 pattern 。
如果一个字符串 x 修改 至多 一个字符会变成 y ，那么我们称它与 y 几乎相等 。
请你返回 s 中下标 最小 的 子字符串 ，它与 pattern 几乎相等 。如果不存在，返回 -1 。
子字符串 是字符串中的一个 非空、连续的字符序列。
测试样例：
输入：s = "abcdefg", pattern = "bcdffg"
输出：1
解释：
将子字符串 s[1..6] == "bcdefg" 中 s[4] 变为 "f" ，得到 "bcdffg" 。
解答：利用Rolling Hash，寻找每个位置可以匹配的最大位置，然后查看剩下的位置是否能够匹配上。
class Solution {
private static final int mod = 1_000_000_007;
private static final int inv = 129032259;
private class RangeHash {
long[] prefix, div;
public RangeHash(String word) {
prefix = new long[word.length() + 1];
div = new long[word.length() + 1];
long mul = 1;
div[0] = 1;
for (int i = 0; i < word.length(); ++i) {
int t = word.charAt(i) - 'a';
prefix[i + 1] = (prefix[i] + t * mul) % mod;
mul = (mul * 31) % mod;
div[i + 1] = div[i] * inv % mod;
}
}
public long getRangeHash(int st, int ed) {
long diff = (prefix[ed + 1] - prefix[st] + mod) % mod;
return diff * div[st] % mod;
}
}
public int minStartingIndex(String s, String pattern) {
if (pattern.length() <= 1) {
return 0;
}
RangeHash sh = new RangeHash(s), ph = new RangeHash(pattern);
for (int i = 0; i <= s.length() - pattern.length(); ++i) {
int st = 0, ed = pattern.length() - 1;
// 折半搜索当前位置最大可以匹配的距离
while (st < ed) {
int mid = (st + ed) / 2;
if (sh.getRangeHash(i, i + mid) == ph.getRangeHash(0, mid)) {
st = mid + 1;
} else {
ed = mid;
}
}
if (st >= pattern.length() - 1) {
return i;
// 利用Rolling Hash快速计算一下剩下的位置是不是正确
} else if (ph.getRangeHash(st + 1, pattern.length() - 1)
== sh.getRangeHash(i + st + 1, i + pattern.length() - 1)) {
return i;
}
}
return -1;
}
}