Title quoted from
https://leetcode-cn.com/
Graphic data structure and algorithm
Daily learning Day02 learning notes
20 numeric values represent strings
Title Description:
Please implement a function to judge whether the string represents a numeric value (including integer and decimal).
The values (in order) can be divided into the following parts:
1. Several spaces
2. A decimal or integer
3. (optional) an 'e' or 'e' followed by an integer
4. Several spaces
Decimals (in order) can be divided into the following parts:
1. (optional) one symbolic character ('+' or '-')
2. One of the following formats:
At least one digit followed by a dot '
At least one digit followed by a dot ', Followed by at least one digit
A dot ', Followed by at least one digit
Integers (in order) can be divided into the following parts:
1. (optional) one symbolic character ('+' or '-')
2. At least one digit
Some values are listed as follows:
["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]
Some non numerical values are listed as follows:
["12e", "1a3.14", "1.2.3", "±5", "12e+5.4"]
Problem solving ideas:
1. Use regular expressions directly to match strings
2. String matching is realized by using state machine and state transition.
----First, find out the transition state corresponding to various states according to the title description, and then judge each bit of the string in turn.
----The contact time is less and the machine is used more.
class Solution {
public:
enum stats{
STATE_STARTBLANK,
STATE_SIGN,
STATE_INT,
STATE_INTPOINT,
STATE_NOINTPOINT,
STATE_DBL,
STATE_E,
STATE_ESIGN,
STATE_EDBL,
STATE_ENDBLANK
};
enum type{
NUMBER,
E,
POINT,
SIGN,
BLANK,
OTHER
};
type istype(char ch){
if(ch >='0' && ch <= '9')
return NUMBER;
else if(ch == 'e' || ch == 'E')
return E;
else if(ch == '.')
return POINT;
else if(ch == '+' || ch == '-')
return SIGN;
else if(ch == ' ')
return BLANK;
else
return OTHER;
};
bool isNumber(string s) {
unordered_map<stats,unordered_map<type,stats>>dp{
{
STATE_STARTBLANK,{
{BLANK,STATE_STARTBLANK},{NUMBER,STATE_INT},
{POINT,STATE_NOINTPOINT},{SIGN,STATE_SIGN},
}
},
{
STATE_SIGN,{
{NUMBER,STATE_INT},{POINT,STATE_NOINTPOINT},
}
},
{
STATE_INT,{
{NUMBER,STATE_INT},{E,STATE_E},
{POINT,STATE_INTPOINT},{BLANK,STATE_ENDBLANK},
}
},
{
STATE_INTPOINT,{
{NUMBER,STATE_DBL},{E,STATE_E},
{BLANK,STATE_ENDBLANK},
}
},
{
STATE_NOINTPOINT,{
{NUMBER,STATE_DBL},
}
},
{
STATE_DBL,{
{NUMBER,STATE_DBL},{E,STATE_E},
{BLANK,STATE_ENDBLANK},
}
},
{
STATE_E,{
{NUMBER,STATE_EDBL},{SIGN,STATE_ESIGN},
}
},
{
STATE_ESIGN,{
{NUMBER,STATE_EDBL},
}
},
{
STATE_EDBL,{
{NUMBER,STATE_EDBL},{BLANK,STATE_ENDBLANK},
}
},
{
STATE_ENDBLANK,{
{BLANK,STATE_ENDBLANK},
}
}
};
int length = s.length();
stats ss = STATE_STARTBLANK;
for(int i = 0;i<length;++i){
type tp = istype(s[i]);
if(dp[ss].find(tp) == dp[ss].end())
return false;
else
ss = dp[ss][tp];
}
return ss == STATE_INT|| ss == STATE_INTPOINT || ss == STATE_DBL || ss == STATE_ENDBLANK || ss == STATE_EDBL;
}
};
Execution time: 76 ms, At all C++ Defeated 5 in submission.47%User Memory consumption: 15.2 MB, At all C++ Defeated 19 in submission.24%User
24 reverse linked list
Title Description:
Define a function, input the head node of a linked list, invert the linked list and output the head node of the inverted linked list.
Problem solving ideas:
1. Recursive inversion
2. Bidirectional pointer inversion
class Solution {
public:
ListNode* isReverse(ListNode* pre,ListNode* now){
if(now==nullptr)
return pre;
ListNode* result = isReverse(now,now->next);
now->next = pre;
return result;
}
ListNode* reverseList(ListNode* head) {
return isReverse(nullptr,head);
}
};
Execution time: 4 ms, At all C++ Defeated 95 in submission.65%User Memory consumption: 8.3 MB, At all C++ Defeated 5 in submission.02%User
30 stack containing min function
Title Description:
To define the data structure of the stack, please implement a min function that can get the smallest element of the stack in this type. In this stack, the time complexity of calling min, push and pop is O(1).
Problem solving ideas:
Traversal cannot be used because the required time complexity is O (1).
Using dual stacks, one stack normally saves the pop-up elements, and the other stack saves the minimum value. When popping into the stack, judge whether the pop-in element is smaller than the minimum stack top element. If so, pop into the smallest stack. Otherwise, pop the stack top element of the smallest stack again. When pop-up the stack top element at the same time, two stacks pop up a stack top element at the same time.
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
st.push(x);
if(st_min.empty()||x < st_min.top())
st_min.push(x);
else
st_min.push(st_min.top());
}
void pop() {
st.pop();
st_min.pop();
}
int top() {
return st.top();
}
int min() {
return st_min.top();
}
stack<int>st;
stack<int>st_min;
};
Execution time: 28 ms, At all C++ Defeated 39 in submission.70%User Memory consumption: 14.6 MB, At all C++ Beat 90 in submission.27%User
35 copy of complex linked list
Title Description:
Please implement the copyRandomList function to copy a complex linked list. In a complex linked list, each node has a next pointer to the next node and a random pointer to any node or null in the linked list.
Problem solving ideas:
1. Map traverses the map twice. The first traversal of the linked list maps each node, and the second traversal maps the relationship between the next and random nodes of each node.
2. Add a node and modify it.
//1. map implementation
class Solution {
public:
Node* copyRandomList(Node* head) {
if(head == nullptr)
return head;
unordered_map<Node*,Node*>dp;
Node* cur = head;
while(cur!=nullptr)
{
dp[cur] = new Node(cur->val);
cur = cur->next;
}
cur = head;
while(cur!=nullptr)
{
dp[cur]->next = dp[cur->next];
dp[cur]->random = dp[cur->random];
cur = cur->next;
}
return dp[head];
}
};
Execution time: 12 ms, At all C++ Defeated 60 in submission.76%User Memory consumption: 10.9 MB, At all C++ Defeated 83 in submission.52%User
It is troublesome to realize splicing. You need to pay attention to the direction of each pointer.
class Solution {
public:
Node* copyRandomList(Node* head) {
if(head == nullptr)
return head;
Node* cur = head;
while(cur!=nullptr)
{
Node* nd = new Node(cur->val);
nd->next = cur->next;
cur->next = nd;
cur = nd->next;
}
cur = head;
while(cur!=nullptr)
{
if(cur->random != nullptr)
cur->next->random = cur->random->next;
cur = cur->next->next;
}
cur = head->next;
Node* pre = head, *res = head->next;
while(cur->next != nullptr) {
pre->next = pre->next->next;
cur->next = cur->next->next;
pre = pre->next;
cur = cur->next;
}
pre->next = nullptr;
return res;
}
};
Execution time: 8 ms, At all C++ Defeated 89 in submission.52%User Memory consumption: 10.9 MB, At all C++ Defeated 95 in submission.95%User