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

剑指 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;

    }
};