LeetCode - 剑指Offer - Part2

LeetCode 剑指Offer

Word count: 4.6k Reading time: 23 min

 2020-09-03  calculating  Share

但使龙城飞将在，不教胡马渡阴山。

剑指 Offer 11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

示例 1：

输入：[3,4,5,1,2]
输出：1
示例 2：

输入：[2,2,2,0,1]
输出：0
注意：本题与主站 154 题相同：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/

通过次数93,573 提交次数188,731

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof

class Solution {
public:
    int minArray(vector<int>& numbers) {
        //  1.遍历与第一个数比较
        //  67.16%  84.90%
        //  问题：如果是这种情况(1,1,2,2,1,1,1)则不对
        //  若改为 i<=num 的反例：（2,2,3,4,5,1,1）
        int len=numbers.size();
        if(!len) { return -1; }
        int num=numbers[0];
        for(int i: numbers) {
            if(i<num) {
                return i;
            }
            //  应该补充这一句：
            //  num=i;
        }
        return numbers[0];
    }
};

class Solution {
public:
    int minArray(vector<int>& numbers) {
        //  2.二分法
        //  67.16%  47.04%
        int len=numbers.size();
        if(!len) { return -1; }
        if(len==1) { return numbers[0]; }
        int l=0, r=len-1, mid;
        while(numbers[l]>=numbers[r]) {
            if(r-l==1) {
                //  只剩两个数，在循环内说明左大右小
                return numbers[r];
            }
            mid=l+(r-l)/2;
            if(numbers[mid]>numbers[l]) {
                l=mid;
            } else if(numbers[mid]<numbers[l]) {
                r=mid;
            } else if(numbers[mid]>numbers[r]) {
                //  numbers[mid] == numbers[l]
                l=mid;
            } else {
                //  numbers[mid] == numbers[r] == numbers[l]
                //  直接顺序查找
                int num=numbers[l];
                for(int i=l; i<=r; i++) {
                    if(numbers[i]<num) {
                        return numbers[i];
                    }
                    num=numbers[i];
                }
                return numbers[l];
            }
        }
        return numbers[l];
    }
};

剑指 Offer 12. 矩阵中的路径*

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。

[[“a”,”b”,”c”,”e”],
[“s”,”f”,”c”,”s”],
[“a”,”d”,”e”,”e”]]

但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

示例 1：

输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED”
输出：true

示例 2：

输入：board = [[“a”,”b”],[“c”,”d”]], word = “abcd”
输出：false

提示：

1 <= board.length <= 200
1 <= board[i].length <= 200

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof

class Solution {
public:
    //  dfs
    //  96.14%  88.34%
    bool exist(vector<vector<char>>& board, string word) {
        if(word.empty() || board.empty()) { return false; }
        int len1=board.size(), len2=board[0].size();
        for(int i=0;i<len1;i++) {
            for(int j=0;j<len2;j++) {
                if(dfs(board, word, i, j, 1)) {
                    return true;
                }
            }
        }
        return false;
    }

    //  顺便把string改为引用可以大幅优化程序
    bool dfs(vector<vector<char>>& board, string& word, int i, int j, int w) {
        //  越界检查
        if(i<0 || i>=board.size() || j<0 || j>=board[0].size()) { return false; }
        //  是否成功匹配
        if(board[i][j]!=word[w-1]) { return false; }
        //  是否全部匹配，没必要继续深挖，w表示当前要匹配的位置/深度
        if(w==word.size()) { return true; }
        //  标记，防止重复访问某个值
        char temp=word[w-1];
        board[i][j] = '\0';
        //  深挖
        if(dfs(board, word, i-1, j, w+1)
        || dfs(board, word, i, j-1, w+1)
        || dfs(board, word, i+1, j, w+1)
        || dfs(board, word, i, j+1, w+1)) {
            return true;
        }
        board[i][j] = temp;
        return false;
    }
};

剑指 Offer 13. 机器人的运动范围*

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例 1：

输入：m = 2, n = 3, k = 1
输出：3
示例 2：

输入：m = 3, n = 1, k = 0
输出：1
提示：

1 <= n,m <= 100
0 <= k <= 20

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof

class Solution {
public:
    int movingCount(int m, int n, int k) {
        //  1.bfs
        //  73.17%  70.38%
        int res=1;
        vector<vector<bool>> flag(m, vector<bool>(n, false));
        queue<pair<int,int>> que;
        que.push(make_pair(0, 0));
        //  Tips：我们在搜索的过程中搜索方向可以缩减为向右和向下，不必向上和向左搜索。
        int d[4] = {0,1,1,0};
        flag[0][0]=true;
        while(!que.empty()) {
            int nx, ny;
            int x=que.front().first;
            int y=que.front().second;
            que.pop();
            for(int i=0; i<2; i++) {
                nx=x+d[i];
                ny=y+d[i+2];
                if(nx<m && ny<n && !flag[nx][ny] && getSum(nx,ny)<=k) {
                    que.push(make_pair(nx,ny));
                    flag[nx][ny]=true;
                    res++;
                }
            }
        }
        return res;
    }
    int getSum(int i, int j) {
        return (i%10+(i/10)%10) + (j%10+(j/10)%10);
    }
};

class Solution {
public:
    int movingCount(int m, int n, int k) {
        //  2.dfs
        //  用stack代替queue，完成bfs到dfs的转换
        //  29.28%  76.87%
        int res=1;
        vector<vector<bool>> flag(m, vector<bool>(n, false));
        stack<pair<int,int>> sta;
        sta.push(make_pair(0, 0));
        int d[4] = {0,1,1,0};
        flag[0][0]=true;
        while(!sta.empty()) {
            int nx, ny;
            int x=sta.top().first;
            int y=sta.top().second;
            sta.pop();
            for(int i=0; i<2; i++) {
                nx=x+d[i];
                ny=y+d[i+2];
                if(nx<m && ny<n && !flag[nx][ny] && getSum(nx,ny)<=k) {
                    sta.push(make_pair(nx,ny));
                    flag[nx][ny]=true;
                    res++;
                }
            }
        }
        return res;
    }
    int getSum(int i, int j) {
        return (i%10+(i/10)%10) + (j%10+(j/10)%10);
    }
};

class Solution {
public:
    int movingCount(int m, int n, int k) {
        //  3.递推
        //  计算全部是否可到达，一个点是否可到达看上左即可
        //  73.17%  88.08%
        int res=0;
        vector<vector<bool>> flag(m, vector<bool>(n, false));
        flag[0][0]=true;
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(getSum(i,j)>k) {}
                else if(i==0 && j==0) {}
                else if(i==0) { flag[i][j]=flag[i][j-1]; }
                else if(j==0) { flag[i][j]=flag[i-1][j]; }
                else { flag[i][j]=flag[i-1][j] | flag[i][j-1]; }
            }
        }
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(flag[i][j]) { res++; }
            }
        }
        return res;
    }
    int getSum(int i, int j) {
        return (i%10+(i/10)%10) + (j%10+(j/10)%10);
    }
};

剑指 Offer 14. 剪绳子*

动态规划

贪婪算法

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

示例 1：

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：

2 <= n <= 58

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jian-sheng-zi-lcof

class Solution {
public:
    int cuttingRope(int n) {
        //  dp
        //  100.00% 70.81%
        if(n<4) return n-1;
        int dp[n+1];
        for(int i=0;i<4;i++) dp[i]=i;
        for(int i=4;i<=n;i++) {
            int max=0;
            for(int j=1;j<=i/2;j++) {
                int temp=dp[j]*dp[i-j];
                max = temp>max?temp:max;
            }
            dp[i]=max;
        }
        return dp[n];
    }
};

-> 数据量变大，不能用动态规划

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m - 1] 。请问 k[0]k[1]…*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示：

2 <= n <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof

//  贪婪算法
//  n>=5时，多剪3能保证结果最大
//  n%3=0,1,2讨论
class Solution {
public:
    int cuttingRope(int n) {
        //  100.00% 36.91%
        if(n<4) return n-1;
        if(n==4) return n;
        long long ans=1;
        while(n>4) {
            n-=3;
            ans*=3;
            ans%=1000000007;
        }
        return ans*n%1000000007; 
    }
};

剑指 Offer 15. 二进制中1的个数

请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

示例 1：

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 ‘1’。
示例 2：

输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 ‘1’。
示例 3：

输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 ‘1’。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof

class Solution {
public:
    int hammingWeight(uint32_t n) {
        //  1.位运算1
        //  100.00% 48.36%
        // int ans=0;
        // while(n) {
        //     if(n&1) { ans++; }
        //     n >>= 1;
        // }
        // return ans;

        //  1.位运算2
        //  100.00% 82.07%
        int ans=0;
        while(n) {
            n = n & (n-1);
            ans++;
        }
        return ans;
    }
};

剑指 Offer 16. 数值的整数次方*

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

示例 1:

输入: 2.00000, 10
输出: 1024.00000
示例 2:

输入: 2.10000, 3
输出: 9.26100
示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1] 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof

class Solution {
public:
    double myPow(double x, int n) {
        //  1.二分
        //  100.00% 36.10%
        if(n==0) {
            return 1;
        } else if(n>0) {
            if(n==1) { return x; }
            double i = myPow(x,n/2);
            if(n%2) { return x*i*i; }
            else { return i*i; }
        } else {
            if(n==-1) { return 1.0/x; }
            double i = myPow(x,n/2);
            if(n%2) { return (1.0/x)*i*i; }
            else { return i*i; }
        }
        return 1;
    }
};

//	2.快速幂
//	x^n 分解几个 x^i 的乘积
//	表示 n 的二进制形式，比如 9 = 1001 = 1*2^3 + 0*2^2 + 0*2^1 + 1*2^0
//	每次乘的值都是前一个值的2倍
//	负数幂和正数幂相同，因为除以一个数就相当于乘这个数的倒数。
class Solution {
public:
    double myPow(double x, int n) {
        if(x == 1 || n == 0) return 1;
        double ans = 1;
        long num = n;	// 必须是long，否则如果n=INT_MIN，-n会越界
        if(n < 0){
            num = -num;
            x = 1/x;
        }
        while(num){
            if(num & 1) ans *= x;
            x *= x;
            num >>= 1;
        }
        return ans;
    }
};

剑指 Offer 17. 打印从1开始的n位数

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

示例 1:

输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]

说明：

用返回一个整数列表来代替打印
n 为正整数

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof

class Solution {
public:
    vector<int> printNumbers(int n) {
        //  92.95%  77.06%
        int num=1;
        vector<int> res;
        for(int i=0;i<n;i++) { num*=10; }
        for(int i=1;i<num;i++) { res.push_back(i); }
        return res;
    }
};

#include <bits/stdc++.h>
using namespace std;
string str="0";
int n=2;

bool fun() {
    //    str+1;
    int len=str.size();
    int p=len-1;
    str[p]=str[p]+1;
    while(str[p]>'9') {
        str[p]='0';
        p--;
        if(p<0) {
            str="1"+str;
            len++;
        } else str[p]=str[p]+1;
    }
    if(len>n) return false;
    cout << str << " ";
    return true;
}

int main() {
    while(fun()) {}
}

剑指 Offer 18. 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

注意：此题对比原题有改动

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明：

题目保证链表中节点的值互不相同
若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        //  97.15%  32.40%
        if(!head) {return head;}
        if(head->val==val) {return head->next;}
        if(!head->next) {return head;}
        ListNode *p=head, *q=head->next;
        while(q) {
            if(q->val==val) {
                p->next=q->next;
                break;
            }
            p=q;
            q=q->next;
        }
        return head;
    }
};

剑指 Offer 19. 正则表达式匹配**

请实现一个函数用来匹配包含’. ‘和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但与”aa.a”和”ab*a”均不匹配。

示例 1:

输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。
示例 2:

输入:
s = “aa”
p = “a“
输出: true
解释: 因为 ‘‘ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。
示例 3:

输入:
s = “ab”
p = “.“
输出: true
解释: “.“ 表示可匹配零个或多个（’*’）任意字符（’.’）。
示例 4:

输入:
s = “aab”
p = “cab”
输出: true
解释: 因为 ‘*’ 表示零个或多个，这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。
示例 5:

输入:
s = “mississippi”
p = “misisp.”
输出: false
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和，无连续的 ‘*’。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof

class Solution {
public:
    //  38.47%  96.68%%
    bool isMatch(string s, string p) {
        int len1=s.size(), len2=p.size();
        if(!len1 && !len2) {return true;}
        else if(!len2) {return false;}	//	len1-0,len2>0有可能true
        return fun(s,p,0,0,len1,len2);
    }

    bool fun(string & s, string & p, int p1, int p2,
    int & len1, int &len2) {
        if(p1==len1 && p2==len2) {
            return true;
        } else if(p2==len2){
            return false;
        }

        if(p2+1<=len2-1 && p[p2+1]=='*') {
            if(fun(s,p,p1,p2+2,len1,len2)) { return true; }
            while(s[p1++]==p[p2] || p[p2]=='.') {
                if(p1==len1+1) {break;}
                if(fun(s,p,p1,p2+2,len1,len2)) { return true;}
            }
            return false;
        } else if(p1<len1 && (s[p1]==p[p2] || p[p2]=='.')) {
            return fun(s,p,p1+1,p2+1,len1,len2);
        }
        return false;
    }
};

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

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”、”5e2”、”-123”、”3.1416”、”-1E-16”、”0123”都表示数值，但”12e”、”1a3.14”、”1.2.3”、”+-5”及”12e+5.4”都不是。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof

class Solution {
public:
    bool isNumber(string s) {
        //  76.64%  93.10%
        //  暴力-懒得继续优化
        bool flag=false;
        bool flagP=false;
        bool flagE=false;
        int len=s.size();
        int i=0;
        while(s[i]==' ') { i++; }
        if(s[i]=='.') {
            flagP=true;
            if(i+1==len || (s[i+1]>'9'||s[i+1]<'0')) return false;
            i++;
        } else if(s[i]=='+'||s[i]=='-'){
            i++;
        }
        for(;i<len;i++) {
            if(s[i]=='e' || s[i]=='E') {
                i++;
                flagE=true;
                if(!flag) return false;
                break;
            } else if(s[i]=='.' && !flagP) {
                flagP=true;
                continue;
            }
            if(s[i]>'9'||s[i]<'0') {
                if(!flag) return false;
                break;
            } else {
                flag=true;
            }
        }
        if(flagE) {
            flag=false;
            if(i==len) {return false;}
            if(s[i]=='+'||s[i]=='-'){
                i++;
            }
            for(;i<len;i++) {
                if(s[i]>'9'||s[i]<'0') {
                    if(!flag) return false;
                    break;
                } else {
                    flag=true;
                }
            }
        }
        while(s[i]==' ') { i++; }
        if(i!=len||!flag) {return false;}
        return true;
    }
};

//	官答
//	状态机
class Solution {
public:
    enum State {
        STATE_INITIAL,
        STATE_INT_SIGN,
        STATE_INTEGER,
        STATE_POINT,
        STATE_POINT_WITHOUT_INT,
        STATE_FRACTION,
        STATE_EXP,
        STATE_EXP_SIGN,
        STATE_EXP_NUMBER,
        STATE_END,
    };

    enum CharType {
        CHAR_NUMBER,
        CHAR_EXP,
        CHAR_POINT,
        CHAR_SIGN,
        CHAR_SPACE,
        CHAR_ILLEGAL,
    };

    CharType toCharType(char ch) {
        if (ch >= '0' && ch <= '9') {
            return CHAR_NUMBER;
        } else if (ch == 'e' || ch == 'E') {
            return CHAR_EXP;
        } else if (ch == '.') {
            return CHAR_POINT;
        } else if (ch == '+' || ch == '-') {
            return CHAR_SIGN;
        } else if (ch == ' ') {
            return CHAR_SPACE;
        } else {
            return CHAR_ILLEGAL;
        }
    }

    bool isNumber(string s) {
        unordered_map<State, unordered_map<CharType, State>> transfer{
            {
                STATE_INITIAL, {
                    {CHAR_SPACE, STATE_INITIAL},
                    {CHAR_NUMBER, STATE_INTEGER},
                    {CHAR_POINT, STATE_POINT_WITHOUT_INT},
                    {CHAR_SIGN, STATE_INT_SIGN},
                }
            }, {
                STATE_INT_SIGN, {
                    {CHAR_NUMBER, STATE_INTEGER},
                    {CHAR_POINT, STATE_POINT_WITHOUT_INT},
                }
            }, {
                STATE_INTEGER, {
                    {CHAR_NUMBER, STATE_INTEGER},
                    {CHAR_EXP, STATE_EXP},
                    {CHAR_POINT, STATE_POINT},
                    {CHAR_SPACE, STATE_END},
                }
            }, {
                STATE_POINT, {
                    {CHAR_NUMBER, STATE_FRACTION},
                    {CHAR_EXP, STATE_EXP},
                    {CHAR_SPACE, STATE_END},
                }
            }, {
                STATE_POINT_WITHOUT_INT, {
                    {CHAR_NUMBER, STATE_FRACTION},
                }
            }, {
                STATE_FRACTION,
                {
                    {CHAR_NUMBER, STATE_FRACTION},
                    {CHAR_EXP, STATE_EXP},
                    {CHAR_SPACE, STATE_END},
                }
            }, {
                STATE_EXP,
                {
                    {CHAR_NUMBER, STATE_EXP_NUMBER},
                    {CHAR_SIGN, STATE_EXP_SIGN},
                }
            }, {
                STATE_EXP_SIGN, {
                    {CHAR_NUMBER, STATE_EXP_NUMBER},
                }
            }, {
                STATE_EXP_NUMBER, {
                    {CHAR_NUMBER, STATE_EXP_NUMBER},
                    {CHAR_SPACE, STATE_END},
                }
            }, {
                STATE_END, {
                    {CHAR_SPACE, STATE_END},
                }
            }
        };

        int len = s.length();
        State st = STATE_INITIAL;

        for (int i = 0; i < len; i++) {
            CharType typ = toCharType(s[i]);
            if (transfer[st].find(typ) == transfer[st].end()) {
                return false;
            } else {
                st = transfer[st][typ];
            }
        }
        return st == STATE_INTEGER || st == STATE_POINT || st == STATE_FRACTION || st == STATE_EXP_NUMBER || st == STATE_END;
    }
};

上一篇文章

LeetCode - 剑指Offer - Part1
继续阅读下一篇

LeetCode - 剑指Offer - Part3

CATALOG

1. 剑指 Offer 11. 旋转数组的最小数字
2. 剑指 Offer 12. 矩阵中的路径*
3. 剑指 Offer 13. 机器人的运动范围*
4. 剑指 Offer 14. 剪绳子*
5. 剑指 Offer 15. 二进制中1的个数
6. 剑指 Offer 16. 数值的整数次方*
7. 剑指 Offer 17. 打印从1开始的n位数
8. 剑指 Offer 18. 删除链表的节点
9. 剑指 Offer 19. 正则表达式匹配**
10. 剑指 Offer 20. 表示数值的字符串*



缺失模块。
1、请确保node版本大于6.2
2、在博客根目录（注意不是archer根目录）执行以下命令：
npm i hexo-generator-json-content --save
3、在根目录_config.yml里添加配置：

jsonContent:
  meta: false
  pages: false
  posts:
    title: true
    date: true
    path: true
    text: false
    raw: false
    content: false
    slug: false
    updated: false
    comments: false
    link: false
    permalink: false
    excerpt: false
    categories: true
    tags: true