阿里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

输出：

解释：

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次方

输入示例：

输出:

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

期望有个好结果。冲啊！

#阿里巴巴##Java工程师##实习##笔试题目##题解##笔经#