0

我正在尝试编写一种算法，该算法将找到给定整数的最大完美平方，并尽可能快地每次从总数中减去它们的值。这有点难以解释，对于有点模棱两可的标题，我深表歉意，所以我将给出一些输入/输出示例：

  • 输入：23
  • 输出：[16、4、1、1、1]
  • 解释：25 (5x5) 太大，但 16 (4x4) 适合。将其添加到数组中并从 23 (7) 中减去 16。下一个适合的最大完美正方形是 4 (2x2)，因​​此将其添加到数组中并从 7 (3) 中减去 4。从这里开始，最大的完美正方形就是 1 (1x1)。所以将 1 添加到数组中，直到我们得到 0。
  • 输入：13
  • 输出：[9, 4]
  • 解释： 9 (3x3) 是最大的正方形，因此将其添加到数组中并从 13 (4) 中减去。那么 4 也是一个完美的正方形，所以添加它并在那里结束。

我的解决方案如下（变量名称与向我提出问题的方式相关）：

public static int[] solution(int startingSquareYards) {

        ArrayList<Integer> largestSquares = new ArrayList<Integer>();

        // Cast for use with Math. methods
        double remainingSquareYards = (double) startingSquareYards;

        while (remainingSquareYards > 0) {

            double largestSquareRoot = Math.floor(Math.sqrt(remainingSquareYards));
            
            // Edit - used to be: 
            // double yardsOfMaterialUsed = Math.pow(largestSquareRoot, 2);
            double yardsOfMaterialUsed = largestSquareRoot * largestSquareRoot;

            remainingSquareYards -= yardsOfMaterialUsed;

            largestSquares.add((int) yardsOfMaterialUsed);

        }

        int[] solutionArray = largestSquares.stream().mapToInt(i -> i).toArray();

        return solutionArray;
    }

我正在征求对我的解决方案的意见，以及我是否可以以任何方式优化它以提高时间/空间复杂性、简单性（同时保持易于阅读/理解）等。它目前适用于我编写的所有测试，但我可能缺少边缘情况或需要改进的地方 - 输入的起始平方码可以在 1 到 1,000,000 之间。任何建设性的反馈表示赞赏:)

感谢您的关注！

4

1 回答 1

2

如评论中所述，您的确切要求尚不清楚。以下代码将重现您的问题的示例。通常，它会更喜欢包括最大的正方形而不是产生最短的解决方案。
例如32将 yield[25, 4, 1, 1, 1]而不是[16, 16]. 这似乎是您的意图，因为您的示例23预计会产生[16, 4, 1, 1, 1]而不是[9, 9, 4, 1]

private static final BitSet SQUARES = new BitSet(1_000_001);
static { for(int i = 0; i <= 1_000; i++) SQUARES.set(i * i); }

public static int[] solution(int startingSquareYards) {
    IntStream.Builder b = IntStream.builder();
    for(int square; startingSquareYards > 0; startingSquareYards -= square) {
        square = SQUARES.previousSetBit(startingSquareYards);
        b.add(square);
    }
    return b.build().toArray();
}

它旨在处理您在 1 到 1,000,000 之间指定的输入数字。

它只是准备BitSet告诉哪个整数是平方数，这允许快速找到等于或小于某个值的最大平方数。这是一个线性搜索，但是一次可以处理 64 个数字的搜索，使用便宜的整数运算。这避免了任何昂贵的浮点运算。它也没有对Integer对象的拳击。

于 2021-12-10T19:06:34.047 回答