题解 | #最大数#

一.题目描述
NC534最大数
给定一个包含大写英文字母和数字的句子，找出这个句子所包含的最大的十六进制整数，返回这个整数的值。数据保证该整数在int表示范围内
图片说明
二.算法(暴力)
根据题目意思我们会了解这一串字符串s中只包含了数字和大写字母而且找出任意字串作为16进制数，求合法的最大数，但是结果一定是int型范围内。那么我们可以暴力的去想，只需要遍历字符串，把每个字符都可以当成一个数字的起点然后找到该数字的终点，对于第一个不合法的字母，将字串截取出来转换成数字，维护最大值即可。下面是完整代码：

class Solution {
public:
    bool ck(char c){ //判断字符是不是属于十六进制
        if((c >= '0' && c <= '9') || (c >= 'A' && c <= 'F')) return true;
        return false;
    }
    int toint(char x){ //把字符串转换为数字
        if(x>='A'&&x<='F')
            return x-'A'+10;
        return x-'0';
    }
    int num(string str){ //将字符串转换成十进制int型
        int res = 0;
        for(int i = 0; i < str.length(); i++)
            res += toint(str[i]) * pow(16, str.length() - i - 1);
        return res;
    }
    int solve(string s) {
        int start = 0;//开始的指针
        int res=0;//最后的返回值
        while(start < s.length()){ //每个点都可以做起点
            int i = start;
            while(!ck(s[i])||s[i] == 0) //找到最远区间
                i++;
            int count = 0;
            while(ck(s[start++]))
                count++;
            res = max(res, num(s.substr(i, count))); //找出每次的最大值
        }
        return res;
    }
};

时间复杂度： $O(n^{2})$ 对每一个点坐标都要找出其终点，所以类似双重循环
空间复杂度： $O(1)$ 不需要什么额外空间
优缺点：方便理解，但是不容易实现
三.算法(贪心)
图片说明
算法二的思路很简单，但是时间复杂度很高，所以我们可以利用贪心的思路去优化一下。首先我们要知道字符串越长对应着的十六进制对应的十进制的值就会很大，所以我们只需要对每一个符合的大区间进行判断，然后比较每一个大区间的最大值就可以找出最终的最大值，下面是完整代码：

class Solution {
public:
    //将字符串转换为数字
    int toint(string a) {
        int ret = 0;
        for (int i = 0; i < a.length(); i++) {
            ret *= 16;
            if (a[i] >= '0' && a[i] <= '9') ret = ret + a[i] - '0';
            else ret = ret + a[i] - 'A' + 10;
        }
        return ret;
    }

    int solve(string s) {
        int ans = 0;
        int len = s.length();
        string a;//临时字符串来记录每一个大区间
        a="";//刚开始临时字符串是空
        for (int i = 0; i < len; i++) {
            if ((s[i]>='0'&&s[i]<='9')||(s[i]>='A'&&s[i]<='F')) {
                a+=s[i];//临时字符串加入字符
            } else {
                //判断大区间的最大值
                if (i!=0&&((s[i-1]>='0'&&s[i-1]<='9')||(s[i-1]>='A'&&s[i-1]<='F'))) {
                    ans= max(ans, toint(a));
                    a="";//对字符串进行清空
                }
            }
        }
        return ans;
    }
};

时间复杂度： $O(n)$ 对每一个点坐标进行一次遍历
空间复杂度： $O(1)$ 不需要什么额外空间
优缺点：方便理解而且容易实现