题解 | #最大数#

题目：
给定一个包含大写英文字母和数字的句子，找出这个句子所包含的最大的十六进制整数，返回这个整数的值。数据保证该整数在int表示范围内
关键点：判断元素是否'F'
方法一：暴力解法:

从字符串的第一个字符开始，定位到最远有效区间的起点
从有效区间起点开始往后遍历，直到找到不合法字符，记录下有效区间的长度
将有效区间截取出来，计算其转换为十进制的大小，保存到max中
重复以上步骤，直到扫描完字符串

图片说明

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int solve (String s) {
        // write code here
        int start=0;//字符串起点
        int max=0;
        while(start<s.length()){
            int i=start;
            while(!hexValid(s.charAt(i)))i++;//找到最远有效区间的起点
            start=i;//定位有效区间的起点
            int cnt=0;//记录有效区间的长度
            while(start<s.length()&&hexValid(s.charAt(start++)))cnt++;
            max=Math.max(max,hexToDec(s.substring(i,i+cnt)));//截取有效区间进行计算，保存最大值
        }return max;
    }
    //判断字符是否合法
    boolean hexValid(char c){
        if((c>='0'&&c<='9'||c>='A'&&c<='F'))return true;
        return false;
    }
    //将字符串转换为十六进制数再换成十进制int型
    int hexToDec(String s){
        int res=0;
        for(int i=s.length()-1;i>=0;i--){
            char c=s.charAt(i);
            int x=(c>='A')?c-'A'+10:c-'0';
            res+=x*Math.pow(16,s.length()-i-1);
        }return res;
    }
}

复杂度：
时间复杂度：两层循环，最坏时间复杂度为 $图片说明$
空间复杂度：常数级的额外空间使用， $O(1)$

方法二：贪心
从后往前遍历：
每次遇到合法字符则转换为对应的数字，并保存到sum中，直到遇到'F'，将sum与原来的最大值比较，更新最大值max，并将sum和十六进制数的位数len置0,如果字符串还没遍历结束则重新开始新一轮的寻找，注意边界条件i=0，包括最后一个十六进制数需要比较，循环结束，最后返回最大值
图片说明

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int solve (String s) {
        // write code here
        //max维护最大值，sum是十六进制数转为的十进制数,len统计每次找到的十六进制数位数
        int max=0,sum=0,len=0;
        for(int i=s.length()-1;i>=0;i--){
            //如果碰到合法字符则加入十六进制数
            char c=s.charAt(i);
            if((c>='0'&&c<='9')||(c>='A'&&c<='F')){
                int x=(c>='A')?10+c-'A':c-'0';
                sum+=x*Math.pow(16,len);
                len++;
            }
            //如果遇到大于'F'的字符，更新最大值，且字符串还没遍历结束，sum和len置0,寻找下个可能的十六进制数
            //i==0包括最后一个十六进制数
            if(c>'F'||i==0){
                max=Math.max(max,sum);//更新最大值
                len=0;
                sum=0;
                continue;
            }
        }return max;
    }
}

复杂度：
时间复杂度：遍历一次是字符串， $O(n)$
空间复杂度：使用额外变量，常数级额外空间， $O(1)$