Leetcode for each question of the day and the next question of the day brush notes 1/30
Writing in the front
This is the first day of my participation in the More text Challenge. For details, see more text Challenge
About to graduate, just find oneself by the algorithm problem in the interview hanging up hammer. No way can only be based on zero identity and classmates to join the force buckle brush problem army. My classmates are very good, they usually just modest, verbally said that they can’t, but I really can’t… As the Nuggets encourage their new players to blog every day, I joined in by recording the first two questions of the day, which I worked on carefully. I plan to brush five questions every day, and the other questions can only be forcibly memorized, not posted in the blog.
I really just a vegetable chicken, solution ideas what don’t reference from me here, coding habits also need to improve, if you want to find brush problem master consult questions I think to find the palace water three leaf brush problem diary this big guy is better. I try not to look at the problem before the problem to work out, so as not to crash with the content of the big guy.
In addition, I also hope that there are idle big guy to provide some more intelligent solution ideas to me, welcome to discuss ha!
All right, let’s get to the first two questions of the first day without further ado!
2021.6.1 One question per day
1744. Can you have your favorite candy on your favorite day?
The rule is to start eating on day 0. Well, that’s very programmer. By day n, I had eaten n + 1 days of sugar. Eat at least 1 candy per day and at most dailyCap, so the total amount of sugar eaten from the beginning to now can be expressed as a range, that is, [n + 1, (n + 1) * dailyCap]. Try not to use the I subscript here to avoid confusion with the I th request. In favoriteDay, the maximum * dailyCap exceeds the total number of candies in the previous favoriteType categories. In this way, you can eat your favorite candy on your favoriteDay. The sum to exceed (but not equal) is the sum[favoriteType -1]. At the beginning, I think this question is not wrong, the result is too simple, in case one day a candy to eat the most favorite day before the favorite candy to the last one, that favorite day is not crying? The minimum range of favoriteDay + 1 cannot exceed sum[favoriteType].
Here’s my C++ code:
class Solution {
public:
vector<bool> canEat(vector<int>& candiesCount, vector<vector<int>>& queries) {
int n = candiesCount.size(a);vector<long long> sum(n);
sum[0] = candiesCount[0];
for (int i = 1; i < n; ++i) {
sum[i] = sum[i - 1] + candiesCount[i];
}
vector<bool> ans;
for (const auto& q: queries) {
int favoriteType = q[0], favoriteDay = q[1], dailyCap = q[2];
long long x1 = favoriteDay + 1;
long long x2 = (long long)(favoriteDay + 1) * dailyCap;
long long y1;
if (favoriteType == 0) {
y1 = 1;
} else {
y1 = sum[favoriteType - 1] + 1;
}
long long y2 = sum[favoriteType];
if(! ((x1 > y2) || (x2 < y1))) { ans.push_back(true);
} else {
ans.push_back(false); }}returnans; }};Copy the code
Old fool… Finally.
By the way, I suggest you try auto after C++ 11, and have a feeling of playing with Python (do nothing lazy first).
It is not recommended to refer to my code, specification elegant fast (three accounted for two) code please refer to the official solution.
Let’s move on to question two…
2021.6.1 One question per day
Click random to see what good questions the system assigns me:
Minimum number of insertions of a balanced parenthesis string
The problem of matching parentheses, one left against two right, I think I’ve seen one left and one right before and it’s easier to do it with the stack. I’m going to do a straightforward stupid thing, which is to go left to right without using the stack. I’m currently left, so I see left plus =1, let’s go to the next one. Current is right, see left -=1, see what is next, is left, insert number +=1 (insert another right), see next (see left, please always pay attention to where is currently); If it’s right, go straight to the next two (the next one is right, but it’s paired with the first one, so don’t look at the next one, go straight to the next two, pay attention to where you are). And you do that until you iterate through the entire string, and you get a left and a number of insertions that you see. The number of inserts has to be positive, so let me just leave that on the side, you can see that the left side can be positive or negative or it can be 0, it’s better if it’s 0, and now it matches, so I just print out the number of inserts. If it’s positive, it’s missing the right, so you see the absolute value of the left times 2 plus the number of inserts is the final result. If it’s negative, it’s missing the left, and the absolute value of the left plus the number of inserts is what you get.
The C++ code is as follows:
class Solution {
public:
int minInsertions(string s) {
int insertions = 0;
int leftCount = 0;
int length = s.size(a);int index = 0;
while (index < length) {
char c = s[index];
if (c == '(') {
leftCount++;
index++;
} else {
leftCount--;
if (index < length - 1 && s[index + 1] = ='(') {
insertions++;
index++;
}
if (index < length - 1 && s[index + 1] = =') ') {
index += 2; }}}if (leftCount > 0) {
insertions += leftCount * 2;
return insertions;
} else if (leftCount < 0) {
insertions -= leftCount;
return insertions;
}
returninsertions; }};Copy the codeVery nice, it timed out…
The left is always a positive number, and there is no judgment outside the bottom loop. In the loop, first judge whether the left is a positive number, which is a positive number, and the left -=1, not a positive number. To add a left, insert number +=1. Then determine whether the following right is still right, yes, look at two (notice where it is currently), no, to add a right, insert number +=1, look at the next (notice where it is currently).
Then it was amazing to find that my code and the official solution seemed to be the same… I’m not going to paste it.
Then let’s use the stack to solve this problem, I should not flip the car… The C++ code looks like this
class Solution {
public:
int minInsertions(string s) {
int length_s = s.length(a); stack<char> stack_s;
int insertions = 0;
for (int i = 0; i < length_s; i++){
if (s[i] == '(') {
stack_s.push('(');
} else {
if(! (i < length_s -1 && s[i + 1] = =') ')) {
insertions++;
} else {
i++;
}
if (stack_s.empty()) {
insertions++;
} else {
stack_s.pop(a); }}}return insertions + stack_s.size(*)2; }};Copy the codePersonally, I think it’s better to use it than not, because C++ is not as good as it used to be. Then I found a little trick, the current is not the left of the two pairs of if-else here can actually switch the order, try to change it may improve performance (I changed the code in the performance decreased…)
summary
What did you learn today: matching prefixes with the C++11 auto keyword, parentheses
Refer to the link
Prefix sum (difference) algorithm
The c++ keyword auto
Bracket pairing problem (C++ stack)
C++ stack for parenthesis matching problems (detail version + title)