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();

    }


}