首页 > 阿里3.15笔试题,通过一道
头像
牛客60048244号
编辑于 2021-03-16 11:37
+ 关注

阿里3.15笔试题,通过一道

阿里

阿里3.15笔试情况:

楼主投的后端开发。

第一题:

  • 给出a,b,c三个数。

  • 现在我们可以通过某种操作,使a,b里头的任意一个二进制位发生翻转,0->1,1->0。

  • 最后我要通过 a | b的形式,使得 a与b或的结果为 c

  • 提问: 我最多要翻转几次?

输入数据:

第一行输入一个数T,告诉你有多少行

第二行至后续行,每一行输入abc,以逗号隔开

每个数最大不超过10的9次方

输入示例:

1
2 6 5

输出:

3

解释:

a = 2  0010
b = 6  0110
c = 5  0101

只需要翻转ab从右往左第二位1两次,最右边1次即可。这也是我做题的思路。

主要就是对c逐位移位,该位置上是0,就判断该位置上ab是0还是1的情况。
0 -》几个1加几次
1 -》都为0才加一次

本题为签到题,不难,很快拿下

第二题:

切割蜡烛;

  • 总共最多切割两次

  • 蜡烛长度为n 厘米,每分钟燃烧1厘米

  • 最多切割n-1厘米,最少1cm

  • 切割任意长度的概率均为 1 / (n-1)

  • 切割完以后,两根蜡烛同时燃烧。

  • 如果蜡烛最后剩下的长度>=2。需要重新像上边一样重新随机切割一次。这次切割以后,不再切割了。并且切割完以后,两根蜡烛同时燃烧。

  • 求总共的蜡烛燃烧的数学期望时间(单位:分钟)

  • 输出浮点数,保留4位精度

输入数据:

就一行,输入长度n,n最大不超过10的4次方

输入示例:

4

输出:

2.0000

思路:

看到10的4次方,直接就想暴力模拟了

1. 第一步new一个长度为n的数组fMinutes,记录第一次预计用时。从i = 1开始递增遍历此数组,i为切割的长度。那么预计用时就是Math.min(i, n-i);

2. 同时记录剩下的长度,这里没想起来用啥好,用了个拼音chazhi数组,chazhi[i] = Math.abs(i-(n-i)) = Math.abs(n-2 * i);

3. 接下来,new一个SMinutes数组,记录第一次加第二次的预计用时(数学期望)。

        -     如果长度剩下2或者1,那么SMinutes[j] = fMinutes[j] + 1,

        -     剩下0,就直接是SMinutes[j] = fMinutes[j]。

        -     剩下长度大于2,这里没想到好的方法,直接暴力了。。。


4. 最后把SMinutes里的元素全加起来,乘以 1 / (n-1)即可

最后两分钟做出来的时候本来挺开心,但是提交的时候一直报运行异常,编译不通过,说我import那里出问题了。。。由于时间所剩无几,也没时间debug了。遂放弃

贴一下我的代码,求大佬指教。由于没有提交成功,也不知道暴力会不会超时。我这个估计得算是O(n²)级别了

import java.io.*;
import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        double n = sc.nextDouble();

        double[] fMinutes = new double[(int)n];
        int[] chazhi = new int[(int)n];//其实就是剩下的长度;
        double[] SMinutes = new double[(int)n];

        for(int i = 1; i<=(n-1); i++){//i代表第一次切割,割的长度
            fMinutes[i] = Math.min(i,n-i);
            chazhi[i] = (int)Math.abs(2*i-n);
        }
        for(int i = 1; i<fMinutes.length; i++){
            if(chazhi[i] == 2 || chazhi[i] == 1)
                SMinutes[i] = fMinutes[i] + 1;
            else if(chazhi[i] == 0){
                SMinutes[i] = fMinutes[i];
            }
            else {
                //长度大于2
                double sum = 0.0;

                for(int j = 1; j<chazhi[i]; j++){
                    sum += Math.max(j,chazhi[i]-j) / (chazhi[i] - 1.0000);
                }
                SMinutes[i] = fMinutes[i] + sum;
            }
        }
        //计算最后的时间
        double ans = 0.0000;
        for(int i = 0; i<SMinutes.length; i++){
            ans += SMinutes[i] / (n - 1.0000);
        }

        String res = String.format("%.4f", ans);
        System.out.println(res);
    }
}

期望有个好结果。冲啊!

全部评论

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

相关热帖

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

近期精华帖

热门推荐