虾皮笔试 Shopee 9.22 笔试


求助大佬们第三题:
给定一个整数n,得到一个数组 [1, 2, ...., n],通过这个数组来生成二次搜索树,求最多可以生成多少棵不同的二次搜索树,返回棵树

#Shopee#
全部评论
背包容量第一题二分做出来了 public long Solve(int n, int m, int[] weights) {         // write code here     int max = -1;     long sum = 0;     for (int i = 0; i < weights.length; i++) {         if(weights[i]>max){             max = weights[i];         }         sum += weights[i];     }     long start =  Math.max(max,sum/m);     long end = sum;     long mid = (start+end)/2;     while(start<end){         mid = (start+end)/2;         if(canHave(m,n,weights,mid)){             end = mid;         }else{             start = mid + 1;mid = mid + 1;             }}     return  mid;     }     private boolean canHave(int m,int n,int[] weights,long k){         int leftNum = m-1;long leftWeight = k;         for (int j = 0; j < weights.length; j++) {             if(leftWeight>= weights[j]){                 leftWeight -= weights[j];             }else{                 leftNum--;leftWeight = k;leftWeight -= weights[j];             }         }         if(leftNum>=0){return true;}         return false;     }
2 回复
分享
发布于 2021-09-22 19:04
后端第三题是求一个最小的背包容纳值
1 回复
分享
发布于 2021-09-22 16:39
淘天集团
校招火热招聘中
官网直投
这不是力扣上的题吗
1 回复
分享
发布于 2021-09-22 21:11
有没有大佬能分享下你的第三题怎么做的
1 回复
分享
发布于 2021-09-22 16:35
楼主是什么卷?我做的后端好像题目不一样啊
点赞 回复
分享
发布于 2021-09-22 16:36
后端第一题是个什么意思
点赞 回复
分享
发布于 2021-09-22 16:46
有多少棵不同的二叉搜索树就是卡特兰数问题 秒了
点赞 回复
分享
发布于 2021-09-22 17:04
蹲一个测试成本T T
点赞 回复
分享
发布于 2021-09-22 17:06
第一题背包求解 暴力只过了0.3      public long Solve(int n, int m, int[] weights) {         long min = 0;         long max = 0;         for(int i=0;i<n;i++){             min+=weights[i];             if(weights[i]>max)              max = weights[i];         }         if(min%m!=0)         min=(long)(min/m)+1;         else min = min/m;                  min=Math.max(min, max);                  while(beibao(min,n,m,weights)==false) {          System.out.println(min);          min++;         }                           return min;     }     public boolean beibao(long min,int n,int m,int[] weights) {      int t = m-1;         //t是指还剩几个背包         long k = 0;         //k指当前背包装了多少东西      for(int i=0;i<n;++i) {      if(k+weights[i]<=min && t>=0) {      k+=weights[i];      continue;      }else if(t>0) {      //当前背包装不下第i个,换个新背包装第i个,且最少有一个新背包      --t;      k=weights[i];      }      else{      //所有背包都用完,t=0      //还没有跳出循环,即还有石头没装下      return false;      }      }      return true;     }
1 回复
分享
发布于 2021-09-22 17:07
第三题优点哈夫曼树的意思。     public int minEffort(ArrayList<Integer> cases) {         // write code here         PriorityQueue<Integer> minHeap = new PriorityQueue<>(new Comparator<Integer>() {             @Override             public int compare(Integer o1, Integer o2) {                 return o1-o2;             }         });         int result = 0;         minHeap.addAll(cases);         while(minHeap.size()>1){             int x1 = minHeap.poll();             int x2 = minHeap.poll();             result += x1;             result += x2;             minHeap.add(x1+x2);         }         return result;     }
1 回复
分享
发布于 2021-09-22 19:04
测试成本的理解错了提意,以为矩阵连乘的那种动态规划问题😂
点赞 回复
分享
发布于 2021-09-22 19:05
现在虾皮笔试还要自己写输入吗
点赞 回复
分享
发布于 2022-03-01 19:07

相关推荐

8 3 评论
分享
牛客网
牛客企业服务