Leetcode brush problem notes 17/30 for one problem of the day and the next problem of the day
Writing in the front
This is the 17th day of my participation in Gwen Challenge
About to graduate, only to find himself in the interview algorithm hanging hammer. There is no way to zero based identity and classmates to join the force buckle brush problem army. My classmates are very good, they are usually just modest, verbally said that they will not, and I really will not… Nuggets encourage new people to blog every day, I also join in a lively, record every day brush the first two questions, these two questions I do. I plan to brush five questions every day. For the other questions, I can only memorize the routine by force and will not post them in my blog.
I am really just a vegetable chicken, what do not want to solve the problem from my reference, coding habits also need to improve, if you want to find brush problem master ask questions, I think it is better to go to the palace water sanye brush problem diary this big guy. I try not to see the solution of the problem before I make it, so as not to collide with the content of the big guy.
In addition, I also hope to have the leisure of the big guy to provide some higher clear problem-solving ideas to me, welcome to discuss ha!
All right, let’s start with the first two questions on day 17!
2021.6.17 One question of the day
65. Significant figures
This topic is absolutely, judge the normal number, recall the fear of being dominated by tan Haoqiang little red book… All kinds of weird multiple choice questions let you pick the legal number.
This problem gives a person a feeling of playing FPGA. Referring to FPGA, the most important is the state machine, this problem can of course be done with the state machine. Please don’t over-deify the state machine. I feel that all majors who have studied the principles of compilation like to deify the state machine anyway, but basically all the majors who have been tortured by the number of computers take the state machine as their friend. In fact, whether it is called state machine or automaton, it is a thing, KMP algorithm will use it, the basic idea of regular is also it, FPGA will use this thing to design their own small system workflow.
So, in fact, classification discussion, re, translation, these ideas behind the real use of the state machine… It’s just that these ideas are being used in tools that are encapsulated in the language. So how do we solve this problem ourselves using the most primitive and essential state machine ideas? I suggest that you read the selected answers to this question first. I think the answer is better than the official answer.
The state machine must have an initial state and a number of acceptable states. The number of acceptable states depends on the designer’s understanding and segmentation of the problem. After all, the state machine is for the convenience of people to deal with the problem, not to bring out the difficult things. This thing is a tool for standardizing the mental steps of case discussion and molecular disassembly. I think read in a number of Spaces is the initial state at the beginning, and then read the sign, and then read the Numbers, and then read the decimal point, and then read the Numbers, then read in scientific notation sign e or e, then read the sign, and then read the Numbers, at the end of the last may be read in a number of Spaces, so that the most complex digital reading in the process is over. And then you can start with the most complicated process and see that you can skip the steps, you can skip the notation, you can skip the decimal point, you can skip the scientific notation notation. Then, I will draw the state transition diagram (do not confuse the state machine with the dynamic programming, the state transition diagram is also for the purpose of thinking, not heavy, not omitted, convenient reading line). Here I borrow the state transition diagram of the selected answers:
I wonder if you could understand, figure from left to right, 0 to 5, the state is the most complicated case, other line description can leapfrog is the case, if you read in a string, not through to the final conditions, then the stop in the middle of the half of the way things are not normal, stop in the middle of the half of the way is not transferred to our acceptable state, The state of being taken for granted is unacceptable.
If this figure is not understand, then have a look at this picture of corresponding state to jump table, see the state jump table just like do psychological tests, the problem is you answered this option, please jump to so-and-so issues continue to test, finally falls in a series of test results of a certain, the state transition table should be best to accept the description of the state machine form.
| state | blank | +/- | 0-9 | . | e/E | other |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 6 | 2 | – 1 | – 1 |
| 1 | – 1 | – 1 | 6 | 2 | – 1 | – 1 |
| 2 | – 1 | – 1 | 3 | – 1 | – 1 | – 1 |
| 3 | 8 | – 1 | 3 | – 1 | 4 | – 1 |
| 4 | – 1 | 7 | 5 | – 1 | – 1 | – 1 |
| 5 | 8 | – 1 | 5 | – 1 | – 1 | – 1 |
| 6 | 8 | – 1 | 6 | 3 | 4 | – 1 |
| 7 | – 1 | – 1 | 5 | – 1 | – 1 | – 1 |
| 8 | 8 | – 1 | – 1 | – 1 | – 1 | – 1 |
Author: User8973 Link: leetcode-cn.com/problems/va… Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.
Bring the link to the original text, if you don’t understand what I’m talking about, just read the original text. I think the problem is completely clear at this point, and then it’s all about translating these things into code.
class Solution {
public:
bool isNumber(string s) {
if (s.empty()) {
return false;
}
int n = s.size(a);int state = 0;
vector<bool> finals({0.0.0.1.0.1.1.0.1});
vector<vector<int>> transfer({{0.1.6.2.- 1.- 1},
{- 1.- 1.6.2.- 1.- 1},
{- 1.- 1.3.- 1.- 1.- 1},
{ 8.- 1.3.- 1.4.- 1},
{- 1.7.5.- 1.- 1.- 1},
{ 8.- 1.5.- 1.- 1.- 1},
{ 8.- 1.6.3.4.- 1},
{- 1.- 1.5.- 1.- 1.- 1},
{ 8.- 1.- 1.- 1.- 1.- 1}});for (int i = 0; i < n; i++) {
state = transfer[state][_make(s[i])];
if(state < 0) return false;
}
return finals[state];
}
private:
int _make(const char& c) {
switch(c) {
case ' ': return 0;
case '+': return 1;
case The '-': return 1;
case '. ': return 3;
case 'e': return 4;
case 'E': return 4;
default: return_number(c); }}int _number(const char& c) {
if (c >= '0' && c <= '9') {return 2;
} else {
return 5; }}};Copy the code
One of the following questions per day
1480. Dynamic sum of one-dimensional arrays
Vector
runningSum(const vector
&nums); vector
runningSum(const vector
&nums);
summary
The state machine determines valid numbers, and the simple questions focus on code specifications
Refer to the link
There is no