10月19日小米第四场笔试第二道编程题

补充一个例子:

1 -> 5 -> 25 -> 125 -> 512

*a *a *a 右移

这个似乎能和上面的形成互补。

小小一步,独立写出的深搜。

结合题例和自己捏的例子大致没什么问题。

可以一看。

总体来说,还没到必须用动态规划之类的我还没掌握的算法才能解决的地步。

debug技巧得到了练习。

(我知道要回溯这件事就是debug出来的!

同时局部变量是不用回溯的我也才明白。)

凌乱的梳理:

尝试使用这样的思路来解题:先考虑大多数情况下的需要的代码,再考虑极端情况下的补丁代码。

A魔法和B魔法是可以交叉使用的——这就意味着可能异常的多,这就是递归出马的时候了。

但除了特殊情况,只能先用A魔法。

右移使用转换字符串实现了,剪切+重拼接。

我觉得关键在于B魔法的使用有两种可能。

一种是位数小于的时候,是绝对不可能得出来的,所以要在B1方法内再调A方法,此时注意全局静态变量的上下文,并且在失败时复原(原来这就是回溯),成功时就不用了。

另一种是位数等于的时候,答案就在此处得出。每循环一次,就在循环内用if检查一次,如果相等了,就及时赋好值退出。

注释的是A、B魔法在最少时的使用次数,如果拓展时也可以问这个。

sc是工具类,直接记忆。

package com.xiaomi;

import java.io.*;

public class Test2 {

    public static int counter = Integer.MAX_VALUE;
    public static int a, b, AC, BC, o;
    public static int printAC, printBC;

    public static class sc {

        static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

        public static int nextInt() throws IOException {
            st.nextToken();
            return (int) st.nval;
        }

        public static <T> void write(T o) {
            pw.print(o);
        }


    }

    public static void A(int o) {
        while (String.valueOf(o).length() <= String.valueOf(b).length()) {
            o *= a;
            AC++;
            if (o == b) {
//                if ((AC + BC) < counter) {
//                    printAC = AC;
//                    printBC = BC;
//                }
                counter = Math.min((AC + BC), counter);
                return;
            }
            if (String.valueOf(o).length() < String.valueOf(b).length()) {
                B1(o);
            } else if (String.valueOf(o).length() == String.valueOf(b).length()) {
                B2(o);
            }
        }
    }

    // 处理位数不等,实质是扩展可能。
    public static void B1(int o) {
        int origin = o;
        int copyBC = 0;
        do {
            if (o < 10 || o % 10 == 0) {
                break;
            }
            String s = String.valueOf(o);
            s = s.substring(s.length() - 1) + s.substring(0, s.length() - 1);
            o = Integer.parseInt(s);
            copyBC++;

            if (o == origin) {
                copyBC = 0;
            }

            BC += copyBC;
            int tmpAC = AC;
            A(o);
            if (o == b) {
                break;
            } else {
                AC = tmpAC;
                BC -= copyBC;
            }

        } while (o != origin);

    }

    public static void B2(int o) {
        int origin = o;
        int copyBC = 0; // 用于单独记录每一次B2中右移操作的次数,因为原先B1的右移计数在B2中会被清零,可这样忽略了此刻的B2就是在之前的B1右移操作上生长出来的。
        do {
            if (o < 10 || o % 10 == 0) {
                break;
            }

            String s = String.valueOf(o);
            s = s.substring(s.length() - 1) + s.substring(0, s.length() - 1);
            o = Integer.parseInt(s);
            copyBC++;

            if (o == b) {
                BC += copyBC;
//                if ((AC + BC) < counter) {
//                    printAC = AC;
//                    printBC = BC;
//                }
                counter = Math.min((AC + BC), counter);
                break;
            }
        } while (o != origin);
    }

    public static void main(String[] args) throws IOException {
        a = sc.nextInt();
        b = sc.nextInt();

        AC = 0;
        BC = 0;
        printAC = 0;
        printBC = 0;
        o = 1;

        A(o);

        sc.write(counter == Integer.MAX_VALUE ? -1 : counter);
//        sc.write("\nAC: " + printAC + " BC: " + printBC); 
        sc.pw.flush();

    }


}


#我的求职思考#
全部评论
佬,现在到那步了,为什么我还是笔试中
点赞 回复 分享
发布于 2024-10-24 15:29 陕西
厉害
点赞 回复 分享
发布于 2024-10-21 21:27 北京

相关推荐

每晚夜里独自颤抖:要求太多的没必要理
点赞 评论 收藏
分享
06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
评论
3
3
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务