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;
    }


#搜狗##笔试题目#
全部评论
第一题,这样的思路行不行的通?类似贪心,三个数放进数组num,然后排序,第一次直接加num[0], 另外两个数先减去,然后第二个数和第三个数num[1]、num[2]减去num[0],这样就剩后面两个了,这时候兑换情况就是,两个num[1]、两个num[2]可以兑换,num[1]兑换完了以后,最后兑换num[2],这时候需要5张num[2]兑换。其中需要处理的就是num[0]兑换完后num[1]的奇偶性处理一下就行了。
点赞 回复 分享
发布于 2020-09-06 10:36
第一题check方法是什么意思呀
点赞 回复 分享
发布于 2020-09-05 22:31
大佬,我感觉我和你第二题思路比较像,但是我为什么只过了0.4;大佬能不能帮我分析下???
点赞 回复 分享
发布于 2020-09-05 20:52
楼主能说下第一题的思路吗
点赞 回复 分享
发布于 2020-09-05 20:49
牛批,第一题终于看懂了
点赞 回复 分享
发布于 2020-09-05 20:47
膜拜大佬
点赞 回复 分享
发布于 2020-09-05 20:38
厉害了大佬
点赞 回复 分享
发布于 2020-09-05 20:33

相关推荐

不愿透露姓名的神秘牛友
06-29 17:30
点赞 评论 收藏
分享
点赞 评论 收藏
分享
ohs的小木屋:比不少实习待遇高了
点赞 评论 收藏
分享
评论
6
10
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务