Google Foobar 挑战 2 级 "Hey-I-Already-Did-That"

Question

我需要帮助解决 Google 的 Foobar 挑战的第二关。

指挥官 Lambda 使用自动算法随机分配小兵任务，以让她的小兵保持警惕。但是您已经注意到该算法中的一个缺陷 - 它最终会自行循环，因此它不会在迭代时分配新的 minions，而是陷入价值循环，因此相同的 minions 最终会反复执行相同的任务再次。您认为向指挥官 Lambda 证明这一点将有助于您为下一次晋升做准备。

你算出算法有以下过程：

1) 从一个随机的minion ID n开始，它是一个基数b
中长度为k的非负整数 2) 将 x 和 y 定义为长度为 k 的整数。 x有n的数字降序排列，y有n的数字升序排列
3) 定义 z = x - y。如有必要，将前导零添加到 z 以保持长度 k
4) 赋值n = z得到下一个minion ID，回到步骤2

例如，给定 minion ID n = 1211，k = 4，b = 10，则 x = 2111，y = 1112 和 z = 2111 - 1112 = 0999。那么下一个 minion ID 将是 n = 0999然后算法再次迭代：x = 9990、y = 0999 和 z = 9990 - 0999 = 8991，依此类推。

根据 n、k（从 n 派生）和 b 的值，算法在某个点达到循环，例如达到恒定值。例如，从n = 210022, k = 6, b = 3开始，算法会到达值的循环[210111, 122221, 102212]，无论继续迭代多少次，都会停留在这个循环中。从n = 1211开始，例程将达到整数6174，并且由于7641 - 1467是6174，因此无论迭代多少次都将保持该值。

给定一个 minion ID 作为字符串 n，表示基数 b 中长度为 k 的非负整数，其中 2 <= k <= 9 且 2 <= b <= 10，编写函数 solution(n, b)其中returns是上述算法的结束循环长度，从n开始。例如，在上面的示例中，solution(210022, 3) 将 return 3，因为在 102212 上迭代将 return 到 210111，当以 3 为基数完成时。如果算法达到常数，例如 0 ，则长度为1.

测试用例：
Solution.solution("1211", 10) returns 1
Solution.solution("210022", 3) returns 3

这是我的代码：

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {

    public static int solution(String n, int b) {
        int k = n.length();
        String m = n;
        ArrayList<String> minionID = new ArrayList<>();

        while (!minionID.contains(m)) {
            minionID.add(m);
            char[] s = m.toCharArray();
            Arrays.sort(s);
            int y = Integer.parseInt(toString(s));
            int x = Integer.parseInt(reverseString(s));
            if (b == 10) {
                int intM = x - y;
                m = Integer.toString(intM);
            } else {
                int intM10 = ((int) Integer.parseInt(toBase10(x,b))) - ((int) Integer.parseInt(toBase10(y, b)));
                m = toBaseN(intM10, b);
            }

            m = addLeadingZeros(k, m);
        }
        System.out.println(minionID);
        return minionID.size() - minionID.indexOf(m);
    }

    private static String toBaseN (int intBase10, int b) {
        int residual = intBase10;
        ArrayList<String> digitsBaseN = new ArrayList<>();

        while (residual >= b) {
            int r = residual % b;
            digitsBaseN.add(Integer.toString(residual));
            residual = (residual - r) / b;
        }
        digitsBaseN.add(Integer.toString(residual));

        StringBuilder reverseDigits = new StringBuilder();
        for (int i = digitsBaseN.size() -1; i >= 0; i--) {
            reverseDigits.append(digitsBaseN.get(i));
        }
        return reverseDigits.toString();
    }

    private static String toBase10 (int intBaseN, int b) {
        int[] xArr = new int[Integer.toString(intBaseN).length()];
        int count = 0;
        for (int i = xArr.length - 1; i >= 0; i--) {
            xArr[count] = Integer.toString(intBaseN).charAt(i) - '0';
            count++;
        }

        int yBase10 = 0;

        for(int i = 0; i < xArr.length; i++) {
            yBase10 += xArr[i] * (Math.pow(b, i));
        }
        return Integer.toString(yBase10);
    }

    public static String toString(char[] arr) {
        StringBuilder newString = new StringBuilder();
        for (char c : arr) {
            newString.append(c);
        }
        if (newString.toString().contains("-")) {
            newString.deleteCharAt(0);
        }
        return newString.toString();
    }

    public static String reverseString(char[] arr) {
        StringBuilder newString = new StringBuilder();
        for (int i = arr.length - 1; i >= 0; i--) {
            newString.append(arr[i]);
        }
        if (newString.toString().contains("-")) {
            newString.deleteCharAt(newString.length()-1);
        }
        return newString.toString();
    }

    public static String addLeadingZeros(int k, String z) {
        if (k > z.length()) {
            String zeros = "";
            for (int i = 0; i < (k - z.length()); i++) {
                zeros += "0";
            }
            zeros += z;
            return zeros;
        }
        return z;
    }

它只适用于十个测试用例中的三个

Answer 1

def answer(n, b):

    k = len(n)
    m = n
    mini_id = []
    while m not in mini_id:
        mini_id.append(m)
        s = sorted(m)
        x_descend = ''.join(s[::-1])
        y_ascend = ''.join(s)        
        if b == 10:
            int_m = int(x_descend) - int(y_ascend)
            m = str(int_m)
        else:
            int_m_10 = int(to_base_10(x_descend, b)) - int(to_base_10(y_ascend, b))
            m = to_base_n(str(int_m_10), b)

        m =  (k - len(m)) * '0' + m
    return len(mini_id) - mini_id.index(m)

Google Foobar 挑战 2 级 "Hey-I-Already-Did-That"

Google Foobar Challenge Level 2 "Hey-I-Already-Did-That"

java

algorithm

base