2021暑期实习京东4.24笔试题目(技术运维岗)

考试情况:
时间:19:00---21:00
平台:赛码
选择题:30道,涉及计算机网络、Linux基础(大量)、mysql数据库、数据结构(连通图……)读程序
算法题:2道,可以在本地IDE调试,难度适中。


1、超大整数转字符串处理问题
A随手写出了一个正整数n。他可以对这个数字做出如下操作: 1、 把这个数字除以一个数,且保证结果是大于1的正整数; 2、 把这个数字减去1。 
小A想知道通过如上操作把这个数变成1的最小操作次数。 输入:第一行有1个正整数T,表示数据的组数; 接下来T行,每行有1个正整数n,含义如题。  1 ≤ T ≤ 100001 ≤ n ≤ 10的18次方输出:输出T行,每行1个整数,表示题目所求的最小操作次数。 输入:2 
      1
      4 输出:0 
      2 
思路1:开始采用动态规划思想,但是只能通过36%,问题出现在对于每次输入的n要自底向上逐个值进行计算,我最初分析可能是时间复杂度过高,改用思路2递归求解。
public class First {
    public static final int INT_MAX=0X7FFFFFFA;
    public static void main(String[] args) {
        Scanner cin=new Scanner(System.in);
        int t=cin.nextInt();
        int n;
        while (t-->0){
            n=cin.nextInt();
            int[]res=new int[n+1];
            res[1]=0;
            if(n==1){
                System.out.println(0);
            }
            else{
                res[2]=1;
                for(int i=3;i<=n;i++){
                    int yueshu=yueshu(i);
                    if(yueshu>=INT_MAX){
                        res[i]=res[i-1]+1;
                    }
                    else{
                        res[i]=Math.min(res[i-1],res[i/yueshu])+1;
                    }
                }

            }
            for(int j=1;j<=n;j++){
                System.out.println("j="+j+"  值:"+res[j]);
            }
        }
    }

    private static int yueshu(int n) {
        for(int i=n-1;i>1;i--)
        {
            if(n%i==0&&n/i>1)
            {
                return i;
            }
        }
        return INT_MAX;
    }
}
思路2:对于输入的n,只需要递归去算n,n/(最大约数),根据奇偶最多也就2次或3次即可得到结果,相比于上面计算n次有了大大的提升,但是结果还是通过36%。认真分析后采用了思路3
public class second {
    public static final int INT_MAX=0X7FFFFFFA;
    public static void main(String[] args) {
        Scanner cin=new Scanner(System.in);
        int t=cin.nextInt();
        int n;
        while (t-->0){
            n=cin.nextInt();
            int res=getnum(n);
            System.out.println(res);
        }
    }
    private static int getnum(int n){
        if(n<=1)
            return 0;
        if(n==2)
            return 1;
        if(yueshu(n)>=INT_MAX){
            return getnum(n-1)+1;
        }
        else{
            return Math.min(getnum(n-1),getnum(n/yueshu(n)))+1;
        }


    }
    private static int yueshu(int n) {
        for(int i=n-1;i>1;i--)
        {
            if(n%i==0)
            {
                return i;
            }
        }
        return INT_MAX;
    }
}
思路3:通过思路2 的尝试我们发现结果有一定的规律性,对于奇数n我们需要计算3次(n=n-1,n除以约束降到2,2-1)对于偶数n只需要执行后面2步即可,所以对于前面特殊情况特殊处理外,后面只需要判断奇偶数进行输出3、2就可以了。因为时间原因,代码比较粗糙,匆匆的改了下,交上去100%,就去做了第二题,但是基本的思想已经在里面了,后面可以自己优化。
核心思想:
1 ≤ n ≤ 10的18次方
对于超长的输入采用字符串进行读取处理 ,取最后以为判断奇偶进行输出,如果有其它处理大数方法请多多指教。
public class four {
    public static void main(String[] args) {
        Scanner cin=new Scanner(System.in);
        int t=cin.nextInt();
        int n;
        String str;
        while (t-->0){
            str=cin.next();
            int res;
            if(str.length()<2){
                n=Integer.parseInt(str);
                if(n==1)
                    res=0;
                else if(n==2)
                    res=1;
                else if(n==3)
                    res=2;
                else if(n==4)
                    res=2;
                else{
                    if(n%2==0)
                    {
                        res=2;
                    }
                    else {
                        res=3;
                    }
                }
            }
            else{
                int len=str.length();
                char c=str.charAt(len-1);
                if(c=='2'||c=='0'||c=='4'||c=='6'||c=='8'){
                    res=2;
                }
                else{
                    res=3;
                }
            }

            System.out.println(res);
        }
    }
}
题目2:
在长度为n的数组上进行查找连续长度为k的区间内和的最大值,最后返回最大值区间的中间位置下标
输入:10 3 
    5 5 5 10 10 10 5 10 10 10
    代表n=10 k=3,后面是输入的n个数
输出:5
    代表下标为4 5 6 三个元素的和最大为30(注意题目要求若符合区域有多个,取较前的),中间下标=5
    

因为时间问题,采用暴力搜索的策略
public class NOtwo {
    public static void main(String[] args) {
        int n,k;
        Scanner cin=new Scanner(System.in);
        n=cin.nextInt();
        k=cin.nextInt();
        ArrayList<Integer> list = new ArrayList<>();
        for(int i=0;i<n;i++){
            list.add(cin.nextInt());
        }

        int maxsum=0;
        int index=0;
        for(int i=0;i+k<=n;i++){
            int sum=0;
            int j;
            for(j=0;j<k;j++){
                sum+=list.get(i+j);
            }
            if(sum>maxsum)
            {

                index=i+(j/2)+1;
                maxsum=sum;
            }
        }
        System.out.println(index);
    }
}

最后过了78%,请大佬指教……




#京东##笔经##运维工程师#
全部评论
我第一题,最后10分钟想起来的,直接判断字符串长度和最后一个字符就行了。😂
点赞 回复
分享
发布于 2021-04-24 21:44

相关推荐

3 10 评论
分享
牛客网
牛客企业服务