LeetCode 90 双周赛

2451. 差值数组不同的字符串

给你一个字符串数组

words

，每一个字符串长度都相同，令所有字符串的长度都为

。

每个字符串

words[i]

可以被转化为一个长度为

n - 1

的差值整数数组

difference[i]

，其中对于

0 <= j <= n - 2

有

difference[i][j] = words[i][j+1] - words[i][j]

。注意两个字母的差值定义为它们在字母表中位置之差，也就是说

'a'

的位置是

，

'b'

的位置是

，

'z'

的位置是

。

比方说，字符串 "acb" 的差值整数数组是 [2 - 0, 1 - 2] = [2, -1] 。

words

中所有字符串除了一个字符串以外，其他字符串的差值整数数组都相同。你需要找到那个不同的字符串。

请你返回

words

中差值整数数组不同的字符串。

提示：

3 <= words.length <= 100
n == words[i].length
2 <= n <= 20
words[i] 只含有小写英文字母。

示例

输入：words = ["adc","wzy","abc"]
输出："abc"
解释：
- "adc" 的差值整数数组是 [3 - 0, 2 - 3] = [3, -1] 。
- "wzy" 的差值整数数组是 [25 - 22, 24 - 25]= [3, -1] 。
- "abc" 的差值整数数组是 [1 - 0, 2 - 1] = [1, 1] 。
不同的数组是 [1, 1]，所以返回对应的字符串，"abc"。

思路

模拟，计算出所有字符串的差值数组，然后找出其中不同的一个即可。

// C++
class Solution {
public:
    string oddString(vector<string>& words) {
        // 计算所有字符串的差值数组
        vector<vector<int>> d;
        for (auto& s : words) {
            vector<int> v;
            for (int i = 1; i < s.size(); i++) v.push_back(s[i] - s[i - 1]);
            d.push_back(v);
        }
        
        // 比较每个差值数组的每个位置, 找到某一个不同的位置
        for (int i = 1; i < d.size(); i++) {
            for (int j = 0; j < d[i].size(); j++) {
                if (d[i][j] != d[i - 1][j]) {
                    if (i > 1) return words[i];
                    if (d[i + 1][j] == d[i][j]) return words[i - 1];
                    return words[i];
                }
            }
        }
        return "";
    }
};

其实可以简化为一次遍历

// C++
class Solution {
public:
    string oddString(vector<string>& words) {
        int n = words.size(), bits = words[0].size();
        int diff = 0; // 只需要存一个差值即可
        // 依次看每一位
        for (int i = 1; i < bits; i++) {
            for (int j = 0; j < n; j++) {
                int t = words[j][i] - words[j][i - 1];
                if (j > 0 && t != diff) {
                    // 第一次出现, 当前这个单词, 与上一个单词, 在同一位置上的差值不一样
                    // 若第一次出现时j已经>=2, 那么至少0和1都是一样的, 那么不一样的一定是j本身
                    if (j >= 2) return words[j];
                    // 否则是j=1, 要看一下0和1究竟是谁
                    if (words[j + 1][i] - words[j + 1][i - 1] == t) return words[j - 1];
                    return words[j];
                }
                diff = t;
            }
        }
        return "";
    }
};

还可以求出某个字符串的

diff

数组，然后将

diff

作为哈希表的

key

，进行统计计数。最后求得计数为1的那个

diff

即可。

// C++
class Solution {
public:
    string diff(string& w) {
        string s;
        for (int i = 1; i < w.size(); i++) s += w[i] - w[i - 1];
        return s;
    }
    string oddString(vector<string>& words) {
        unordered_map<string, int> freq;
        for (auto& s : words) freq[diff(s)]++;
        for (auto& s : words) {
            if (freq[diff(s)] == 1) return s;
        }
        return "";
    }
};

2452. 距离字典两次编辑以内的单词

给你两个字符串数组

queries

和

dictionary

。数组中所有单词都只包含小写英文字母，且长度都相同。

一次编辑中，你可以从

queries

中选择一个单词，将任意一个字母修改成任何其他字母。从

queries

中找到所有满足以下条件的字符串：不超过两次编辑内，字符串与

dictionary

中某个字符串相同。

请你返回

queries

中的单词列表，这些单词距离

dictionary

中的单词编辑次数不超过两次。单词返回的顺序需要与

queries

中原本顺序相同。

提示：

1 <= queries.length, dictionary.length <= 100
n == queries[i].length == dictionary[j].length
1 <= n <= 100
所有 queries[i] 和 dictionary[j] 都只包含小写英文字母。

示例

输入：queries = ["word","note","ants","wood"], dictionary = ["wood","joke","moat"]
输出：["word","note","wood"]
解释：
- 将 "word" 中的 'r' 换成 'o' ，得到 dictionary 中的单词 "wood" 。
- 将 "note" 中的 'n' 换成 'j' 且将 't' 换成 'k' ，得到 "joke" 。
- "ants" 需要超过 2 次编辑才能得到 dictionary 中的单词。
- "wood" 不需要修改（0 次编辑），就得到 dictionary 中相同的单词。
所以我们返回 ["word","note","wood"] 。

思路

看了一下数据范围，这道题可以直接用暴力，遍历

queries

中的全部单词，依次与

dictionary

中的全部单词做比对，时间复杂度在

10^6

级别。

// C++
class Solution {
public:
    vector<string> twoEditWords(vector<string>& queries, vector<string>& dictionary) {
        vector<string> ans;
        for (auto& s : queries) {
            for (auto& d : dictionary) {
                int cnt = 0; //不同的字母数
                for (int i = 0; i < s.size(); i++) {
                    if (s[i] != d[i]) cnt++;
                }
                if (cnt <= 2) {
                    ans.push_back(s);
                    break;
                }
            }
        }
        return ans;
    }
};

2453. 摧毁一系列目标

给你一个下标从 0 开始的数组

nums

，它包含若干正整数，表示数轴上你需要摧毁的目标所在的位置。同时给你一个整数

space

。

你有一台机器可以摧毁目标。给机器输入

nums[i]

，这台机器会摧毁所有位置在

nums[i] + c * space

的目标，其中

是任意非负整数。你想摧毁

nums

中尽可能多的目标。

请你返回在摧毁数目最多的前提下，

nums[i]

的最小值。

提示：

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= space <= 10^9

示例

输入：nums = [3,7,8,1,1,5], space = 2
输出：1
解释：如果我们输入 nums[3] ，我们可以摧毁位于 1,3,5,7,9,... 这些位置的目标。
这种情况下， 我们总共可以摧毁 5 个目标（除了 nums[2]）。
没有办法摧毁多于 5 个目标，所以我们返回 nums[3] 。

思路

这道题需要注意解读题意。直观的来说，选择某个元素

nums[i]

之后，能够删除所有与

nums[i]

的距离为

space

倍数的位置。

比如选择

nums[i] = 1

，

space = 2

，则能删除这些位置：

1，3，5，7，9，...

我们需要将题目中的条件

nums[i] + c * space

，进行一下变换。设

nums[i] + c * space = x

，则选定

nums[i]

后，能够删除的所有位置就是

，其中

是任意非负整数。观察这个式子，其实我们可以对式子的两边做一下模运算。分别模

space

。能够得到

nums[i] % space = x % space

，这其实也就是说，

nums[i]

和

其实是关于

space

同余的。

选定一个数

nums[i]

后，能够删除的所有数的位置，其除以

space

后的余数，是等于

nums[i]

除以

space

后的余数的。

那么我们可以对

nums

中全部的数都做一下

mod space

的计算，并对余数进行计数。摧毁数目最多，那么就是出现次数最多的那个余数。

求得余数

后，我们再遍历一次

nums

，找到

mod space = r

的最小的

nums[i]

即可。一共需要2次遍历，时间复杂度为

第一版代码：

// C++
class Solution {
public:
    int destroyTargets(vector<int>& nums, int space) {
        unordered_map<int, int> freq;  // 余数的出现次数
        int r = 0, maxFreq = 0;
        for (auto& i : nums) {
            if (++freq[i % space] > maxFreq) {
                maxFreq = freq[i % space];
                r = i % space;
            }
        }
        // 求得出现次数最大的余数后, 直接找出对应最小的nums[i]
        int ans = 1e9;
        for (auto& i : nums) {
            if (i % space == r && i < ans) ans = i;
        }
        return ans;
    }
};

提交后会发现WA，因为有些特殊情况没有考虑到，比如：

当全部余数出现的频率都是1时，则需要直接返回 nums 的最小值
可能有多个余数具有相同的最大出现次数，我们需要取 nums[i] 更小的那个余数（包含了上面的情况）

// C++
class Solution {
public:
    int destroyTargets(vector<int>& nums, int space) {
        unordered_map<int, int> freq; // 某个余数出现的次数
        unordered_map<int, int> min_v; // 某个余数对应的最小的nums[i]
        int r = 0, maxFreq = 0;
        for (auto& i : nums) {
            int x = i % space;
            // 不存在时
            if (min_v.find(x) == min_v.end()) min_v[x] = i;
            else min_v[x] = min(min_v[x], i);

            freq[x]++;
            if (freq[x] > maxFreq) {
                maxFreq = freq[x];
                r = x;
            } else if (freq[x] == maxFreq && min_v[x] < min_v[r]) {
                r = x;
            }
        }
        return min_v[r];
    }
};

后记：听y总讲解后，发现题目中要求

是非负数，这也就意味着，如果

space = 2

，则

nums[i] = 1

，能删除

1, 3, 5, ...

；

若

nums[3]

，则能删除

3, 5, 7, ...

，只能删除往后的。而

和

模

的结果都是1，我们实际统计同余的次数，其实都是针对最小的

nums[i]

而言有效的。

2454. 下一个更大元素 IV

给你一个下标从 0 开始的非负整数数组

nums

。对于

nums

中每一个整数，你必须找到对应元素的第二大整数。

如果

nums[j]

满足以下条件，那么我们称它为

nums[i]

的第二大整数：

j > i
nums[j] > nums[i]
恰好存在一个 k 满足 i < k < j 且 nums[k] > nums[i] 。

如果不存在

nums[j]

，那么第二大整数为

-1

。

比方说，数组 [1, 2, 4, 3] 中， 1 的第二大整数是 4 ， 2 的第二大整数是 3 ， 3 和 4 的第二大整数是 -1 。

请你返回一个整数数组

answer

，其中

answer[i]

是

nums[i]

的第二大整数。

提示：

1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9

示例

输入：nums = [2,4,0,9,6]
输出：[9,6,6,-1,-1]
解释：
下标为 0 处：2 的右边，4 是大于 2 的第一个整数，9 是第二个大于 2 的整数。
下标为 1 处：4 的右边，9 是大于 4 的第一个整数，6 是第二个大于 4 的整数。
下标为 2 处：0 的右边，9 是大于 0 的第一个整数，6 是第二个大于 0 的整数。
下标为 3 处：右边不存在大于 9 的整数，所以第二大整数为 -1 。
下标为 4 处：右边不存在大于 6 的整数，所以第二大整数为 -1 。
所以我们返回 [9,6,6,-1,-1] 。

思路

审完题后，发现这道题求解的是：某个数右侧第二个比其大的数。而使用单调栈能求解出某个数右侧第一个比其大的数。那么我们用两次单调栈行不行呢？直接用两次单调栈貌似不行，当出现形如

[2 6 4]

这样的，6是第一个比2大的，4是第二个比2大的，但是4是大于6的。

换一种思路，我们使用一次单调栈，能够求出第一个比其大的数的位置（假设为

），那么我们第二次使用单调栈时，能不能加入一个条件呢？

求解位置大于 i 的，且第一个比其大的数

好像想不太通。下面直接看题解。

单调栈+小根堆

从左往右进行遍历，使用单调栈求出右侧存在第一个比起大的数，然后将其放到小根堆中，继续往右遍历的过程中，如果出现了某个数大于小根堆的堆顶元素，则说明该数是堆顶元素的第二大的数。

通俗的说，我们使用单调栈，从左往右遍历时，对某个数

，当第一次遇到其右侧有比其大的数时，将

塞到小根堆中。小根堆中的数，都是当前已经找到其右侧第一个比其大的数，那么继续往右遍历时，当遍历到的数大于小根堆的堆顶，则找到第二大。

// C++
typedef pair<int, int> PII;
class Solution {
public:
    vector<int> secondGreaterElement(vector<int>& nums) {
        int n = nums.size();
        stack<int> stk;
        vector<int> ans(n, -1);
        priority_queue<PII, vector<PII>, greater<PII>> heap; // 小根堆
        for (int i = 0; i < n; i++) {
            // printf("i = %d\n", i);
            while (!heap.empty() && nums[i] > heap.top().first) {
                // 堆顶对应的元素, 找到其右侧第二大的
                ans[heap.top().second] = nums[i];
                heap.pop();
            }

            while (!stk.empty() && nums[stk.top()] < nums[i]) {
                // 对于nums[stk.top()], 其右侧存在第一个比起大的数
                // 将其插入到小根堆
                heap.push({nums[stk.top()], stk.top()});
                stk.pop();
            }
            stk.push(i);
        }
        return ans;
    }
};

再上一下y总的解法，挺牛的。

排序+维护下标

由于是求某个数右侧第二大的数（涉及到数的大小，已经下标）。那么我们把所有数，按照从大到小的顺序，依次枚举，而要求右侧，所以我们需要维护下标。

假设有一根线段，线段上出现的点，表示当前已经纳入考虑的数的下标。

那么，我们从大到小，依次把数对应的下标放到这跟线段上。那么当枚举到某个数

上时，此时线段上放的都是大于该数的数的下标。我们只需要查找第二个大于数

下标的位置即可。由于可能存在相等的数，我们一次性处理所有值相同的数。否则，如果每次只处理一个数，当下一次再处理相同的数时，就不能满足线段上的数都是大于当前数这一语义了。

注：这里再次运用了，使用下标来对数据进行排序的这一技巧！！！

时间复杂度

// C++
class Solution {
public:
    vector<int> secondGreaterElement(vector<int>& nums) {
        int n = nums.size();
        // 把下标存起来
        vector<int> p(n);
        for (int i = 0; i < n; i++) p[i] = i;
        // 从大到小排序, 只排下标, 不改变原数组
        sort(p.begin(), p.end(), [&](int a, int b){
            return nums[a] > nums[b];
        });
        // C++中的set是自带排序的
        
        vector<int> ans(n, -1);

        set<int> s;
        s.insert(n);
        s.insert(n + 1);// 保证一定存在大于某个数的第二个位置
        for (int i = 0; i < n; i++) {
            // 找到一段连续相等的数, 一起处理
            int j = i + 1;
            while (j < n && nums[p[j]] == nums[p[i]]) j++;
            // 已经插入到set中的下标, 对应的数, 都是比当前数大的
            // 因为set中存的是下标, 直接从set中找到第一个比当前下标大的, 然后将迭代器+1, 就是第二大数的下标
            for (int k = i; k < j; k++) {
                auto it = s.upper_bound(p[k]);
                ++it;
                if (*it < n) ans[p[k]] = nums[*it]; // 如果*it >= n,则说明不存在
            }
            // 将本次处理的数的下标全部插入到set中
            for (int k = i; k < j; k++) {
                s.insert(p[k]);
            }
            i = j - 1; // 下一个要处理的位置, 其实是j, 但是i会自动+1, 所以更新i=j-1
        }
        return ans;
    }
};

双单调栈

其实和

单调栈+小根堆

的思路差不多，开两个栈

s1

，

s2

，其中

s1

中存的是当前还没有找到其右侧第一个比它大的那些数。而

s2

中存的是当前已经找到了其右侧第一个比它大的那些数。我们每次只要判断当前的数

nums[i]

是否比

s2

中的数大，即可。所以

s2

的栈顶必须是最小的。所以

s2

中也要保持元素的递减（栈顶最小）。故需要一个辅助栈。

// C++
class Solution {
public:
    vector<int> secondGreaterElement(vector<int>& nums) {
        int n = nums.size();
        stack<int> s1, s2;
        vector<int> ans(n, -1);
        for (int i = 0; i < n; i++) {
            while (s2.size() && nums[s2.top()] < nums[i]) {
                ans[s2.top()] = nums[i];
                s2.pop();
            }
            stack<int> tmp;
            while (s1.size() && nums[s1.top()] < nums[i]) {
                // 找到了第一个大的数
                tmp.push(s1.top());
                s1.pop();
            }
            // s1保持递减
            s1.push(i);
            while (tmp.size()) {
                s2.push(tmp.top());
                tmp.pop();
            }
        }
        return ans;
    }
};

总结

本场比赛很拉跨。只做出两题。

最近准备换租，当天晚上去楼上新的房子里打扫了卫生，有点累，做题的时候有点心不在焉，边做边和朋友聊天。哈哈哈，结果第一题花了45分钟才做出来。第三题也是在临近12点比赛结束时才发现规律，等到提交通过时已经是12点4分了。

T1可以模拟，也可以用哈希表；

T2暴力；

LeetCode 90 双周赛

2451. 差值数组不同的字符串

2452. 距离字典两次编辑以内的单词

2453. 摧毁一系列目标

2454. 下一个更大元素 IV

总结

继续阅读

开源低带宽语音编解码器

数组和类数组

241 Different Ways to Add Parentheses（C代码版）

【趋高机器视觉】机器视觉技术原理解析及解决方案

LeetCode-110-平衡二叉树-C语言

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制规程及特点4． CSMA/CD协议5． CSMA/CD的优点6．结束语

极大似然法(ML)与最大期望法(EM)

C++ 第十五周报告1--《冒泡法排序》

笔试面试题目：滑动窗口(二)

27. Remove Element(列表)题目代码

数据结构与算法（27）——排序（二）

Dijkstra--简易版（最短路径）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

LeetCode OJ Binary Tree Right Side View

leetcode809

hdu7108哈希