搜狗9.5笔试 100 100 70

第一题 AC100 做法有点笨😂

    public int numberofprize (int a, int b, int c) {
        // write code here
        int res = Math.min(a,Math.min(b,c));
                //手动模拟
        while(Math.min(a,Math.min(b,c)) >= res){
            //第一次减，从最大的数减1
            if (a >= b && a >= c){
                a--;
            }else if(b >= a && b >= c){
                b--;
            }else if(c >= a && c >= b){
                c--;
            }
            //第二次减
            if (a >= b && a >= c){
                if (b > c){//从最大的数减1，最小的数加1
                    a--;
                    c++;
                }else{
                    a--;
                    b++;
                }
            }else if(b >= a && b >= c){
                if (a > c){
                    b--;
                    c++;
                }else{
                    b--;
                    a++;
                }
            }else if(c >= a && c >= b){
                if (b > a){
                    c--;
                    a++;
                }else{
                    c--;
                    b++;
                }
            }
            res = Math.max(res,Math.min(a,Math.min(b,c)));
        }
        return res;
    }

第二题 AC100

        public int getHouses (int t, int[] xa) {
        // write code here
        int res = 2;

        double[] right = new double[xa.length/2];//每个房子右边界
        double[] left = new double[xa.length/2];//每个房子左边界
        int index = 0;
        for (int i = 0; i < xa.length; i++) {
            if(i % 2 == 0){
                left[index] =xa[i] - (double)xa[i+1]/2;
                right[index] = xa[i] + (double)xa[i+1]/2;
                index++;
            }
        }

        for (int i = 0; i < xa.length / 2 - 1; i++) {
            if(left[i] + t < right[i+1]){//放下房子后还有空，可以靠左和靠右
                res+=2;
            }else if(left[i] + t == right[i+1]){//放下房子没空了，只有一种情况
                res++;
            }
        }

        return res;
    }

第三题 AC70 复杂度太高了

    //回溯，结果存在set中去重

        Set<String> set = new HashSet<>();
    public long getPasswordCount (String password) {
        // write code here
        int n = password.length();
        set.add(password);

        for (int i = 0; i <= 9; i++) {
            StringBuilder sb = new StringBuilder();
            sb.append(i);
            backtrack(password,1,sb,i);
        }

        return set.size()-1;
    }

    public void backtrack(String password,int i,StringBuilder sb,double pre){
        if(i == password.length()){
            set.add(sb.toString());
            return;
        }
        int cur = Integer.valueOf(password.charAt(i)-'0');
        double newNum = (pre + cur) / 2;

        int num =(int) newNum;

        sb.append(num);
        backtrack(password,i+1,sb,num);
        sb.deleteCharAt(sb.length()-1);

        if(newNum > num){
            sb.append(num+1);
            backtrack(password,i+1,sb,num+1);
            sb.deleteCharAt(sb.length()-1);
        }
    }

#笔试题目##搜狗#