首页 > 贝壳笔试题解 2020-08-11
头像
cxy229
编辑于 2020-08-11 21:22
+ 关注

贝壳笔试题解 2020-08-11


1. 给个数组,需要移除k个数使得这个数组的最大公因数为1,求k,不存在输出-1。AC

看整个序列的最大公约数是不是1,是1 返回0,不是1返回-1。

import java.util.*;

public class Main20200811001 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int i=0;i<T;i++){
            int N = sc.nextInt();
            int[] arr = new int[N];
            for(int ii=0;ii<N;ii++){
                arr[ii] = sc.nextInt();
            }
            int g = arr[0];
            for(int ii=1;ii<N;ii++){
                g = gcd(arr[ii], g);
                if(g==1){
                    break;
                }
            }
            if(g==1){
                System.out.println(0);
            }else{
                System.out.println(-1);
            }
        }
    }

    public static int gcd(int a, int b){
        if(b==0){
            return a;
        }
        return gcd(b, a%b);
    }
}


2. 求a mod x = b的解的个数。90%
不知道哪里错了。。。
import java.util.*;

public class Main20200811002 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        if(a==b){
            System.out.println("inf");
            return ;
        }
        long t;
        if(a-b>0){
            t = a-b;
        }else{
            t = b-a;
        }
        int ans = 0;
        long k = 1;
        for(;t>k*b && t/k>=1;k++){ // 保证 x>b,x>=1 k越来越大,x越来越小
            if(k>100000000){
                System.out.println("inf");
                return ;
            }
            if(t%k!=0){ // x不是整数
                continue;
            }
            ans++; // x=t/k

        }
        System.out.println(ans);
    }
}


3. 给定矩阵地图,有不可行点。自己选择起点或终点,问最短路径的最大值为多少。AC
遍历起点,对每个起点BFS
import java.util.*;

public class Main20200811003 {
    static int H;
    static int M;
    static int[][] next = {{0,-1}, {-1,0}, {1,0}, {0,1}};
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        H = sc.nextInt();
        M = sc.nextInt();
        sc.nextLine();

        char[][] table = new char[H][M];
        for(int i=0;i<H;i++){
            String line = sc.nextLine();
            table[i] = line.toCharArray();
        }

        int ans = 0;
        for(int x=0;x<H;x++){
            for(int y=0;y<M;y++){
                if(table[x][y]=='.'){
                    int tmp = bfs(x*100+y, table);
                    ans = Math.max(ans, tmp);
                }
            }
        }
        System.out.println(ans);
    }

    public static int bfs(int start, char[][] table){

        int[][] isVis = new int[H][M];

        LinkedList<Integer> pre = new LinkedList<>();
        LinkedList<Integer> cur = new LinkedList<>();

        cur.add(start);
        isVis[start/100][start%100] = 1;
        int ans = -1;
        while(cur.size()>0){
            ans++;
            pre = cur;
            cur = new LinkedList<>();
            for(int pos: pre){
                int x = pos/100;
                int y = pos%100;
                for(int i=0;i<4;i++){
                    int nx = x+next[i][0];
                    int ny = y+next[i][1];
                    if(nx>=0&&nx<H && ny>=0&&ny<M && isVis[nx][ny]==0 && table[nx][ny]=='.'){
                        cur.add(nx*100+ny);
                        isVis[nx][ny]=1;
                    }
                }
            }
        }

        return ans;
    }
}


4. 4个人,每个人有一些音乐,给定所有音乐长度,选择若干首播放,并行播放时,最长结束时间和最短结束时间的差最小为多少。AC
暴力,首先得到每个人的所有播放时间长度,然后4个for循环,可过60%,加剪枝(如果当前时间差大于ans,就跳过)可过100%
import java.util.*;

public class Main20200811004 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] a = new int[4][n];

        for(int i=0;i<4;i++){
            for(int j=0;j<n;j++) {
                a[i][j] = sc.nextInt();
            }
        }
        int[] s0 = gen(a[0],n);
        int[] s1 = gen(a[1],n);
        int[] s2 = gen(a[2],n);
        int[] s3 = gen(a[3],n);
        int ans = Integer.MAX_VALUE;
        int[] d = new int[4];
        for(int i0=0;i0<s0.length;i0++){
            d[0] = s0[i0];
            for(int i1=0;i1<s1.length;i1++){
                d[1] = s1[i1];
                if(Math.abs(d[0]-d[1])>ans){
                    continue;
                }
                for(int i2=0;i2<s2.length;i2++){
                    d[2]= s2[i2];
                    if(Math.abs(d[0]-d[2])>ans){
                        continue;
                    }
                    if(Math.abs(d[1]-d[2])>ans){
                        continue;
                    }
                    for(int i3=0;i3<s3.length;i3++){
                        d[3] = s3[i3];
                        if(Math.abs(d[0]-d[3])>ans){
                            continue;
                        }
                        if(Math.abs(d[1]-d[3])>ans){
                            continue;
                        }
                        if(Math.abs(d[2]-d[3])>ans){
                            continue;
                        }
                        int minD = d[0], maxD = d[0];
                        for(int tt=0;tt<4;tt++){
                            if(d[tt]<minD) minD = d[tt];
                            if(d[tt]>maxD) maxD = d[tt];
                        }

                        int curAns = maxD - minD ;
                        ans = Math.min(ans, curAns);
                    }
                }
            }


        }
        System.out.println(ans);
    }

    
    public static int[] gen(int[] arr, int n){
        ArrayList<Integer> ansl = new ArrayList<>();
        for(int idx=0;idx<n;idx++){
            int curn = ansl.size();
            for(int i=0;i<curn;i++){
                ansl.add(ansl.get(i)+arr[idx]);
            }
            ansl.add(arr[idx]);
        }
        ansl.sort((a,b)->(a-b));
        int[] rst = new int[ansl.size()];
        int len = 0;
        int pre = -1;
        for(int i=0;i<ansl.size();i++){
            int cur = ansl.get(i);
            if(pre==cur){
                continue;
            }else{
                rst[len] = cur;
                pre = cur;
                len++;
            }
        }
        return Arrays.copyOfRange(rst, 0, len);
    }
}


全部评论

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

推荐话题

相关热帖

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

近期精华帖

热门推荐