美团笔试测试方向第二场算法题

第一题：字符串匹配

有相对应的匹配模式

    public static void main(String[] args) {
        int m ;
        Scanner in = new Scanner(System.in);
        m = in.nextInt();
        in.nextLine();
        for(int i = 0; i < m ;i++){
            System.out.println(check(in.nextLine()));
        }
    }

    public static String check(String transportId){
        if(transportId.length() < 2) return "Invalid";
        String str = transportId.substring(0,2);
        String context = transportId.substring(2);

        switch (str){
            case "SF" :
                if(context.length() != 10) return "Invalid";
                for(char c : context.toCharArray()){
                    if (c < '0' || c > '9'){
                        return "Invalid";
                    }
                }
                return "Normal";
            case "EX" :
                if(context.length() != 10) return  "Invalid";
                for(int i = 0; i< context.length(); i++){
                    if(i < 2){
                        if(context.charAt(i) < 'A' || context.charAt(i) > 'Z'){
                            return "Invalid";
                        }
                    }
                    if(context.charAt(i) < '0' || context.charAt(i) > '9'){
                        return "Invalid";
                    }
                }
                return "Express";
            case "IN":
                if(context.length() != 9) return "Invalid";
                int sum = 0;
                for(int i = 0; i< context.length(); i++){
                    if(i < 3){
                        if(context.charAt(i) < 'A' || context.charAt(i) > 'Z'){
                            return "Invalid";
                        }
                    }
                    if(context.charAt(i) < '0' || context.charAt(i) > '9'){
                        return "Invalid";
                    }
                    if(i >= context.length()-3){
                        sum += context.charAt(i) - '0';
                    }
                }
                if(sum % 2 == 0) return "InterNational";
                else return "Invalid";
            default:
                if(transportId.length() != 12) return "Invalid";
                if(transportId.charAt(0) == '0') return "Invalid";
                for(char c : transportId.toCharArray()){
                    if(c > '9' || c < '0') return "Invalid";
                }
                return "E-commerce";
        }
    }

通过62.5% 后面的特殊情形想不到了

第二题

字符匹配

遇到R反转 遇到Z回退操作（如果是R就反转回来，如果是添加操作就删除）

   static StringBuilder res;
   static String target;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        for (int i = 0;i < n;i++){
            target = in.nextLine();
            res = new StringBuilder();
            dfs(0,false,0);
            System.out.println(res.toString());
        }
    }

    public static void dfs(int i,boolean isRev, int addWhat){
            if(i >= target.length()) return;

        //尝试回溯
        if(target.charAt(i) == 'Z'){
            if(isRev){
                res.reverse();
                isRev = false;
            }
            if(addWhat != 0){
                res.deleteCharAt(addWhat);
                addWhat = 0;
            }
        }

            if(target.charAt(i) == 'R') {
                res.reverse();
                isRev = true;
            }else{
                isRev = false;
            }
            //添加参数
        addWhat = 0;
        if(target.charAt(i) != 'R' && target.charAt(i) != 'Z') {
            res.append(target.charAt(i));
            addWhat = res.length() - 1;
        }

        //传递的参数为i+1 这一步的操作
        dfs(i+1,isRev,addWhat);



    }

通过50%，应该还需要回溯，想不到了

第三题

求和 给定l1 r1 l2 r2

存在以下关系 f(a,b) 当a是b的倍数时 f(a,b) = 1反之为0

现在要求和

贴一段暴力代码

        for(int j = l2 ;j<=r2;j++){
            for(int i = l1;i<=r1;i++){
                sum+= f(i,j);
            }
        }

麻了