2017校招全国统一模拟笔试第一场-编程题（8题）-牛客网（java）

逃离我推掉我的手 2022-10-01 00:51 198阅读 0赞

# 1、好多鱼 #

## 牛牛有一个鱼缸。鱼缸里面已经有n条鱼，每条鱼的大小为fishSize\[i\] (1 ≤ i ≤ n,均为正整数)，牛牛现在想把新捕捉的鱼放入鱼缸。鱼缸内存在着大鱼吃小鱼的定律。经过观察，牛牛发现一条鱼A的大小为另外一条鱼B大小的2倍到10倍(包括2倍大小和10倍大小)，鱼A会吃掉鱼B。考虑到这个，牛牛要放入的鱼就需要保证： ##

## 1、放进去的鱼是安全的，不会被其他鱼吃掉 ##

## 2、这条鱼放进去也不能吃掉其他鱼 ##

## 鱼缸里面已经存在的鱼已经相处了很久，不考虑他们互相捕食。现在知道新放入鱼的大小范围minSize,maxSize,牛牛想知道有多少种大小的鱼可以放入这个鱼缸。 ##

### 输入描述: ###

输入数据包括3行.  
第一行为新放入鱼的尺寸范围minSize,maxSize(1 ≤ minSize,maxSize ≤ 1000)，以空格分隔。

第二行为鱼缸里面已经有鱼的数量n(1 ≤ n ≤ 50)

第三行为已经有的鱼的大小fishSize\[i\](1 ≤ fishSize\[i\] ≤ 1000)，以空格分隔。

### 输出描述: ###

输出有多少种大小的鱼可以放入这个鱼缸。考虑鱼的大小都是整数表示

输入例子:  
1 12  
1  
1

输出例子:  
3

## 答案： ##

import java.util.Scanner;
    
    public class Main {
    
        public static void main(String[] args){
    
            Scanner scanner = new Scanner(System.in);//接收输入的参数
            int minSize = scanner.nextInt();//新放入鱼的最小范围
            int maxSize = scanner.nextInt();//新放入鱼的最大范围
            int n = scanner.nextInt();//鱼缸中原有的鱼数
            int[] fishSize = new int[n];
            for(int k=0;k<n;k++){
                fishSize[k] = scanner.nextInt();//原有鱼的大小
            }
            int canPut = 0;//鱼缸中可以放入鱼的种类
            for(int i=minSize;i<=maxSize;i++){
                boolean willBeEaten = false;//定义一个标记，记录鱼是否被吃,i为放入鱼缸的鱼的尺寸
                for(int j=0;j<n;j++){
                   if((10*i>=fishSize[j] && 2*i<=fishSize[j])||                                     (10*fishSize[j]>=i && 2*fishSize[j]<=i))
                   {
                        willBeEaten = true;
                        break;//此大小的鱼被吃，之后的鱼都不会符合要求
                    }
                }
                if(!willBeEaten)
                    canPut++;
             }
            System.out.println(canPut);
            scanner.close();
    
        }
    
    }

# 2、 循环单词 #

## 如果一个单词通过循环右移获得的单词，我们称这些单词都为一种循环单词。 例如：picture 和 turepic 就是属于同一种循环单词。 现在给出n个单词，需要统计这个n个单词中有多少种循环单词。 ##

### 输入描述: ###

输入包括n+1行：

第一行为单词个数n(1 ≤ n ≤ 50)

接下来的n行，每行一个单词word\[i\]，长度length(1 ≤ length ≤ 50)。由小写字母构成

### 输出描述: ###

输出循环单词的种数

输入例子:  
5  
picture  
turepic  
icturep  
word  
ordw

输出例子:  
2

## 答案： ##

/*思路：把要测试的单词后再重复下这个单词，如：picture ，变成 picturepicture
    然后判断其他要测试的单词是不是这个串的子串（长度要先相等）*/
    
    import java.util.LinkedList;
    import java.util.Scanner;
    
    public class Main {
          public static void main(String[] args){
                Scanner sc = new Scanner(System.in);
                int n = sc.nextInt();
                LinkedList<String> list = new LinkedList<String>();
                int count = 0;
                for(int i = 0;i<n;i++)
                {
                    String s = sc.next();//输入并存储每行的单词。此处必须调用next（）方法，不能是nextLine（）方法
                    if(!list.contains(s)){
                        count++;
                        list.add(s);
                    }
                    for(int j = 1;j<s.length();j++){
                        StringBuilder string = new StringBuilder();
                        string.append(s);
                        string.append(s);
                        String s1 = string.substring(j,j+s.length());//获取子串
    
                        list.add(s1);
                    }
                }
    
                sc.close();
                System.out.println(count);
            }
        }

substring用法：  
“hamburger”.substring(4, 8) returns “urge”  
“smiles”.substring(1, 5) returns “mile”

# 3、 DNA合成 #

## DNA分子是以4种脱氧核苷酸为单位连接而成的长链，这4种脱氧核苷酸分别含有A,T,C,G四种碱基。碱基互补配对原则：A和T是配对的，C和G是配对的。如果两条碱基链长度是相同的并且每个位置的碱基是配对的，那么他们就可以配对合成为DNA的双螺旋结构。现在给出两条碱基链，允许在其中一条上做替换操作：把序列上的某个位置的碱基更换为另外一种碱基。问最少需要多少次让两条碱基链配对成功 ##

### 输入描述: ###

输入包括一行：  
包括两个字符串,分别表示两条链,两个字符串长度相同且长度均小于等于50。

### 输出描述: ###

输出一个整数，即最少需要多少次让两条碱基链配对成功

输入例子:  
ACGT TGCA

输出例子:  
0

## 答案： ##

//思路：逐个判断是否配对，不配对的个数就是需要的次数
    import java.util.Scanner;
    public class DNA {
       public static void main(String[] args){
           Scanner sn=new Scanner(System.in);
    
               String str1 = sn.next();
               String str2 = sn.next();
    
               int count=0;
               for(int i=0;i<str1.length();i++){
    
                   if(str1.charAt(i)=='A' && str2.charAt(i)=='T')
                       continue;
                   else if(str1.charAt(i)=='T' && str2.charAt(i)=='A')
                       continue;
                   else if(str1.charAt(i)=='C' && str2.charAt(i)=='G')
                       continue;
                   else if(str1.charAt(i)=='G' && str2.charAt(i)=='C')
                       continue;
                   else 
                       count++;
                }
    
           sn.close();
           System.out.println(count);
       }
    }

# 4、 连续整数 #

## 牛牛的好朋友羊羊在纸上写了n+1个整数，羊羊接着抹除掉了一个整数，给牛牛猜他抹除掉的数字是什么。牛牛知道羊羊写的整数神排序之后是一串连续的正整数，牛牛现在要猜出所有可能是抹除掉的整数。例如： ##

## 10 7 12 8 11 那么抹除掉的整数只可能是9 ##

## 5 6 7 8 那么抹除掉的整数可能是4也可能是9 ##

### 输入描述: ###

输入包括2行：

第一行为整数n(1 <= n <= 50)，即抹除一个数之后剩下的数字个数

第二行为n个整数num\[i\] (1 <= num\[i\] <= 1000000000)

### 输出描述: ###

在一行中输出所有可能是抹除掉的数,从小到大输出,用空格分割,行末无空格。如果没有可能的数，则输出mistake

输入例子:  
2  
3 6

输出例子:  
mistake

## 答案： ##

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    import java.util.Scanner;
    
    public class Lianxu_zhengshu {
    
            public static void main(String[] args) {
                Scanner scanner = new Scanner(System.in);
    
                int n = scanner.nextInt();
                int[] num = new int[n];
    
                for (int i = 0; i < n; i++) 
                {
                    num[i] = scanner.nextInt();
                }
                 scanner.close();
    
                //第一步，先排序
                Arrays.sort(num);//排序
                List<Integer> list = new ArrayList<>();
    
                int flag = 0;
                //第二步，判断中间间隔几个数，如果是大于2，就输出mistake,如果等于2，就将flag++
                for (int i = 1; i < num.length; i++) 
                {
                    if (num[i] - num[i - 1] > 2)
                    {
                        System.out.print("mistake");
                        return;
                    } 
                    else if (num[i] - num[i - 1] == 2)
                    {
                        list.add(num[i - 1] + 1);
                        flag++;
                    }
                }
    
                /*第三步，判断flag的状态
               1） 如果数组中间不缺即flag=0，就判断让第一个元素与1相比，大于1就在前面后面都放入集合，否则就只在后面加;
                2）如果flag>=2,说明连续整数中间不只是却一个，与题意不符，也报错 */  
    
                if (flag == 0) 
                {
                    if(num[0] > 1)
                    {
                        list.add(num[0] - 1);
                     }
                    list.add(num[n - 1] + 1);
                }
                else if (flag >= 2) 
                {
                    System.out.print("mistake");
                    return;
                }
    
               // 第四步，list.get(i)输出集合里的元素，用空格分割,行末无空格
    
                for (int i = 0; i < list.size(); i++) 
                {
                    System.out.print(list.get(i));
                    if (i < list.size() - 1)
                    {
                        System.out.print(" ");
                    }
                }
            }
        }

# 5、超级素数幂 #

## 如果一个数字能表示为p^q(^表示幂运算)且p为一个素数,q为大于1的正整数就称这个数叫做超级素数幂。现在给出一个正整数n,如果n是一个超级素数幂需要找出对应的p,q。 ##

### 输入描述: ###

输入一个正整数n(2 ≤ n ≤ 10^18)

### 输出描述: ###

如果n是一个超级素数幂则输出p,q,以空格分隔,行末无空格。  
如果n不是超级素数幂，则输出No

输入例子:  
27

输出例子:  
3 3

## 答案 ##

public class zhishu_5 {
        public static void main(String[] args) {
            Scanner scanner=new Scanner(System.in);
            long num=scanner.nextLong();
            scanner.close();
            boolean b=false;
            double p;
    
            for (long q=2; q*q<=num; q++) 
            {
                //为何这里是 q*q<=num？
                p=Math.pow(num, 1d/q);//pow(a,b)表示a的b次幂；
                if ((long)p==p&&isPrim((long)p) )
                    //(long)p == p 判断p经过 Math.pow((double) num, 1d/q)后是否为整数
                {
                    System.out.println((long)p+" "+q);
                    b=true;
                    break;
                }
    
            }
    
            if(!b){
                System.out.println("no!");
            }
        }
    
        private static boolean isPrim(long n) {
            if(n<=1){
       return false;}
    
            for (int i=2; i*i<=n; i++) 
                /*这里写成i*i<=n,是因为如果n不是素数那就可以写成n=a*b;
                其中a和b必定一个大于n的算术根，一个小于n的算术平方根，或者就等于n的算术平方根*/
               {
                    if(n%i==0){
                        return false;
                    }
                }
    
            return true;
        }
    
    }

# 6、序列和 #

## 给出一个正整数N和长度L，找出一段长度大于等于L的连续非负整数，他们的和恰好为N。答案可能有多个，我们需要找出长度最小的那个。 ##

## 例如 N = 18 L = 2： ##

## 5 + 6 + 7 = 18 ##

## 3 + 4 + 5 + 6 = 18 ##

## 都是满足要求的，但是我们输出更短的 5 6 7 ##

### 输入描述: ###

输入数据包括一行：  
两个正整数N(1 ≤ N ≤ 1000000000),L(2 ≤ L ≤ 100)

### 输出描述: ###

从小到大输出这段连续非负整数，以空格分隔，行末无空格。如果没有这样的序列或者找出的序列长度大于100，则输出No

输入例子:  
18 2

输出例子:  
5 6 7

## 答案： ##

![这里写图片描述][SouthEast]

public class xuliehe_6 {
    
         public static void main(String args[]){
                Scanner sc = new Scanner(System.in);
                int N = sc.nextInt();
                int L = sc.nextInt();
                for(int i = L; i <= 100; i++) {
                    if((2*N+i-i*i)%(2*i) == 0) {
                        int start = (2*N+i-i*i)/(2*i);
                        for(int j = 0; j < i-1; j++) {
                            System.out.print(start+j+" ");
                        }
                        System.out.print(start+i-1);
                        return;
                    }
                }
                System.out.print("No");
            }
        }

return 指令一个作用是返回一个指定数据给主调函数，

另外的一个作用就是结束所在函数的执行

如果将上述代码中的return改为break,那么还会输出“No”。

# 7、页码统计 #

## 牛牛新买了一本算法书，算法书一共有n页，页码从1到n。牛牛于是想了一个算法题目：在这本算法书页码中0~9每个数字分别出现了多少次？ ##

### 输入描述: ###

输入包括一个整数n(1 ≤ n ≤ 1,000,000,000)

### 输出描述: ###

输出包括一行10个整数，即0~9这些数字在页码中出现的次数，以空格分隔。行末无空格。

输入例子:  
999

输出例子:  
189 300 300 300 300 300 300 300 300 300

## 答案： ##

//问题是在这本算法书页码中0~9每个数字分别出现了多少次?而不是包含0-9的页码分别有多少页？
    //如1 2 3 4 5 6 7 8 9 10 11 12 这里面1共出现了5次
    import java.util.Scanner;
    
    public class yematongji_7_self {
        public static void main(String[] args) {
            Scanner scanner=new Scanner(System.in);
            int n=scanner.nextInt();
            String s="0123456789";
            int num[]=new int[10];
            for (int i =1; i <=n; i++) {
                char c[]=new String(i+"").toCharArray();
                for (int j = 0; j < c.length; j++) {
                    num[s.indexOf(c[j])]+=1;
                    //点睛之笔
                }
    
            }
            for (int k = 0; k < 9; k++) {
                System.out.print(num[k]+" ");
            }
            System.out.println(num[9]);
            scanner.close();
        }
    
    }

# 8、01翻转 #

## 牛牛正在挑战一款名为01翻转的游戏。游戏初始有A个0,B个1，牛牛的目标就是把所有的值都变为1，每次操作牛牛可以任意选择恰好K个数字，并将这K个数字的值进行翻转(0变为1，1变为0)。牛牛如果使用最少的操作次数完成这个游戏就可以获得奖品，牛牛想知道最少的操作次数是多少？ ##

## 例如:A = 4 B = 0 K = 3 ##

## 0000 -> 1110 -> 1001 -> 0100 -> 1111 ##

## 需要的最少操作次数为4 ##

### 输入描述: ###

输入为一行：  
一共三个整数A(0 ≤ A ≤ 100,000),B(0 ≤ B ≤ 100,000),K(1 ≤ K ≤100,000).以空格分隔

### 输出描述: ###

输出一个整数，表示最少需要的操作次数。如果不能完成，则输出-1

输入例子:  
4 0 3

输出例子:  
4

## 答案： ##

设 n = A+B  
设 位置值序列集合 E = \{e1, e2, e3,… en\}， ei ∈ \{0, 1\}，其中ei表示第i个位置上的值 （1 ≤ i ≤ n）  
假设初始时，前面A个位置为0，后面B个位置为1  
设 Ti 为 第i个位置上翻转的次数  
因为一次翻转必翻转K个位置，假设进行了X次翻转（未知数），则有以下等式  
① XK = ∑Ti （1 ≤ i ≤ n）  
因为同一个位置翻转2次得到是原来的值，所以为了使所有位置均为1， Ti 必满足以下条件：  
② Ti = 1 + 2Si （ei 初始为0）  
③ Ti = 2Si（ei 初始为1）  
其中Si 表示第i个位置进行了 Si次2次翻转  
结合①、②、③可得：  
④ XK = A + 2 ∑Si （1 ≤ i ≤ n）  
⑤ XK - A 必为偶数  
我对此的理解为，总的来看：在某些位置上进行了2次翻转，和A个位置的1次翻转，就全部为1了。  
对 ∑Si 观察可得：  
对于初始为1的位置，2次翻转次数不能超过X/2  
对于初始为0的位置，2次翻转次数不能超过(X-1)/2 ，因为最后一次翻转不能属于“2次翻转”中的一次翻转  
我们假设所有位置的2次翻转次数都达到最大，即 Ti =X,则有不等式：  
⑥ (XK - A)/2 = ∑Si （1 ≤ i ≤ n）≤ A ((X-1)/2) + B(X/2)  
满足⑤、⑥条件X即可满足题意  
我们可以相信，X不能大于 A的最大值+B的最大值 = 200000

public class fanzhuan01_8 {
          public static void main(String[] args) {
                Scanner in = new Scanner(System.in);
    
                    int A = in.nextInt();
                    int B = in.nextInt();
                    int K = in.nextInt();
                    in.close();
                    System.out.println(calZeroReverse(A, B, K));
    
    
            }
    
         public static int calZeroReverse(int A, int B, int K) {
                int MAX = 200000;
                int N = 0;
                for (; N <= MAX; N++) {
                    if (N*K - A < 0 || (N*K - A) % 2 != 0) {
                        continue;
                    }
                    if ((N*K - A) / 2 <= A * ((N-1)/2) + B * (N/2) || A == 0) {
                        break;
                    }
                }
                if (N <= MAX){
                    return N;
                }
                else {
                    return -1;
                }
    
            }
    
    
    }

[SouthEast]: /images/20220705/b8f50bea23384c83af4e4d8a3caaa54f.png