首页 > 20200905搜狗后端笔试题
头像
neebie
编辑于 2020-09-05 20:11
+ 关注

20200905搜狗后端笔试题

代码都有优化的空间,不喜勿喷~
1.二分法:
public int numberofprize (int a, int b, int c) {
        // write code here
        int left=min(a,b,c);
        int right=max(a,b,c);
        while (left<=right){
            int mid=left+(right-left)/2;
            if (check(mid,a,b,c)){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return right;
    }

    private boolean check(int mid, int a, int b, int c) {
        long left=0;
        if (a>=mid){
            left+=(a-mid);
        }else {
            left-=(2*(mid-a));
        }
        if (b>=mid){
            left+=(b-mid);
        }else {
            left-=(2*(mid-b));
        }
        if (c>mid){
            left+=(c-mid);
        }else {
            left-=(2*(mid-c));
        }
        return left>=0;
    }

    private int min(int a, int b, int c) {
        return Math.min(Math.min(a,b),c);
    }
    private int max(int a, int b, int c) {
        return Math.max(Math.max(a,b),c);
    }
2. 数组模拟,注意转换成浮点数计算
public int getHouses (int t, int[] xa) {
        // write code here
        if (xa==null||xa.length==0)
            return 0;
        double[][] xAndA=new double[xa.length/2][2];
        int idx=0;
        for (int i = 0; i < xa.length; i+=2) {
            xAndA[idx][0]=(double)xa[i]-(double) xa[i+1]/2;
            xAndA[idx][1]=(double)xa[i]+(double) xa[i+1]/2;
            idx++;
        }
        int count=2;
        for (int i = 0; i < xAndA.length-1; i++) {
            if ((xAndA[i+1][0]-xAndA[i][1])==t){
                count++;
            }else if  ((xAndA[i+1][0]-xAndA[i][1])>t){
                count+=2;
            }
        }
        return count;
    }

3. 回溯(80%)
public long getPasswordCount (String password) {
        // write code here
        if (password.length()==1)
            return 9;
        int i[]=new int[1];
        Deque<Character> stack=new ArrayDeque<>();
        backTrack(password.toCharArray(),0,i,stack);
        return i[0];
    }

    private void backTrack(char[] chars, int start, int[] i, Deque<Character> stack) {
        if (stack.size()==chars.length){
            if (!checkEquals(stack,chars)){
                i[0]++;
            }
            return;
        }
        if (start==0){
            for (int j = 0; j <=9; j++) {
                stack.addLast((char)('0'+(j-0)));
                backTrack(chars,start+1,i,stack);
                stack.pollLast();
            }
        }else{
            int cur=((chars[start]-'0')+(stack.peekLast()-'0'));
            if (cur%2==0){
                stack.addLast((char)('0'+(cur/2-0)));
                backTrack(chars,start+1,i,stack);
                stack.pollLast();
            }else{
                for (int j = 0; j < 2; j++) {
                    stack.addLast((char)('0'+(cur/2+j-0)));
                    backTrack(chars,start+1,i,stack);
                    stack.pollLast();
                }
            }
        }

    }

    private boolean checkEquals(Deque<Character> stack, char[] chars) {
        int idx=0;
        for (Character c:stack){
            if (c!=chars[idx++])
                return false;
        }
        return true;
    }


全部评论

(7) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐