虾皮笔试 Shopee 9.22 笔试

背包容量第一题二分做出来了 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;     }

后端第三题是求一个最小的背包容纳值

这不是力扣上的题吗

有没有大佬能分享下你的第三题怎么做的

 #虾皮笔试# #Shopee#

楼主是什么卷？我做的后端好像题目不一样啊

后端第一题是个什么意思

有多少棵不同的二叉搜索树就是卡特兰数问题 秒了

蹲一个测试成本T T

第一题背包求解 暴力只过了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;     }

第三题优点哈夫曼树的意思。     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;     }

测试成本的理解错了提意，以为矩阵连乘的那种动态规划问题😂

现在虾皮笔试还要自己写输入吗