这周有点拉跨啊，就搞出来2题。

记录一下吧:

每个字符最多出现两次的最长子字符串

给你一个字符串 s ，请找出满足每个字符最多出现两次的最长子字符串，并返回该子字符串的最大长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int maximumLengthSubstring(String S) {
        char[] s = S.toCharArray();
        int ans = 0;
        int left = 0;
        int[] cnt = new int[26];
        for (int i = 0; i < s.length; i++) {
            int b = s[i] - 'a';
            cnt[b]++;
            while (cnt[b] > 2) {
                cnt[s[left++] - 'a']--;
            }
            ans = Math.max(ans, i - left + 1);
        }
        return ans;
    }
}

最高频率的 ID

你需要在一个集合里动态记录 ID 的出现频率。给你两个长度都为 n 的整数数组 nums 和 freq ，nums 中每一个元素表示一个 ID ，对应的 freq 中的元素表示这个 ID 在集合中此次操作后需要增加或者减少的数目。

增加 ID 的数目：如果 freq[i] 是正数，那么 freq[i] 个 ID 为 nums[i] 的元素在第 i 步操作后会添加到集合中。 减少 ID 的数目：如果 freq[i] 是负数，那么 -freq[i] 个 ID 为 nums[i] 的元素在第 i 步操作后会从集合中删除。 请你返回一个长度为 n 的数组 ans ，其中 ans[i] 表示第 i 步操作后出现频率最高的 ID 数目 ，如果在某次操作后集合为空，那么 ans[i] 为 0 。

示例 1：

输入：nums = [2,3,2,1], freq = [3,2,-3,1]

输出：[3,3,2,2]

解释：

第 0 步操作后，有 3 个 ID 为 2 的元素，所以 ans[0] = 3 。 第 1 步操作后，有 3 个 ID 为 2 的元素和 2 个 ID 为 3 的元素，所以 ans[1] = 3 。 第 2 步操作后，有 2 个 ID 为 3 的元素，所以 ans[2] = 2 。 第 3 步操作后，有 2 个 ID 为 3 的元素和 1 个 ID 为 1 的元素，所以 ans[3] = 2 。

方法一：哈希表 + 有序集合

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public long[] mostFrequentIDs(int[] nums, int[] freq) {
        Map<Integer, Long> cnt = new HashMap<>();
        TreeMap<Long, Integer> m = new TreeMap<>();
        int n = nums.length;
        long[] ans = new long[n];
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            if (cnt.containsKey(x) && m.containsKey(cnt.get(x)) && m.merge(cnt.get(x), -1, Integer::sum) == 0) { // --m[cnt[x]] == 0
                m.remove(cnt.get(x));
            }
            long c = cnt.merge(x, (long) freq[i], Long::sum); // cnt[x] += freq[i]
            m.merge(c, 1, Integer::sum); // ++m[cnt[x]]
            ans[i] = m.lastKey();
        }
        return ans;
    }
}

方法二：哈希表 + 懒删除堆

也可以不用有序集合，而是用一个最大堆保存数对 (cnt[x],x)(\textit{cnt}[x], x)(cnt[x],x)。

在堆中查询 cnt[x]\textit{cnt}[x]cnt[x] 的最大值时，如果堆顶保存的数据并不是目前实际的 cnt[x]\textit{cnt}[x]cnt[x]，那么就弹出堆顶。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
    public long[] mostFrequentIDs(int[] nums, int[] freq) {
        int n = nums.length;
        long[] ans = new long[n];
        Map<Integer, Long> cnt = new HashMap<>();
        PriorityQueue<Pair<Long, Integer>> pq = new PriorityQueue<>((a, b) -> Long.compare(b.getKey(), a.getKey()));
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            long c = cnt.merge(x, (long) freq[i], Long::sum);
            pq.add(new Pair<>(c, x));
            while (!pq.peek().getKey().equals(cnt.get(pq.peek().getValue()))) { // 堆顶保存的数据已经发生变化
                pq.poll(); // 删除
            }
            ans[i] = pq.peek().getKey();
        }
        return ans;
    }
}

最长公共后缀查询

给你两个字符串数组 wordsContainer 和 wordsQuery 。

对于每个 wordsQuery[i] ，你需要从 wordsContainer 中找到一个与 wordsQuery[i] 有 最长公共后缀 的字符串。如果 wordsContainer 中有两个或者更多字符串有最长公共后缀，那么答案为长度 最短 的。如果有超过两个字符串有 相同 最短长度，那么答案为它们在 wordsContainer 中出现 更早 的一个。

请你返回一个整数数组 ans ，其中 ans[i]是 wordsContainer中与 wordsQuery[i] 有 最长公共后缀 字符串的下标。

示例 1：

输入：wordsContainer = [“abcd”,“bcd”,“xbcd”], wordsQuery = [“cd”,“bcd”,“xyz”]

输出：[1,1,1]

解释：

我们分别来看每一个 wordsQuery[i] ：

对于 wordsQuery[0] = “cd” ，wordsContainer 中有最长公共后缀 “cd” 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。 对于 wordsQuery[1] = “bcd” ，wordsContainer 中有最长公共后缀 “bcd” 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。 对于 wordsQuery[2] = “xyz” ，wordsContainer 中没有字符串跟它有公共后缀，所以最长公共后缀为 "" ，下标为 0 ，1 和 2 的字符串都得到这一公共后缀。这些字符串中， 答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。 示例 2：

输入：wordsContainer = [“abcdefgh”,“poiuygh”,“ghghgh”], wordsQuery = [“gh”,“acbfgh”,“acbfegh”]

输出：[2,0,2]

解释：

我们分别来看每一个 wordsQuery[i] ：

对于 wordsQuery[0] = “gh” ，wordsContainer 中有最长公共后缀 “gh” 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 2 的字符串，因为它的长度为 6 ，是最短的字符串。 对于 wordsQuery[1] = “acbfgh” ，只有下标为 0 的字符串有最长公共后缀 “fgh” 。所以尽管下标为 2 的字符串是最短的字符串，但答案是 0 。 对于 wordsQuery[2] = “acbfegh” ，wordsContainer 中有最长公共后缀 “gh” 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 2 的字符串，因为它的长度为 6 ，是最短的字符串。

提示：

1 <= wordsContainer.length, wordsQuery.length <= 104 1 <= wordsContainer[i].length <= 5 * 103 1 <= wordsQuery[i].length <= 5 * 103 wordsContainer[i] 只包含小写英文字母。 wordsQuery[i] 只包含小写英文字母。 wordsContainer[i].length 的和至多为 5 * 105 。 wordsQuery[i].length 的和至多为 5 * 105 。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class Node {
    Node[] son = new Node[26];
    int minL = Integer.MAX_VALUE;
    int i;
}

class Solution {
    public int[] stringIndices(String[] wordsContainer, String[] wordsQuery) {
        Node root = new Node();
        for (int idx = 0; idx < wordsContainer.length; ++idx) {
            char[] s = wordsContainer[idx].toCharArray();
            int l = s.length;
            Node cur = root;
            if (l < cur.minL) {
                cur.minL = l;
                cur.i = idx;
            }
            for (int i = s.length - 1; i >= 0; i--) {
                int b = s[i] - 'a';
                if (cur.son[b] == null) {
                    cur.son[b] = new Node();
                }
                cur = cur.son[b];
                if (l < cur.minL) {
                    cur.minL = l;
                    cur.i = idx;
                }
            }
        }

        int[] ans = new int[wordsQuery.length];
        for (int idx = 0; idx < wordsQuery.length; idx++) {
            char[] s = wordsQuery[idx].toCharArray();
            Node cur = root;
            for (int i = s.length - 1; i >= 0 && cur.son[s[i] - 'a'] != null; i--) {
                cur = cur.son[s[i] - 'a'];
            }
            ans[idx] = cur.i;
        }
        return ans;
    }
}

代码参考自灵茶山艾府