java - 数字谜题解决方案的数字平方和可以进一步优化吗？

Question

下面的代码计算一个值，该值作为str中每个数字的平方和而获得。这个总和再次计算m次。

Example: m = 2, str="123"
At m=1 (1^2)+(2^2)+(3^2) = 1+4+9 = 14
At m=2 (1^2)+(4^2) = 1+16 = 17

因此 17 应该是该输入的最终答案。对于大量输入或针对上面的 1000 个测试用例运行时，此代码会给出超出时间限制的错误。这段代码可以进一步优化吗？

Test case will be less than 1001
1 <= str.length(), m <= 10^9

         public static void puzzle(int m,String str) {
            int ans = 0;
            while (m > 0) {
                ans=0;
                m--;
                int j = 0;
                while (j < str.length()) {
                    int val = Integer.parseInt(str.charAt(j) + "");
                    ans +=  val* val;
                    j++;
                }
                str = String.valueOf(ans);
            }
            System.out.println(ans);
        }

我已经尽力了，可以想出上述迭代解决方案。即使使用递归解决方案也无法改进。

递归代码:

public static int solve(int m, String n){
        if(m < 1)
            return Integer.parseInt(n);
        int idx = 0;
        int res = 0;
        while(idx< n.length()){
            int val = Integer.parseInt(n.charAt(idx) + "");
            res += val*val;
            idx++;
        }
        return solve(m-1,String.valueOf(res));
    }

Answer 1

不要使用字符串进行操作。坚持使用整数。

由于您只是将数字的平方相加，因此您可以从最后一位数字开始执行此操作，因此循环执行模数和除以 10，直到为零，即可实现此目的。

public static int puzzle(int m, String str) {
    int value = Integer.parseInt(str);
    for (int i = 0; i < m; i++) {
        int sum = 0;
        for (; value != 0; value /= 10) {
            int digit = value % 10;
            sum += digit * digit;
        }
        value = sum;
    }
    return value;
}