友人C

北邮2014软院机试
Problem A.奇偶求和题目描述题目链接给出N个数,求出这N个数,奇数的和以及偶数的和。输入格式第一行为测试数...
扫描右侧二维码阅读全文
01
2019/03

北邮2014软院机试

Problem A.奇偶求和

题目描述

题目链接

给出N个数,求出这N个数,奇数的和以及偶数的和。

输入格式

第一行为测试数据的组数T(1<=T<=50)。请注意,任意两组测试数据之间是相互独立的。

每组数据包括两行:

第一行为一个整数N(1 <= N <=100)。

第二行为N个正整数,整数之间用一个空格隔开,且每个整数的绝对值均 不大于10^5。

输出格式

每组数据输出两个数,即N个数中奇数之和和偶数之和,中间用空格隔开。

输入样例

2
5
1 2 3 4 5 
5
1 1 1 1 1

输出样例

9 6
5 0

思路解析

送分题,不用解析了

AC代码

import java.util.Scanner;

public class OddEvenAdd {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        for(int i =0;i<num;i++){
            int N = scanner.nextInt();
            int odd = 0;
            int event = 0;
            for (int j = 0; j < N; j++) {
                int input = scanner.nextInt();
                if (input%2 == 0) {
                    event += input;
                }else {
                    odd += input;
                }
            }
            
            System.out.println(odd + " " + event);
        }
    }
}

Problem B.最长连续等差子数列

题目描述

题目链接

给定-个长度为N的整数数列,你需要在其中找到最长的连续子数列的长度, 并满足这个子数列是等差的。
注意公差小于或等于0的情况也是允许的。

输入格式

第一行为数据组数T(1~100),表示测试数据的组数。
对于每组测试数据:
第一行是一个正整数N (1~ 100),表示给定数列的长度^
第二行是N个整数,其中第丨个整数valuei (1<= valuei <= 10s)表示下标为i 的数字。

输出格式

对于每组测试数据,输出最长的连续等差子数列的长度。

样例输入

2
2
1 3
5
1 6 4 2 4

样例输出

2
3

思路解析

这题难度还可以增强一点,比如让你输入最长等差数列,而不只是长度。

  • 从头到尾扫描一遍数组,然后把后一个元素减掉前一个元素的差存下来,看后后一个元素减去后一个元素差是否相等,如果相等,等差数列长度加一,否则表示等差数列断掉了,就需要重新计数。
  • 要考虑好特殊情况,数组长度为1,等差数列长度为1,数组长度为2,等差数列长度也为2.

AC代码

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class maxArray {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        
        for(int i = 0;i< num;i++){
            int N = scanner.nextInt();
            int [] array = new int[N];
            int tempsub = 0;
            int tempLeght =2;//
            List<Integer> list = new ArrayList<Integer>();
            for (int j = 0; j < N; j++) {
                array[j] = scanner.nextInt();
                if (j==1) {
                    tempsub = array[1] - array[0];
                }else if (j > 1) {
                    int currentSub = array[j] - array[j-1];
                    if (currentSub == tempsub) {
                        tempLeght ++;
                    }else {
                        list.add(tempLeght);
                        tempLeght = 2;
                        tempsub = currentSub;
                    }
                }
            }
            list.add(tempLeght);
            
            Collections.sort(list);
            if (N == 1) {
                System.out.println("1");
            }else {
                System.out.println(list.get(list.size() -1));
            }
        }
        
        scanner.close();
    }
}

Problem C. 最近公共祖先

题目描述

题目链接

给出一棵有N个节点的有根树TREE(根的编号为1),对于每组查询,请输出树上节点u和v的最近公共祖先。
最近公共祖先:对于有向树TREE的两个结点u,v。最近公共祖先LCA(TREE u,v)表示一个节点x,满足x是u、v的祖先且x的深度尽可能大。

输入格式

输入数据第一行是一个整数T(1<=T<=100),表示测试数据的组数。
对于每组测试数据:
第一行是一个正整数N(1<=N<=100),表示树上有N个节点。
接下来N-1行,每行两个整数u,v(1<=u,v<=N),表示节点u是v的父节点。
接下来一行是一个整数M(1<=M<=1000),表示查询的数量。
接下来M行,每行两个整数u,v(11<=u,v<=N),表示查询节点u和节点v的最近公共祖先。

输出格式

对于每个查询,输出一个整数,表示最近公共祖先的编号,

输入样例

2
3
1 2
1 3
1
2 3
4
1 2
1 3
3 4
2
2 3
3 4

输出样例

1
1
3

思路解析

  • 树的表示,这题就是用到前面说的双亲表示法/父亲表示法,用顺序数组存储,很容易找到从该点到根的路径(不是从根到该点的路径,所以反向输出就可以了)。
  • 最近公共祖先,就是两条路径,都是从根开始匹配,当匹配到的第一个不相等的节点时候,那么上一个节点就是两者的最近公共祖先。

AC代码

import java.util.Scanner;

public class Common {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        for (int i = 0; i < num; i++) {
            int N = scanner.nextInt();//the num of vertexes
            int [] edges = new int [N+1];
            edges[1] = -1;//root
            for (int j = 0; j < N -1; j++) {
                int parent = scanner.nextInt();
                int child = scanner.nextInt();
                edges[child] = parent;
            }
            int queryNum = scanner.nextInt();
            for (int j = 0; j < queryNum; j++) {
                int u = scanner.nextInt();
                int v = scanner.nextInt();
                
                int [] array_u =  new int[N+1];
                int [] array_v =  new int[N+1];
                int u_length = 0;
                int v_length = 0;
                
                
                int parent_u = u;
                int parent_v = v;
                array_u[0] = u;
                array_v[0] = v;
                for (int k = 1; ; k++) {
                    
                    
                    if (parent_u!=-1) {
                        parent_u = edges[u];
                        u = parent_u;
                        array_u[k] = parent_u;    
                        u_length++;
                    }

                    
                    if (parent_v!=-1) {
                        parent_v = edges[v];
                        v = parent_v;
                        array_v[k] = parent_v;
                        v_length ++;
                    }
                    if (parent_u == -1 && parent_v == -1) {
                        break;
                    }
                }
                int length = Math.max(v_length,u_length);
                
                int common = -1;
                
                
                for(int m = v_length-1,o = u_length-1; ;m--,o --){
                    if (m == -1 || o == -1) {
                        break;
                    }else {
                        if (array_u[o] == array_v[m]) {
                            common = array_u[o];
                        }else {
                            break;
                        }    
                    }
                }
                System.out.println(common);
            }
        }
    }
}

Problem D. 数据库检索

题目描述

题目链接

在数据库的操作过程中,我们进场会遇到检索操作。这个题目的任务是完成一些特定格式的检索,并输出符合条件的数据库中的所有结果。
我们现在有一个数据库,维护了学生的姓名(Name),性别(Sex)以及出生日期(Birthday)。其中,Name项是长度不超过30的字符串,只可能包含大小写字母,没有空格;Sex项进可能为Male或者Female;Birthday项以yyy/mm/dd的格式存储,如:1990/01/01,1991/12/31,等等。
每个查询所可能包含的条件如下:
Name=‘REQUIRED_NAME’,查询姓名为REQUIRED_NAME的学生,其中REQUIRED_NAME为长度在1到30之间的字符串;
Sex=‘Male’或Sex=‘Female’,查询性别为男/女的学生;
Birthday=‘yyy/mm/dd’,查询出生年/月/日为特定值的学生。如果其中某项为’’,则说明该项不受限制。例如,‘1990/06/’表示1990年6月出生,‘/03/’表示出生月份为3月。
给定数据库的所有表项以及若干条查询,你需要对每条查询输出它返回的结果。

输入格式

输入包含多组测试数据。输入的第一行为测试数据的组数T(1<=T<=50)。
对于每组测试数据,第一行是两个整数N和M(N,M<=500),分别表示数据的数量以及查询的数量。
接下来N行,每行以Name Sex Birthday的形式给出每个学生的信息。
没下来M行,每行给出若干条限制条件,以空格隔开。条件以Name Sex Birthday的顺序给出(如果存在),且每种限制条件最多只出现一次。

输出格式

对于每条查询,按照输入的顺序输出符合条件的学生姓名,每个一行。如果没有符合查询的信息,则输出一行NULL。

样例输入

1
5 6
Michael Male 1990/02/28
Amy Female 1992/04/03
Tom Male 1991/12/15
Lynn Female 1991/04/09
Zheng Male 1990/04/20
Name=’Amy’
Name=’Betty’
Sex=’Female’ Birthday=’*/04/09’
Sex=’Female’ Birthday=’//*’
Name=’Michael’ Sex=’Female’
Name=’Michael’ Sex=’Male’ Birthday=’1990/02/*’

样例输出

Amy
NULL
Lynn
Amy
Lynn
NULL
Michael

思路解析

  • 难点1处理输入,这个和2014北邮网研机试的problem 4 输入差不多的点,明白了就很容易
  • 难点2匹配这个日期是否相等。需要年月日三个条件都满足才可以。
  • 但是提交总是超时,没能优化成功……

超时代码

package bupt;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;


public class Search {
    private static Scanner scanner;

    List<Student> students = new ArrayList<Student>();
    
    int inputNum;
    int queryNum;
    
    public static void main(String[] args) {

        scanner = new Scanner(System.in);
        
        int arrayNum = scanner.nextInt();
        for (int i = 0; i < arrayNum; i++) {
            Search search = new Search();
            search.handle();    
        }
    }
    
    public void handle(){
        inputNum = scanner.nextInt();
        queryNum = scanner.nextInt();

        handleInputConditions();
        handleInputQueries();
        
    }
    
    public void handleInputConditions(){
        for (int j = 0; j < inputNum; j++) {
            //input
            String name = scanner.next();
            String sex = scanner.next();
            String date = scanner.next();
            Student student = new Student(name,sex,date);
            students.add(student);
        }
    }
    
    public void handleInputQueries(){
        for (int j = 0; j < queryNum; j++) {
            //query
            if (j == 0) {
                String notUse = scanner.nextLine();//\n
            }
            String input = scanner.nextLine();
            
            boolean is_suits = false;
            
            for (Iterator<Student> iterator = students.iterator(); iterator.hasNext();) {
                boolean student_suits_all_conditons_flag = true;// true means suits false mean not suits.
                Student student = (Student) iterator.next();
                for (int k = 0; k < inputArray.length; k++) {// circle by each condition
                    String query = inputArray[k];
                    String[] array = query.split("=");
                    if (array[0].equals("Name")) {
                        String name = splitTrueString(array[1]);
                        if (!name.equals(student.name)) {
                            student_suits_all_conditons_flag = false;
                        }
                    }else if (array[0].equals("Sex")) {
                        student_suits_all_conditons_flag = is_suit_sex(splitTrueString(array[1]),student.sex);
                    }else if (array[0].equals("Birthday")) {
                        student_suits_all_conditons_flag = is_suit_birthDay(splitTrueString(array[1]),student.birthdate);
                    }
                    if (!student_suits_all_conditons_flag) {//end the condition circle only if one condition not suits
                        break;
                    }
                }//end conditions circle    
                
                if (student_suits_all_conditons_flag) {//suit
                    if (!is_suits) {
                        is_suits = true;    
                    }
                    System.out.println(student.name);

                }
            }// end students circle
            
            if(!is_suits) {// not a student suits the all conditions
                System.out.println("NULL");
            }
        
        }
    }
    
    public boolean is_suit_name(String name,String student_name){
        return name.equals(student_name);
    }
    
    public boolean is_suit_sex(String sex,String student_sex){
        return sex.equals(student_sex);
    }
    
    public boolean is_suit_birthDay(String birthday,String [] student_array){
        String [] birthdayArray = splitDate(birthday);
        for (int l = 0; l < birthdayArray.length; l++) {
            if (!birthdayArray[l] .equals("")  && !birthdayArray[l] .equals("*")) {
                if (!student_array[l].equals(birthdayArray[l])) {
                    return false;
                }
            
            }    
        }
        return true;
    }
    class Student{
        String name;
        String sex;
        String[] birthdate = new String[3];
        
        public Student() {
        }
        
        Student(String name,String sex,String date){
            this.name = name;
            this.sex = sex;
            this.birthdate = splitDate(date);
        }
        
    }
    
    
    public String[] splitDate(String input){
        return input.split("\\/",0);
    }
    
    public String splitTrueString(String string){
        return string.substring(1,(string.length()-1));
    }
}
C++ 版本指路 https://blog.csdn.net/TQCAI666/article/details/86762459
最后修改:2019 年 03 月 01 日 10 : 35 PM
打赏一包辣条钱吧,唔该啊大佬

5 条评论

  1. 揽山

    加油 今天准备机试的时候搜到了你的代码 祝都能考上北邮做同学

    1. 友人C
      @揽山

      加油加油

  2. 夏目贵志

    如果当初在努力一点

    或许现在的我 应该在上学而不是上班

    1. 友人C
      @夏目贵志

      其实也比没有什么所谓。什么样的人生都会有不一样的遗憾而已

      1. 夏目贵志
        @友人C

        也对 回忆过去 不如珍惜现在

发表评论