Google Foobar挑战级别2“嘿，我已经做到了”

Z时代
2024-01-10
分类：问答

在解决Google Foobar挑战的第二阶段时，我需要帮助。

指挥官Lambda使用自动算法将小兵随机分配给任务，以使小兵保持脚尖。但是您已经注意到该算法的一个缺陷-

它最终会循环返回自身，因此，它不会像迭代那样分配新的奴才，而是陷入了一个值循环中，从而使相同的奴才最终可以完成并执行相同的任务。再次。您认为向Lambda指挥官证明这一点将为您的下一次晋升提供依据。

您已经确定该算法具有以下过程：

1）以随机小号ID n开头，它是基数b中长度为k的非负整数

。2）定义x和y为长度为k的整数。x具有n的降序数字，而y具有n的升序数字

3）定义z = x-y。在必要时向z添加前导零以保持长度k

4）分配n = z获得下一个奴才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），该函数返回长度为以上算法的结束循环从n开始。例如，在上面的示例中，solution（210022，3）将返回3，因为在基数3中完成时在102212上进行迭代将返回210111。如果算法达到常数（例如0），则长度为1。

测试用例：

Solution.solution（“ 1211”，10）返回1

Solution.solution（“ 210022”，3）返回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;
    }

仅适用于十个测试用例中的三个

回答：

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)