Hello everyone, Rigongyi pawn, I am Liang Tang.
Today is Monday, as usual, let’s watch yesterday morning’s LeetCode week. This article originated from the public account: Coder Liang, welcome to follow
The competition was sponsored by Horizon Corporation, a seemingly small company that offered few rewards and push-in opportunities. Only the top 5 get the internal push… It’s kind of funny to be honest…
This competition overall partial simple, suitable for novice practice.
Okay, no more nonsense, let’s look at the problem.
The minimum number of operands required for conversion time
Difficulty: 1 star
You are given two strings, current and correct, representing two 24-hour times.
The 24-hour time format is HH:MM, where HH is between 00 and 23 and MM is between 00 and 59. The earliest 24-hour time is 00:00, and the latest is 23:59.
In one step, you can add current by 1, 5, 15, or 60 minutes. You can perform this operation any number of times.
Returns the minimum operands required to convert current to correct.
solution
Current <= correct means that the target time must be larger than the current time, so there is no need to overflow, such as dial 10 to 3.
Since there is no such special case, it is easy to perform as few operations as possible by maximizing the payoff for each operation. Of these, it is clear that fluctuating hours are the most profitable, followed by 15 minutes, then 5 minutes, and finally one minute.
We can start with the maximum 60 minutes, when the time difference is less than 60 minutes, 15 minutes, and so on. So we need to convert the time into minutes first, then calculate the difference between the two times, and then do it with greedy thinking.
class Solution {
public:
int convertTime(string current, string correct) {
auto conv = [](string s) -> int {
return (s[0] - '0') * 10 + s[1] - '0';
};
int cur_h = conv(current.substr(0.2)), cur_m = conv(current.substr(3.2));
int tar_h = conv(correct.substr(0.2)), tar_m = conv(correct.substr(3.2));
cur_m += cur_h * 60;
tar_m += tar_h * 60;
int hour = (tar_m - cur_m) / 60;
cur_m += 60 * hour;
int qua = (tar_m - cur_m) / 15;
cur_m += 15 * qua;
int fiv = (tar_m - cur_m) / 5;
cur_m += 5 * fiv;
returnhour + qua + fiv + tar_m - cur_m; }};Copy the codeFind out who has lost zero or one match
Difficulty: 1 star
Matches [I] = [Winneri, loseri] indicates that Winneri defeated Loseri in a match.
Return a list of length 2
answer[0]Is that allThere is noList of players who have lost any matches.answer[1]It’s all that happens to loseaList of players for the match.
The values in both lists should be returned in ascending order.
Note:
- Consider only players who have played at least one match.
- Generated test cases ensure that no two matches have the same result.
solution
Simulation, we can just simulate the meaning of the problem.
Iterate over Matches, storing the number of wins, losses, and matches played by each player. When the number of wins equals the number of matches played, the player is a complete winner. When the number of losses equals 1, the player is a player who has lost only one game.
It’s a simple use of a map, with almost no technical content.
class Solution {
public:
vector<vector<int>> findWinners(vector<vector<int>>& matches) {
map<int.int> win, lose, att;
for (auto &vt : matches) {
win[vt[0]] + +; lose[vt[1]] + +; att[vt[0]] + +; att[vt[1]] + +; } vector<int> all_win, lose_one;
for (auto it = att.begin(a); it ! = att.end(a); it++) {int i = it->first, n = it->second;
if (win.count(i) && win[i] == n) {
all_win.push_back(i);
}
if (lose.count(i) && lose[i] == 1) {
lose_one.push_back(i);
}
}
vector<vector<int>> ret{all_win, lose_one};
returnret; }};Copy the codeHow much candy can each child get
Difficulty: 2.5 stars
Gives you an array of integer candies with indexes starting from 0 Each element in the array represents a bunch of candies with the size of Candies [I]. You can divide each pile into as many subpiles as you want, but you can’t join the two piles together.
I’ll give you another integer k. You need to divide the candy among k children so that each child gets the same amount of candy. Each child can take up to one pile of candy, and some candies may not be distributed.
Returns the maximum number of candies each child can take.
solution
If we look at the data range first, we can find that the data range is not small, especially the maximum size of K is 1E12, and the initial pile number of candy is also 1E5, basically excluding the method of solving by violence.
Many students get this question will feel very difficult, because they can not find a breakthrough, do not know where to start to find the answer.
And indeed, since the number of candy piles is a variable, and the number of candy in each pile is a variable, these values are uncertain, and it doesn’t seem like there’s a very good way for us to find out from this information.
So the key is to recognize that positive thinking is not feasible, and to start thinking in the opposite direction.
Positive thinking is to use the question information to find the answer, and reverse thinking is to assume an answer, and then use the question information to determine whether the hypothesis is correct. Once we switch our thinking, we find that all the mountains in front of us are gone.
Suppose the final answer is x, how do we know if it’s true? It’s very simple. We go through each pile of candy, breaking it up into each pile of x. The final result is nums[I] / x, which can be divided among so many children. We can determine if x is correct by just adding up all the results, comparing them to K, and seeing if all the kids get a bunch.
Assuming that x is true, and by definition, it’s true for all numbers less than x. If we think of it as a function f, then f of x is a binary function. They’re all 1’s up to a certain point, and then 0’s up to a certain point. All we have to do is find this critical point. How? Binary.
So as long as you can change the idea, this problem is not difficult, the code is very simple.
class Solution {
public:
int maximumCandies(vector<int>& cand, long long k) {
long long tot = 0;
int n = cand.size(a);for (int i = 0; i < n; i++) {
tot += cand[i];
}
long long avg = tot / k;
// Open interval
long long l = 0, r = avg+1;
while (l + 1 < r) {
long long m = (l + r) >> 1;
long long s = 0;
for (int i = 0; i < n; i++) {
s += cand[i] / m;
}
// Calculate the maximum number of heaps per heap m, if greater than or equal to K, the condition is met
if (s >= k) l = m;
else r = m;
}
returnl; }};Copy the codeEncrypt and decrypt string
Difficulty: 3 stars
You are given a string array keys, consisting of several different characters. There is also a string array values that contains strings of length 2. You are also given an array of strings called dictionaries containing all the original strings allowed after decryption. Design and implement a data structure that supports encryption and decryption of strings with subscripts starting from 0.
String encryption is performed as follows:
- For each character in the string
cFirst, from thekeysFind satisfaction inkeys[i] == cThe subscripti。 - In a string, use
values[i]Substitution charactersc。
Decryption of strings follows the following steps:
- Divides a string into substrings for every 2 adjacent characters, for each substring
sFind satisfactionvalues[i] == sA subscript of thetai. If there are multiple validi, from which to chooseanyA. This means that one string decryption can result in multiple decrypted strings. - In a string, use
keys[i]replaces。
Implementing the Encrypter class:
Encrypter(char[] keys, String[] values, String[] dictionary)用keys,values和dictionaryInitialize theEncrypterClass.String encrypt(String word1)Follow the above encryption procedure to complete the pairword1And returns the encrypted string.int decrypt(String word2)Statistics and returns can be made byword2Decrypt obtained and appear indictionaryNumber of strings in.
solution
Let’s implement a class that can encode and decode.
The problem can be divided into three parts, the first part is the constructor, the second part is the encoding, and the third part is the decoding. The coding is the simplest, we can map each character according to the meaning of the question. To do this, we need to store the mapping between keys and values.
What is more complicated is the operation of decoding, since the string can have multiple matching results when it is decoded. For example, “EI” in this example can match either A or C. After decoding, we also count the number of existing in the dictionary.
One pitfall here is that the general idea might be to decode the string, enumerate all the combinations of the decodes, and then determine if each result is in the dictionary. But if you look at it, it’s possible to decode it. Especially if there’s a lot of repetition in values. The number of choices increases exponentially, and the inevitable result is timeout.
Solving the timeout problem also requires us to think backwards, and the key point is that the number of possible decoding combinations we’re going through is probably a lot, but the dictionary we’re matching isn’t that large. So we can do the reverse and enumerate all the strings in the dictionary to determine whether each string is possible to decode. There are only 100 strings in the dictionary at most, so the matching space is greatly reduced.
The operation of reverse matching is also not difficult. When we decode, each bit can be mapped to multiple characters in the set, each bit corresponds to a set, and the whole corresponds to a set array. When matching the string in the dictionary, we only need to find the corresponding set according to the serial number and determine whether the current character exists in the set. As long as one digit is not present, it cannot constitute a match and can be passed.
See the code for more details:
class Encrypter {
public:
map<char, string> mapping;
// Reverse map, store the mapping between value and key
map<string, set<char>> refmap;
vector<string> dict;
Encrypter(vector<char>& keys, vector<string>& values, vector<string>& dictionary) {
dict = dictionary;
int n = keys.size(a);for (int i = 0; i < n; i++) {
mapping[keys[i]] = values[i];
if (refmap.count(values[i]) == 0) {
set<char> st;
refmap[values[i]] = st;
}
refmap[values[i]].insert(keys[i]); }}string encrypt(string word1) {
string ret = "";
for (auto c: word1) {
ret += mapping[c];
}
return ret;
}
int decrypt(string word2) {
int ret = 0;
// Store the set after decoding each bit
vector<set<char>> chars;
for (int i = 0; i < word2.length(a); i +=2) {
string sub = word2.substr(i, 2);
// Cannot decode, returns 0 directly
if (refmap.count(sub) == 0) return 0;
chars.push_back(refmap[sub]);
}
for (int i = 0; i < dict.size(a); i++) { string &s = dict[i];if (s.length() != chars.size()) continue;
bool flag = true;
for (int j = 0; j < s.length(a); j++) {char c = s[j];
// Determine if each bit of s can be found in set
if (chars[j].count(c) == 0) {
flag = false;
break;
}
}
ret += flag;
}
returnret; }};/** * Your Encrypter object will be instantiated and called as such: * Encrypter* obj = new Encrypter(keys, values, dictionary); * string param_1 = obj->encrypt(word1); * int param_2 = obj->decrypt(word2); * /
Copy the codeThe routines of the last two questions in this competition are the same, which are difficult to solve in front and require reverse thinking. At the core, the difficulty of the questions is not too great, which is very suitable for exercising your thinking ability.
Well, that’s all for the weekly contest. Thank you for reading.