# LeetCode data structure and algorithm learning Day02

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
```

### 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;

}
}
};
```
```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:
unordered_map<Node*,Node*>dp;
while(cur!=nullptr)
{
dp[cur] = new Node(cur->val);
cur = cur->next;
}
while(cur!=nullptr)
{
dp[cur]->next = dp[cur->next];
dp[cur]->random = dp[cur->random];
cur = cur->next;
}
}
};
```
```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:
while(cur!=nullptr)
{
Node* nd = new Node(cur->val);
nd->next = cur->next;
cur->next = nd;
cur = nd->next;
}
while(cur!=nullptr)
{
if(cur->random != nullptr)
cur->next->random = cur->random->next;
cur = cur->next->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
```

Keywords: C++ Algorithm data structure leetcode

Added by WebMonkey on Fri, 18 Feb 2022 10:11:50 +0200