题解 | #最大数#

思路

题目分析

1. 题目给出一串字符串，包含数字和大写英文字母
2. 题目要求我们找出其中连续的最大的一组十六进制字符串
3. 并最终返回其十进制的结果

• 方法一使用指针的思路，从前往后按照顺序访问字符串，将首指针和尾指针分别指向一组合法的16进制子字符串，然后计算其10进制值，下一轮继续用首尾指针读取一个16进制子字符串，转换成10进制值，并以此循环迭代计算出所有的10进制值，记录返回最大值即可
• 方法二使用贪心思路，优化方法一中获取子字符串的部分，贪心地选择最大的区间存储到返回值中，贪心的最大距离就是遇到非法16进制字符的时候。最终返回16进制最大值即可。

方法一：双指针

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    bool legal(char c) {        // 判断字符是否是16进制合法
        return (c <= '9' && c >= '0') || (c >= 'A' && c <= 'F');
    }

    int c2i(char c) {           // 将16进制字符转换成10进制数
        if(c >= 'A' && c <= 'F') return c - 'A' + 10;
        return c - '0';
    }

    int hex2dec(string s) {     // 将16进制字符串转换成10进制数字
        int n = 0;
        for(int i = 0; i < s.size(); i++) {
            n += c2i(s[i]) * pow(16, s.size() -i -1);
        }
        return n;
    }
    int solve(string s) {
        // write code here
        int res = 0;
        int n = s.size();
        for(int i = 0, j = 0; i < n; i++) {
            if(legal(s[i]) && s[i] != '0') {    // 左指针通过循环一直找到合法的16进制子字符串的开头
                for(j = i; j < n; j++) {
                    if(!legal(s[j])) {          // 右指针通过循环找到合法16进制子字符串的末尾
                        break;
                    }
                }
                res = max(res, hex2dec(s.substr(i, j-i)));    //返回当前双指针限制区域内的16进制子字符串的10进制值，维护最大值
                i = j;                          // 迭代从下一处继续开始
            }
        }
        return res;                             // 返回最大值
    }
};

复杂度分析

• 时间复杂度：，虽然看起来有双重循环，但是对字符串只按序访问了一次
• 空间复杂度：，无额外空间申请

方法二：贪心

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    int hex2dec(char c) {    // 将表示16进制的字符转换为十进制的数字
        return c >= 'A' ? c - 'A' + 10 : c - '0';
    }

    int solve(string s) {
        // write code here
        int sum = 0;
        int mx = 0;
        for(int i = 0; i < s.size(); i++) {
            if(s[i] > 'F') {                    // 如果碰到非16进制的字符，则认为要在新的起点处重新计算一组sum值
                mx = max(mx, sum);              // 维护最大值
                sum = 0;                        // 重置sum值，准备计算新的一组十六进制数的值
                continue;
            }
            int num = hex2dec(s[i]);            // 将当前访问字符转换为16进制
            sum = sum * 16 + num;               // 通过多轮次循环来计算16进制数
        }
        return mx;
    }
};

复杂度分析

• 时间复杂度：，一重循环的时间开销
• 空间复杂度：，无额外空间申请