题解 | #最大数#

思路：

题目的主要信息：

一串字符串s中只包含了数字和大写字母
找出任意子串作为16进制数，求合法的最大数
结果一定是int型范围内

方法一：暴力法
具体做法：
遍历字符串每个字符都可以当成一个数字的起点，找到该数字的终点：第一个不合法的字母，将字串截取出来转换成数字，维护最大值即可。

class Solution {
public:
    bool hex_valid(char c){ //判断字符是否合法
        if((c >= '0' && c <= '9') || (c >= 'A' && c <= 'F'))
            return true;
        return false;
    }
    int char_to_int(char c){ //将字符转换成数字
        if(c >= 'A' && c <= 'F')
            return c - 'A'  + 10;
        return c - '0';
    }
    int hex_to_dec(string str){ //将字符串转换成十六进制数字再换成十进制int型
        int res = 0;
        for(int i = 0; i < str.length(); i++)
            res += char_to_int(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(!hex_valid(s[i]) || s[i] == 0) //找到最远区间
                i++;
            int count = 0;
            while(hex_valid(s[start++]))
                count++;
            res = max(res, hex_to_dec(s.substr(i, count))); //记录最大值
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n^2)$ ，最坏相当于两层嵌套循环，每层为 $O(n)$
空间复杂度： $O(1)$ ，无额外空间使用

方法二：贪心
具体做法：
上述方法一解法虽然最直观，但是重复计算了很多内容，因此我们可以用贪心思想，每次只取最大区间，比最大区间小的区间组成的数字一定最大区间小，因此我们遍历字符串，每次遇到数字或者A-F就转换为数字，加入int型变量sum中，并将前序存储的值乘上16，每次遇到大于F的字母，就将sum中内容拿出来与返回值比较，维护最大值，再将sum重新置为0.
图片说明

class Solution {
public:
    int solve(string s) {
        int res = 0; 
        int sum = 0; //存储每次遇到的值
        for(int i = 0; i < s.length(); i++){ 
            if(s[i] > 'F'){ //遇到大于F的字母，更新res为当前最大值
                res = max(res, sum);
                sum = 0;
                continue;
            }
            int a = s[i] >= 'A' ? s[i] - 'A' + 10 : s[i] - '0'; //组合成数字
            sum = sum * 16 + a;
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，一次遍历，循环 $n$ 个
空间复杂度： $O(1)$ ，无额外空间使用