小米 20240919 算法笔试
1.单选 25*2
2.多选 6 * 2
3.编程题
1)(18)有一个容量为 N 的箱子,希望能够把一些玩具和填充物放入箱子,要求刚好填满。玩具有不同的大小和数量,同时还有体积为 1 的填充物。希望能够通过选择玩具和适当数量的填充物刚好装满箱子。
2)(20)通过在两个数组相应位置交换,最终目的是判断能否将其中一个数组变为非递减或非递增的序列
2.多选 6 * 2
3.编程题
1)(18)有一个容量为 N 的箱子,希望能够把一些玩具和填充物放入箱子,要求刚好填满。玩具有不同的大小和数量,同时还有体积为 1 的填充物。希望能够通过选择玩具和适当数量的填充物刚好装满箱子。
2)(20)通过在两个数组相应位置交换,最终目的是判断能否将其中一个数组变为非递减或非递增的序列
全部评论
不知道为什么第一题卡在18%了
第一题和分割等和子集做法一样 第二题完全不会
第一道换了好几种写法只过了百分之十八,第二道完全不会,心态炸裂
第二题暴力列举组合,然后判定排序😅
第一题:用一个数组收录所有的玩具,并且有几个填充物就push进去几个1,然后就是经典0-1背包;
第二题:贪心。先尝试让a变成递增的,如果没做出来就再尝试让a变成递减的。为了让a尽可能的递增,那么a的每个元素递增的程度就要尽可能的低,比如1 2 3就要比1 5 9递增的程度低,对于每个下标i,找出a和b的最大值和最小值来判断,尽可能让最小值作为a的元素。
我测,你是真快啊
第一题排序后按滑动窗口做的 只过了55%不知道为啥 有大佬讲讲嘛
第一题搞了好久就才100%,第二题18%,后面想改没时间了
第一题数据就读不对,光读数据提交就会运行错误
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
while (T>0){
T--;
int n = in.nextInt();
int[] a = new int[n];
int[] b = new int[n];
for (int i = 0; i < n; i++) {
a[i] = in.nextInt();
}
for (int i = 0; i < n; i++) {
b[i] = in.nextInt();
}
int k = 0;
int preNum = -1;
boolean flag = true;
//尝试升序
while(k<n){
if(a[k]<preNum && b[k]<preNum){
flag = false;
break;
}
if(a[k]<b[k]){
if(a[k]>=preNum){
preNum = a[k];
}else{
preNum = b[k];
}
}else {
if(b[k]>=preNum){
preNum = b[k];
}else {
preNum = a[k];
}
}
k++;
}
if (flag){
System.out.println("YES");
continue;
}else{
//尝试降序
flag = true;
preNum = Integer.MAX_VALUE;
k=0;
while(k<n){
if(a[k]>preNum && b[k]>preNum){
flag = false;
break;
}
if(a[k]>b[k]){
if(a[k]<=preNum){
preNum = a[k];
}else{
preNum = b[k];
}
}else {
if(b[k]<=preNum){
preNum = b[k];
}else {
preNum = a[k];
}
}
k++;
}
if(flag){
System.out.println("YES");
}else{
System.out.println("NO");
}
}
}
}
public static void main1(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
while (t>0){
t--;
int N,n,c;
N = in.nextInt();
n = in.nextInt();
c = in.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = in.nextInt();
}
if(dfs(a,0,c,N)) System.out.println("YES");
else System.out.println("NO");
}
}
static boolean dfs(int[] a,int index,int c,int res){
if(res<=c) return true;
if(index>=a.length) return false;
boolean flag = false;
if(res>= a[index]){
flag = dfs(a,index+1,c,res-a[index]);
}
if(flag) return flag;
flag = dfs(a,index+1,c,res);
return flag;
}
static boolean dfs(int[] a,int index,int c,int res){
if(res<=c) return true;
if(index>=a.length) return false;
boolean flag = false;
if(res>= a[index]){
flag = dfs(a,index+1,c,res-a[index]);
}
if(flag) return flag;
flag = dfs(a,index+1,c,res);
return flag;
}
两个都直接dfs做了
这个要大约多少分能通过啊
为啥我的多选只有一题?
笔试限时多长时间呀?
相关推荐
09-27 18:15
华东理工大学 数据运营 点赞 评论 收藏
分享