外观
58同城
约 1663 字大约 6 分钟
2025-02-27
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输出：
4说明：
有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]。
- 初始化 DP 数组：
边界条件处理：
- 输入验证： 如果输入格式不正确，直接输出
-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];
}