# biweekly-contest-90

## A

### Statement

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

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

``````输入：words = ["adc","wzy","abc"]

- "adc" 的差值整数数组是 [3 - 0, 2 - 3] = [3, -1] 。
- "wzy" 的差值整数数组是 [25 - 22, 24 - 25]= [3, -1] 。
- "abc" 的差值整数数组是 [1 - 0, 2 - 1] = [1, 1] 。

``````

``````输入：words = ["aaa","bob","ccc","ddd"]

``````

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

You are given an array of equal-length strings `words`. Assume that the length of each string is `n`.

Each string `words[i]` can be converted into a difference integer array `difference[i]` of length `n - 1` where `difference[i][j] = words[i][j+1] - words[i][j]` where `0 <= j <= n - 2`. Note that the difference between two letters is the difference between their positions in the alphabet i.e. the position of `'a'` is `0`, `'b'` is `1`, and `'z'` is `25`.

• For example, for the string `"acb"`, the difference integer array is `[2 - 0, 1 - 2] = [2, -1]`.

All the strings in words have the same difference integer array, except one. You should find that string.

Return the string in `words` that has different difference integer array.

Example 1:

``````Input: words = ["adc","wzy","abc"]
Output: "abc"
Explanation:
- The difference integer array of "adc" is [3 - 0, 2 - 3] = [3, -1].
- The difference integer array of "wzy" is [25 - 22, 24 - 25]= [3, -1].
- The difference integer array of "abc" is [1 - 0, 2 - 1] = [1, 1].
The odd array out is [1, 1], so we return the corresponding string, "abc".
``````

Example 2:

``````Input: words = ["aaa","bob","ccc","ddd"]
Output: "bob"
Explanation: All the integer arrays are [0, 0] except for "bob", which corresponds to [13, -13].
``````

Constraints:

• `3 <= words.length <= 100`
• `n == words[i].length`
• `2 <= n <= 20`
• `words[i]` consists of lowercase English letters.

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T& a, const S& b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T& a, const S& b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
string oddString(vector<string>& words) {
int m = int(words[0].size());

const auto get_v = [&m](const string& s) {
auto v = vector<int>();
for (int i = 1; i < m; i++) {
v.push_back(s[i] - s[i - 1]);
}

return v;
};

auto mp = map<vector<int>, int>();
for (const auto& word : words) {
mp[get_v(word)]++;
}

for (const auto& word : words) {
auto v = get_v(word);
if (mp[v] == 1) {
return word;
}
}

return "";
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

``````输入：queries = ["word","note","ants","wood"], dictionary = ["wood","joke","moat"]

- 将 "word" 中的 'r' 换成 'o' ，得到 dictionary 中的单词 "wood" 。
- 将 "note" 中的 'n' 换成 'j' 且将 't' 换成 'k' ，得到 "joke" 。
- "ants" 需要超过 2 次编辑才能得到 dictionary 中的单词。
- "wood" 不需要修改（0 次编辑），就得到 dictionary 中相同的单词。

``````

``````输入：queries = ["yes"], dictionary = ["not"]

"yes" 需要超过 2 次编辑才能得到 "not" 。

``````

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

You are given two string arrays, `queries` and `dictionary`. All words in each array comprise of lowercase English letters and have the same length.

In one edit you can take a word from `queries`, and change any letter in it to any other letter. Find all words from `queries` that, after a maximum of two edits, equal some word from `dictionary`.

Return a list of all words from `queries`, that match with some word from `dictionary` after a maximum of two edits. Return the words in the same order they appear in `queries`.

Example 1:

``````Input: queries = ["word","note","ants","wood"], dictionary = ["wood","joke","moat"]
Output: ["word","note","wood"]
Explanation:
- Changing the 'r' in "word" to 'o' allows it to equal the dictionary word "wood".
- Changing the 'n' to 'j' and the 't' to 'k' in "note" changes it to "joke".
- It would take more than 2 edits for "ants" to equal a dictionary word.
- "wood" can remain unchanged (0 edits) and match the corresponding dictionary word.
Thus, we return ["word","note","wood"].
``````

Example 2:

``````Input: queries = ["yes"], dictionary = ["not"]
Output: []
Explanation:
Applying any two edits to "yes" cannot make it equal to "not". Thus, we return an empty array.
``````

Constraints:

• `1 <= queries.length, dictionary.length <= 100`
• `n == queries[i].length == dictionary[j].length`
• `1 <= n <= 100`
• All `queries[i]` and `dictionary[j]` are composed of lowercase English letters.

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T& a, const S& b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T& a, const S& b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
vector<string> twoEditWords(vector<string>& queries, vector<string>& dictionary) {
auto res = vector<string>();

for (const auto& q : queries) {
int len = int(q.size());
for (const auto& d : dictionary) {
int len_d = int(d.size());
if (len != len_d) {
continue;
}

int cnt = 0;

for (int i = 0; i < len; i++) {
cnt += (q[i] != d[i]);
}

if (cnt <= 2) {
res.push_back(q);
break;
}
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

``````输入：nums = [3,7,8,1,1,5], space = 2

``````

``````输入：nums = [1,3,5,2,4,6], space = 2

``````

``````输入：nums = [6,2,5], space = 100

``````

• `1 <= nums.length <= 105`
• `1 <= nums[i] <= 109`
• `1 <= space <= 109`

You are given a 0-indexed array `nums` consisting of positive integers, representing targets on a number line. You are also given an integer `space`.

You have a machine which can destroy targets. Seeding the machine with some `nums[i]` allows it to destroy all targets with values that can be represented as `nums[i] + c * space`, where `c` is any non-negative integer. You want to destroy the maximum number of targets in `nums`.

Return the minimum value of `nums[i]` you can seed the machine with to destroy the maximum number of targets.

Example 1:

``````Input: nums = [3,7,8,1,1,5], space = 2
Output: 1
Explanation: If we seed the machine with nums[3], then we destroy all targets equal to 1,3,5,7,9,…
In this case, we would destroy 5 total targets (all except for nums[2]).
It is impossible to destroy more than 5 targets, so we return nums[3].
``````

Example 2:

``````Input: nums = [1,3,5,2,4,6], space = 2
Output: 1
Explanation: Seeding the machine with nums[0], or nums[3] destroys 3 targets.
It is not possible to destroy more than 3 targets.
Since nums[0] is the minimal integer that can destroy 3 targets, we return 1.
``````

Example 3:

``````Input: nums = [6,2,5], space = 100
Output: 2
Explanation: Whatever initial seed we select, we can only destroy 1 target. The minimal seed is nums[1].
``````

Constraints:

• `1 <= nums.length <= 105`
• `1 <= nums[i] <= 109`
• `1 <= space <= 109`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
int destroyTargets(vector<int> &nums, int space) {
sort(all(nums));
reverse(all(nums));

auto mp = map<int, int>();

int mx = 0;
int res = -1;

for (const auto &a : nums) {
int b = a % space;
++mp[b];
if (mp[b] >= mx) {
mx = mp[b];
res = a;
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

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

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

``````输入：nums = [2,4,0,9,6]

``````

``````输入：nums = [3,3]

``````

• `1 <= nums.length <= 105`
• `0 <= nums[i] <= 109`

You are given a 0-indexed array of non-negative integers `nums`. For each integer in `nums`, you must find its respective second greater integer.

The second greater integer of `nums[i]` is `nums[j]` such that:

• `j > i`
• `nums[j] > nums[i]`
• There exists exactly one index `k` such that `nums[k] > nums[i]` and `i < k < j`.

If there is no such `nums[j]`, the second greater integer is considered to be `-1`.

• For example, in the array `[1, 2, 4, 3]`, the second greater integer of `1` is `4`, `2` is `3`, and that of `3` and `4` is `-1`.

Return an integer array `answer`, where `answer[i]` is the second greater integer of `nums[i]`.

Example 1:

``````Input: nums = [2,4,0,9,6]
Output: [9,6,6,-1,-1]
Explanation:
0th index: 4 is the first integer greater than 2, and 9 is the second integer greater than 2, to the right of 2.
1st index: 9 is the first, and 6 is the second integer greater than 4, to the right of 4.
2nd index: 9 is the first, and 6 is the second integer greater than 0, to the right of 0.
3rd index: There is no integer greater than 9 to its right, so the second greater integer is considered to be -1.
4th index: There is no integer greater than 6 to its right, so the second greater integer is considered to be -1.
Thus, we return [9,6,6,-1,-1].
``````

Example 2:

``````Input: nums = [3,3]
Output: [-1,-1]
Explanation:
We return [-1,-1] since neither integer has any integer greater than it.
``````

Constraints:

• `1 <= nums.length <= 105`
• `0 <= nums[i] <= 109`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
vector<int> secondGreaterElement(vector<int> &nums) {
int n = int(nums.size());

auto se = set<int>();
auto vec = vector<pair<int, int>>();
for (int i = 0; i < n; i++) {
vec.push_back(make_pair(nums[i], i));
}

sort(all(vec));
reverse(all(vec));

auto res = vector<int>(n, -1);

for (int i = 0, j = 0; i < n; i++) {
for (; j < i && vec[j].first > vec[i].first; j++) {
se.insert(vec[j].second);
}

const auto &p = vec[i];
auto pos = se.lower_bound(p.second);
if (pos != se.end()) {
++pos;
if (pos != se.end()) {
res[p.second] = nums[*pos];
}
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````