慧策笔试 - 1002

缺失的订单号

题面

找出缺失的订单号：假设有若干个订单号（orderId）, 它们的类型为 int, 且每个订单号在数组或列表中是唯一的。现在一个数组（大小为 $n$）经过某个流程处理后，缺失了一个订单号（数组大小变为 $n-1$），请通过算法尽可能快地找出缺失的订单号，并且写出算法的复杂度。

注: $0 < orderId < 65536, 0 < n < 30000$

思路与代码：

计算两个数组的元素总和，两者之差即为缺失的订单号。

public int findLostOrderId(int[] originalList, int[] lostList) {
    int sum1 = 0;
    int sum2 = 0;
    
    for (int orderId : originalList) {
        sum1 += orderId;
    }
    
    for (int orderId : lostList) {
        sum2 += orderId;
    }
    
    return sum1 - sum2;
}

完全平方数

题面

将一个数拆为完全平方数之和：输入一个整数 $n$, 返回和为 $n$ 的完全平方数的最少数量。

注: 完全平方数是一个整数, 值等于另一个整数的平方。如 $1$、$4$、$9$ 和 $16$ 都是完全平方数，而 $3$ 和 $11$ 不是。$0 < n <= 10000$。

如: $8=4+4$，输出为 $2$；$16=16$，输出为 $1$

思路与代码：

转化为背包问题。其中每个完全平方数是一个物品，目标是找到最少的物品数量使得它们的和等于 $n$。

步骤：

1. 定义 DP 数组：dp[n + 1]，其中 dp[i] 表示和为 $i$ 的完全平方数的最少数量。
2. 初始化：dp[0] = 0，其余 dp[i] 初始化为一个较大的值。
3. 状态转移：对于每个 $i(1 \leq i \leq n)$，尝试用所有小于等于 $i$ 的完全平方数来更新 dp[i]
   • 对于每个完全平方数 $j^2$（$j^2 <= i$），更新 dp[i] = min(dp[i], dp[i - j^2] + 1)。
4. 结果：dp[n] 即为所求的最少完全平方数的数量。

public int numSquares(int n) {
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        dp[i] = n + 1;
    }

    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j * j <= i; j++) {
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
        }
    }
    
    return dp[n];
}