LeetCode数据结构与算法学习Day02

• 图解数据结构与算法
• • 20 数值表示字符串
  • • 题目描述：
    • 解题思路：
  • 24 反转链表
  • • 题目描述：
    • 解题思路：
  • 30 包含min函数的栈
  • • 题目描述：
    • 解题思路：
  • 35 复杂链表的复制
  • • 题目描述：
    • 解题思路：

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%的用户