题解 | #最大数#

题目描述
给定一个包含大写英文字母和数字的句子，找出这个句子所包含的最大的十六进制整数，返回这个整数的值。数据保证该整数在int表示范围内

方法一：暴力求解

求解思路
对于本题目求解，我们首先想到暴力遍历的想法来求解，即遍历字符串的每个字符并以其为起点，然后找到数字的终点，即第一个不合法的字母，并对字符串截取出来转换成数字，并记录最大值即可，最终即可得到本题的答案。

图片说明

解题代码

class Solution {
public:
    int char_to_int(char c)
    {   //将字符转换成数字
        if(c >= 'A' && c <= 'F')
            return c - 'A'  + 10;
        return c - '0';
    }
    bool hex_valid(char c)
    {   //判断字符是否合法
        if((c >= '0' && c <= '9') || (c >= 'A' && c <= 'F'))
            return true;
        return false;
    }
    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 myres = 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++;
            myres = max(myres, hex_to_dec(s.substr(i, count))); // 记录最大值
        }
        return myres; // 返回结果
    }
};

复杂度分析
时间复杂度：两层循环，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：没有使用额外的内存地址空间，因此空间复杂度为 $O(1)$

方法二：贪心思想求解

求解思路
对于本题我们也可以使用贪心的思想进行求解，即每次只取最大区间，我们遍历字符串，每次遇到数字或者字母A到F就转换为数字，并加入到sum中进行记录，并且后续的操作同前面，并且更新sum中的记录，最后输出最大值即可。

图片说明

解题代码

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

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：没有使用额外的内存地址空间，因此空间复杂度为 $O(1)$