58同城

90分钟：14道单选，6道多选，3道编程

第一题¶

题目背景：¶

平均值是统计学中常用的指标之一，可以表示一组数据的中心趋势。然而，平均值容易受到极端值（异常值或离群点）的影响，导致结果失真。在数据集存在极端值或分布不均时，可以结合中位数等其他统计指标进行综合分析。

中位数是指在一组有序数据中处于中间位置的数值，它将数据集分为两个部分，使得其中一半数据的数值小于等于它，另一半数据的数值大于等于它。

对于奇数个数据：如果数据集的数量是奇数，则中位数是排序后处于中间位置的那个数。例如，对于数据集 3,5,7，排序后中位数为 5。

对于偶数个数据：如果数据集的数量是偶数，则中位数是排序后位于中间的两个数中较小的那个数。例如，对于数据集 2,4,6,8，排序后中位数为 4。

题目描述：¶

假设现在有两个长度均为N且元素不重复的有序数组（从小到大）array1和array2，请计算这两个有序数组合并后的中位数。要求：时间复杂度为O(logN)，额外的空间复杂度O(1)，不能使用sort函数。

示例1：输入：

[1.00000, 3.00000, 7.00000],[2.0000, 5.00000, 10.00000]

输出：

3.00000

解题思路：¶

时间复杂度 O(log N)：通过对 array1 进行二分查找，每次将搜索范围减半。
空间复杂度 O(1)：只使用了常数级别的额外空间。
算法思路：
- 二分查找：在 array1 中找到一个分割点 i，使得满足以下条件：
  - Aleft <= Bright 且 Bleft <= Aright，其中：
    - Aleft 是 array1 在分割点左侧的最大值。
    - Aright 是 array1 在分割点右侧的最小值。
    - Bleft 和 Bright 类似。
    - 中位数计算：当找到合适的分割点后，中位数就是左侧部分的最大值，即 max(Aleft, Bleft)。

代码：¶

public float find_median(float[] array1, float[] array2) {
    int N = array1.length;
    int low = 0;
    int high = N;

    while (low <= high) {
        int i = (low + high) / 2;
        int j = N - i;

        float Aleft = (i == 0) ? Float.NEGATIVE_INFINITY : array1[i - 1];
        float Aright = (i == N) ? Float.POSITIVE_INFINITY : array1[i];

        float Bleft = (j == 0) ? Float.NEGATIVE_INFINITY : array2[j - 1];
        float Bright = (j == N) ? Float.POSITIVE_INFINITY : array2[j];

        if (Aleft <= Bright && Bleft <= Aright) {
            return Math.max(Aleft, Bleft);
        } else if (Aleft > Bright) {
            high = i - 1;
        } else {
            low = i + 1;
        }
    }

    throw new IllegalArgumentException("Input arrays are not sorted or have invalid lengths.");
}

第二题¶

题目描述：¶

每个非负整数 N 都有其二进制表示。例如， 6 可以被表示为二进制 "110"，12 可以用二进制 "1100" 表示，依此类推。注意，除 N = 0 外，任何二进制表示中都不含前导零。二进制的反码表示是将每个 1 改为 0 且每个 0 变为 1。例如，二进制数 "101" 的二进制反码为 "010"。给你一个十进制数 N，请你返回其二进制表示的反码所对应的十进制整数。补充说明：提示：2 <= N < 10^8

示例1：输入： 5 输出： 2

示例2：输入： 7 输出： 0

解题思路：¶

算法思路：
- 找到最高位： 计算 N 的二进制表示的位数，即最高位的位置。
- 生成掩码： 创建一个与 N 的二进制位数相同且所有位都为 1 的掩码。
- 计算反码： 将 N 与掩码进行按位异或操作，得到反码对应的十进制整数。
示例解析：
- 输入： 5（二进制 101）
- 最高位数： 3 位
- 掩码： (1 << 3) - 1 = 7（二进制 111）
- 反码： 5 ^ 7 = 2（二进制 010）

代码：¶

 public static int findBinaryComplement(int N) {

        int numBits = Integer.toBinaryString(N).length();

        int mask = (1 << numBits) - 1;

        return N ^ mask;
    }

第三题¶

题目描述¶

小明同学在58集团中秋活动中获得了X积分，这些积分可以用来兑换商品。现有N种不同类型的商品并且每种商品的数量有限。编号为i的商品所需积分为points[i]，对应的数量为counts[i]。如果小明想要恰好用完X积分来兑换商品，最少需要选择多少件商品？如果无法恰好用X积分兑换商品，请返回-1。

补充说明：

数据范围：
1 <= N <= 15
0 <= X <= 1000
0 <= points[i] <= 50
0 <= counts[i] <= 10

示例1：输入：

[2,3,7,11,13],[1,2,3,4,5],30

输出：

说明：

有5件商品，所需积分分别为2，3，7，11，13，数量分别为1、2、3、4、5件，可以购买1件3积分、2件7积分、1件13积分的商品，合计花费3+7+7+13=30积分，总共4件商品

示例2：输入：

[2,3,7,11,13],[1,1,1,4,5],30

输出：

-1

说明：

无法恰好用30积分兑换商品，因此输出-1

解题思路：¶

算法思路：
- 多重背包问题（优化版）： 由于每种商品的数量有限，我们需要解决一个多重背包问题。
- 二进制拆分优化： 为了降低时间复杂度，将物品的数量进行二进制拆分，这样可以将多重背包转换为 0-1 背包的形式，减少循环次数。
实现细节：
- 初始化 DP 数组： dp[s] 表示达到积分 s 所需的最少商品数量，初始时除 dp[0]=0 外，其余位置设置为无穷大（这里使用 Integer.MAX_VALUE / 2 以防止整数溢出）。
- 动态规划更新： 对于每种商品，通过二进制拆分的方式，将其数量转换为若干件商品，每件商品的数量为 c = min(k, count)，价值为 c * points[i]。
  - 内层循环： 从积分 X 递减到当前商品的总积分 totalPoint，更新 dp[s]。
  - 状态转移方程： dp[s] = min(dp[s], dp[s - totalPoint] + c)。
- 结果输出： 如果 dp[X] 仍为初始值，表示无法恰好用完 X 积分，输出 -1，否则输出最少商品数量 dp[X]。
边界条件处理：
- 输入验证： 如果输入格式不正确，直接输出 -1。
- 整数溢出防范： 在初始化 dp 数组时，将无穷大值设为 Integer.MAX_VALUE / 2，以防止加法操作时溢出。

代码：¶

public static int minItems(int[] points, int[] counts, int X) {
        int[] dp = new int[X + 1];
        final int INF = Integer.MAX_VALUE / 2;
        Arrays.fill(dp, INF);
        dp[0] = 0;

        int N = points.length;

        for (int i = 0; i < N; i++) {
            int point = points[i];
            int count = counts[i];
            int k = 1;
            while (count > 0) {
                int c = Math.min(k, count);
                int totalPoint = c * point;
                for (int s = X; s >= totalPoint; s--) {
                    if (dp[s - totalPoint] + c < dp[s]) {
                        dp[s] = dp[s - totalPoint] + c;
                    }
                }
                count -= c;
                k <<= 1;
            }
        }

        return dp[X] == INF ? -1 : dp[X];
    }