前言
「小孩子别装成熟。妳们就是光读恋爱小说才会这样。」
「才……才没有，其他书我也读得很多啊！」 珂朵莉似乎不否认自己有读恋爱小说这件事。 大概是因为发烧，或者慌乱得露出本性的关系，她讲的话变得有些奇怪。而且，当事人好像并没有自觉。
整体评价
前三题比较简单， t3想到同余就是秒解，t4感觉方法还是蛮多的。珂朵莉MM用了两次单调栈+离线处理，感觉写复杂了。
比赛入口： 第 90 双周赛
更多解题报告详见：珂朵莉MM的解题报告汇总
T1. 差值数组不同的字符串
做差分数组, 掐掉了首元素，因为单词数才100，长度上限也为100，如果两两比较，这样比较时间复杂度最多
确实对差分数组，hash的话，会很快.
方法一：莽
Java
class Solution {
public String oddString(String[] words) {
int n = words.length;
int m = words[0].length();
int[][] arr = new int[n][m - 1];
for (int i = 0; i < n; i++) {
String w = words[i];
char[] buf = w.toCharArray();
for (int j = 0; j < buf.length - 1; j++) {
arr[i][j] = (int)(buf[j + 1] - buf[j]);
}
}
for (int i = 0; i < n; i++) {
int diff = 0;
for (int j = 0; j < n; j++) {
if (i != j && !Arrays.equals(arr[i], arr[j])) {
diff++;
}
}
if (diff > 1) return words[i];
}
// unreachable
return null;
}
}方法二： hash表
两次遍历，这样就变成.
Java
class Solution {
public String specialHashString(String word) {
StringBuilder sb = new StringBuilder();
char[] buf = word.toCharArray();
for (int j = 0; j < buf.length - 1; j++) {
sb.append((int)(buf[j + 1] - buf[j])).append(",");
}
return sb.toString();
}
public String oddString(String[] words) {
int n = words.length;
Map<String, Integer> hash = new HashMap<>();
for (int i = 0; i < n; i++) {
String h = specialHashString(words[i]);
hash.put(h, hash.getOrDefault(h, 0) + 1);
}
for (int i = 0; i < n; i++) {
String h = specialHashString(words[i]);
if (hash.get(h) == 1) return words[i];
}
// unreachable
return null;
}
}T2. 距离字典两次编辑以内的单词
这题，第一眼的想法，竟然是字典树， 不过呢？幸好把这个邪恶的念头掐掉了， 因为最多2个改动，可不好搞，还是直接莽比较稳妥。
也算是力扣特色，前两题，尽量以莽为主。
方法一： 莽
Java
class Solution {
boolean dist(String p, String s) {
int diff =0;
for (int i = 0; i < p.length(); i++) {
if (p.charAt(i) != s.charAt(i)) {
diff++;
}
if (diff > 2) return false;
}
return true;
}
public List<String> twoEditWords(String[] queries, String[] dictionary) {
List<String> result = new ArrayList<>();
for (int i = 0; i < queries.length; i++) {
String q = queries[i];
boolean f = false;
for (int j = 0; j < dictionary.length; j++) {
if (dist(q, dictionary[j])) {
f = true;
break;
}
}
if (f) {
result.add(q);
}
}
return result;
}
}方法二： 字典树(补充)
Java
class Solution {
static class Trie {
Trie[] childs = new Trie[26];
boolean tag;
public static void addWord(Trie root, String word) {
Trie cur = root;
for (int i = 0; i < word.length(); i++) {
int p = word.charAt(i) - 'a';
if (cur.childs[p] == null) {
cur.childs[p] = new Trie();
}
cur = cur.childs[p];
}
cur.tag = true;
}
public static boolean search(Trie root, String word, int idx, int limit) {
if (word.length() <= idx) {
return root.tag;
}
int p = word.charAt(idx) - 'a';
if (root.childs[p] != null) {
if (Trie.search(root.childs[p], word, idx + 1, limit)) {
return true;
}
}
if (limit > 0) {
for (int i = 0; i < 26; i++) {
if (root.childs[i] != null) {
if (Trie.search(root.childs[i], word, idx + 1, limit - 1)) {
return true;
}
}
}
}
return false;
}
}
public List<String> twoEditWords(String[] queries, String[] dictionary) {
Trie root = new Trie();
for (String w: dictionary) {
Trie.addWord(root, w);
}
List<String> result = new ArrayList<>();
for (String q: queries) {
if (Trie.search(root, q, 0, 2)) {
result.add(q);
}
}
return result;
}
}T3. 摧毁一系列目标
看到 , 大概就猜到了同余。
然后按照同余进行分组，其实就是hash计数，这样的话，就比较简单了。
其实可以用一个循环的，不过比赛中，感觉思路清晰，比代码简洁更重要.
Java
class Solution {
public int destroyTargets(int[] nums, int space) {
TreeMap<Integer, Integer> hash = new TreeMap<>();
for (int v: nums) {
int no = v % space;
hash.put(no, hash.getOrDefault(no, 0) + 1);
}
int ans = 0;
int idx = 0;
for (int i = 0; i < nums.length; i++) {
int no = nums[i] % space;
int cnt = hash.get(no);
if (cnt > ans) {
ans = cnt;
idx = nums[i];
} else if (cnt == ans && idx > nums[i]) {
idx = nums[i];
}
}
return idx;
}
}T4. 下一个更大元素 IV
方法一：两次单调栈+离线处理
用了两次单调栈+离线处理
- 第一次单调栈，逆序构建，主要是确定每个元素的第一大的元素位置信息
- 根据第一大的元素信息，进行排序，这就是所谓的离线处理
- 第二次单调栈，这一次，主要是为每个元素查找第二大元素，做铺垫的。
其实第二次单调栈，可以用其他数据结构代替了，比如优先队列，BST，这样话，其实更方便，而且不容易错。
Java
class Solution {
public int[] secondGreaterElement(int[] nums) {
// 先单调栈
int n = nums.length;
int[] idx = new int[n];
Stack<Integer> stack = new Stack<>();
// 第一次用单调栈
for (int i = n - 1; i >= 0; i--) {
int v = nums[i];
while (!stack.isEmpty() && v >= nums[stack.peek()]) {
stack.pop();
}
if (!stack.isEmpty()) {
idx[i] = stack.peek();
} else {
idx[i] = -1;
}
stack.push(i);
}
// 离线处理，先排序
Integer[] xls = IntStream.range(0, n).boxed().toArray(Integer[]::new);
Arrays.sort(xls, Comparator.comparingInt(x -> idx[x]));
int j = xls.length - 1;
int[] barr = new int[n];
int ptr = 0;
// 第二次用单调栈
int[] res = new int[n];
Arrays.fill(res, -1);
for (int i = n - 1; i >= 0; i--) {
// 离线批量处理，寻找起第二大的元素
while (j >= 0 && idx[xls[j]] == i) {
// 这是二分寻找
int l = 0, r = ptr - 1;
int v = nums[xls[j]];
while (l <= r) {
int m = l + (r - l) / 2;
if (nums[barr[m]] <= v) {
r = m - 1;
} else {
l = m + 1;
}
}
if (r == -1) {
res[xls[j]] = -1;
} else {
res[xls[j]] = nums[barr[r]];
}
j--;
}
// 维护单调栈
int tv = nums[i];
while (ptr >= 1 && tv >= nums[barr[ptr - 1]]) {
ptr--;
}
barr[ptr++] = i;
}
return res;
}
}方法二：双堆模拟
巧妙用了两个堆结构，进行第一大，第二大的分离.
Java
class Solution {
public int[] secondGreaterElement(int[] nums) {
PriorityQueue<int[]> first = new PriorityQueue<>(Comparator.comparing(x -> x[0]));
PriorityQueue<int[]> second = new PriorityQueue<>(Comparator.comparing(x -> x[0]));
int[] res = new int[nums.length];
Arrays.fill(res, -1);
for (int i = 0; i < nums.length; i++) {
int v = nums[i];
while (!second.isEmpty() && second.peek()[0] < v) {
int[] cur = second.poll();
res[cur[1]] = v;
}
while (!first.isEmpty() && first.peek()[0] < v) {
second.offer(first.poll());
}
first.offer(new int[] {v, i});
}
return res;
}
}写在最后
珂朵莉MM还是菜菜，尽想一些复杂的思路，差点绕进去了......
评论 (4)
