LeetCode数据结构与算法学习Day02
题目引用自
https://leetcode-cn.com/
图解数据结构与算法
每日学习Day02学习笔记
20 数值表示字符串
题目描述：
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
数值（按顺序）可以分成以下几个部分：
1、若干空格
2、一个小数或者整数
3、（可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个整数
4、若干空格
小数（按顺序）可以分成以下几个部分：
1、（可选）一个符号字符（’+’ 或 ‘-’）
2、下述格式之一：
至少一位数字，后面跟着一个点 ‘.’
至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
一个点 ‘.’ ，后面跟着至少一位数字
整数（按顺序）可以分成以下几个部分：
1、（可选）一个符号字符（’+’ 或 ‘-’）
2、至少一位数字
部分数值列举如下：
["+100", “5e2”, “-123”, “3.1416”, “-1E-16”, “0123”]
部分非数值列举如下：
[“12e”, “1a3.14”, “1.2.3”, “±5”, “12e+5.4”]
解题思路：
1、直接使用正则表达式匹配字符串
2、利用状态机、状态转移来实现字符串匹配。
----先根据题目描述求出各种状态与状态对应的转移状态有什么，然后依次对字符串每一位进行判断。
----接触状态机较少，用的时间比较多。
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;
}
};
执行用时：
76 ms, 在所有 C++ 提交中击败了5.47%的用户
内存消耗：
15.2 MB, 在所有 C++ 提交中击败了19.24%的用户
24 反转链表
题目描述：
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
解题思路：
1、递归反转
2、双向指针反转
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);
}
};
执行用时：
4 ms, 在所有 C++ 提交中击败了95.65%的用户
内存消耗：
8.3 MB, 在所有 C++ 提交中击败了5.02%的用户
30 包含min函数的栈
题目描述：
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
解题思路：
由于要求时间复杂度为O（1），则无法使用遍历。
使用双栈，一个栈正常保存弹入元素，另一个栈保存最小值。在弹入栈的时候作判断，弹入元素是否小于最小栈顶元素，是的话弹入最小栈，否则将最小栈的栈顶元素再次弹入，同时弹出栈顶元素时，两个栈同时弹出一个栈顶元素。
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;
};
执行用时：
28 ms, 在所有 C++ 提交中击败了39.70%的用户
内存消耗：
14.6 MB, 在所有 C++ 提交中击败了90.27%的用户
35 复杂链表的复制
题目描述：
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
解题思路：
1、map两次遍历映射。第一次遍历链表映射各个节点，第二次遍历映射各个节点的next与random节点关系。
2、新增节点并修改。
//1、map实现
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];
}
};
执行用时：
12 ms, 在所有 C++ 提交中击败了60.76%的用户
内存消耗：
10.9 MB, 在所有 C++ 提交中击败了83.52%的用户
拼接实现的时候比较麻烦，需要注意各个指针的指向。
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;
}
};
执行用时：
8 ms, 在所有 C++ 提交中击败了89.52%的用户
内存消耗：
10.9 MB, 在所有 C++ 提交中击败了95.95%的用户