秋招面/笔试题目集合——13-创新互联
第一题
标题名称:秋招面/笔试题目集合——13-创新互联
当前网址:http://scyanting.com/article/ddepcc.html
leetcode2141:同时运行 N 台电脑的最长时间
思路:二分答案 + 前缀和
public class 第一题13 {public static long maxRunTime(int n,int[] batteries){Arrays.sort(batteries);
int m = batteries.length;
long[] pre = new long[m + 1];
for (int i = 1;i<= m;i++){pre[i] = pre[i - 1] + batteries[i - 1];
}
long l = 0;
long r = pre[m];
long ans = 0;
while (l<= r){long mid = (l + r) / 2;
if (ok(batteries,pre,n,mid)){ans = mid;
l = mid + 1;
}else {r = mid - 1;
}
}
return ans;
}
private static boolean ok(int[] batteries, long[] pre, int n, long limit) {int l = 0;
int r = batteries.length - 1;
int index = 0;
while (l<= r){int mid = (l + r) / 2;
if (batteries[mid] >= limit){index = mid;
r = mid - 1;
}else {l = mid + 1;
}
}
long sum = pre[index];
int rest = n - (batteries.length - index);
return sum >= rest * limit;
}
}
第二题
思路:位图
public class 第二题13 {public static int[] record(int n, int m, int q, int[][] A, int[][] B) {int size = (n + 31) / 32;
int[][] bitmap = new int[m][size];
for (int i = 0;i< n;i++){for (int j = 0;j< A[i].length;j++){bitmap[A[i][j]][i] |= 1<< (i % 32);
}
}
int[] ans = new int[B.length];
for (int i = 0;i< B.length;i++){int sum = 0;
for (int j = 0;j< size;j++){int count = 0;
for (int k = 0;k< B[i].length;k++){count |= bitmap[B[i][k]][j];
}
sum += countOnes(count);
}
ans[i] = sum;
}
return ans;
}
public static int[] record2(int n, int m, int q, int[][] A, int[][] B) {// n 一共有多少人
// 任何一个实验,需要几个整数,能表示所有人谁出现谁没出现?
int parts = (n + 31) / 32;
// m 0 ~ m -1
// [i] [.........]
int[][] bitMap = new int[m][parts];
for (int i = 0; i< n; i++) {// i 人的编号 : a b c
for (int exp : A[i]) {bitMap[exp][i / 32] |= 1<< (i % 32);
}
}
int[] ans = new int[q];
for (int i = 0; i< q; i++) {// i号查询 : a、c、e,一共有多少去重的人
// a[0] | c[0] | e[0] ->几个1
// a[1] | c[1] | e[1] ->几个1
int all = 0;
for (int j = 0; j< parts; j++) {int status = 0;
for (int exp : B[i]) {status |= bitMap[exp][j];
}
all += countOnes(status);
}
ans[i] = all;
}
return ans;
}
private static int countOnes(int n) {n = (n & 0x55555555) + ((n >>>1) & 0x55555555);
n = (n & 0x33333333) + ((n >>>2) & 0x33333333);
n = (n & 0x0f0f0f0f) + ((n >>>4) & 0x0f0f0f0f);
n = (n & 0x00ff00ff) + ((n >>>8) & 0x00ff00ff);
n = (n & 0x0000ffff) + ((n >>>16) & 0x0000ffff);
return n;
}
}
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
标题名称:秋招面/笔试题目集合——13-创新互联
当前网址:http://scyanting.com/article/ddepcc.html