美文网首页
Day4 ⭐表示数值的字符串+从尾到头打印链表+斐波那契数列

Day4 ⭐表示数值的字符串+从尾到头打印链表+斐波那契数列

作者: 吃掉夏天的怪物 | 来源:发表于2021-06-10 17:40 被阅读0次

    剑指 Offer 20. 表示数值的字符串

    好复杂不会不会,得理清逻辑

    {
    public:
        bool isNumber(string s)
        {
            if(s.empty())
                return false;
            
            while(s[index] == ' ')  //去掉字符串头部的' '
                ++index;
    
            bool numeric = scanInterger(s); //扫描小数点前面整数部分,可能为以'+'或'-'开头的整数
    
            if(s[index] == '.') //如果出现'.',扫描小数部分,小数部分为无符号整数
            {
                ++index;
                numeric = scanUnsignedInterger(s) || numeric;
                //1、小数点前面可以没有整数部分,如 .123
                //2、小数点后面可以没有数字,如 233.
                //3、小数点前后可以都有数字,如 233.123
            }
    
            if(s[index] == 'e' || s[index] == 'E') //如果出现e或E,扫描数字的指数部分,可能为以'+'或'-'开头的整数
            {
                ++index;
                numeric = numeric && scanInterger(s); 
                // e的前后必须有数字
                // 1、当e或E前面没有数字时,整个字符串不能表示数字,如 .e1、e1;
                // 2、当e或E后面没有整数时,整个字符串不能表示数字,如 12e、12e+5.4
            }
            while (s[index] == ' ' && index != s.size()) //去掉末尾的' '
                ++index;
    
            return numeric && index == s.size();
    
        }
    
    private:
        bool scanInterger(string &s)
        {
            //扫描有符号的整数部分,去掉'+'或'-'即为扫描无符号整数
            if(s[index] == '+' || s[index] == '-')
                ++index;
            return scanUnsignedInterger(s);
        }
    
        bool scanUnsignedInterger(string &s)
        {
            //扫描无符号整数部分
            int before = index;
            while(index != s.size() && s[index] >= '0' && s[index] <= '9')
                ++index;
            //如果存在若干0~9的数字,返回true
            return index > before;
        }
    
        int index = 0;
    };
    
    

    剑指 Offer 06. 从尾到头打印链表

    简单递归也可以用栈,数据翻转等,是一道简单题。

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<int> res;
        void p (ListNode* head){
            if(head == nullptr) return ;
            // if(head->next == nullptr) {res.push_back(head->val);return;}
            if(head!=nullptr){
                p(head->next);
                res.push_back(head->val);
            }
        }
        vector<int> reversePrint(ListNode* head) {
            if(head == nullptr) return {};
            p(head);
            return res;
            
    
        }
    };
    

    这样写好像会更简洁一点,但是时间从4ms变成了8ms

    class Solution {
    public:
        vector<int> reversePrint(ListNode* head) {
            if(head == nullptr) return {};
            vector<int> res = reversePrint(head->next);
            res.push_back(head->val);
            return res;
        }
    };
    

    剑指 Offer 10- I. 斐波那契数列(简单)

    很简单,注意溢出

    class Solution {
    public:
        int fib(int n) {
            int a = 0,b = 1;
            if(n==0) return 0;
            if(n == 1||n==2) return 1;
            for(int i = 2; i <= n; i++){
                int t = (a+b)%1000000007;
                a = b;
                b = t;
            }
            return b;
    
        }
    };
    

    相关文章

      网友评论

          本文标题:Day4 ⭐表示数值的字符串+从尾到头打印链表+斐波那契数列

          本文链接:https://www.haomeiwen.com/subject/mdfpeltx.html