2021.09.22 虾皮 笔试 Shopee 笔试统计

第一第三题a了（都是暴力a），第二题动态规划属实做不来，a了10%溜了溜了，希望能进面

第一题是什么意思？不是排序依次求和嘛？怎么就过了10%😥

感觉这题目比较容易啊，大家AC率都好高

第二题真的是区间dp吗？，，，我只过了10%，怎么检查都检查不出错误

字符串编辑距离 public int dynamic(String command,String input) { int dp[][] = new int [command.length()+1][input.length()+1]; dp[0][0]=0; int i,j; for(i=1;i<=command.length();i++) { dp[i][0]=i; } for(j=1;j<=input.length();j++) { dp[0][j]=j; } int f; for(i=1;i<=command.length();i++) { for(j=1;j<=input.length();j++) { if(command.charAt(i-1)==input.charAt(j-1)) f=0; else f=1; dp[i][j]=Math.min(dp[i][j-1]+1, Math.min(dp[i-1][j]+1, dp[i-1][j-1]+ f)); } } return dp[command.length()-1][input.length()-1]; }     public String didYouMean(String[] commands, String input) {         // write code here           int n[] = new int[commands.length];      int min = 65535;      int mini=0;           for(int i=0;i<commands.length;i++) {      n[i]=dynamic(commands[i],input);      if(n[i]<min) {      min=n[i];      mini=i;      }      }      return commands[mini];     }

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

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