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.最长连续等差子数列
题目描述
输入格式
输出格式
对于每组测试数据,输出最长的连续等差子数列的长度。
样例输入
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. 最近公共祖先
题目描述
输入格式
输出格式
对于每个查询,输出一个整数,表示最近公共祖先的编号,
输入样例
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. 数据库检索
题目描述
输入格式
输出格式
对于每条查询,按照输入的顺序输出符合条件的学生姓名,每个一行。如果没有符合查询的信息,则输出一行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));
}
}
5 条评论
加油 今天准备机试的时候搜到了你的代码 祝都能考上北邮做同学
加油加油
如果当初在努力一点
或许现在的我 应该在上学而不是上班
其实也比没有什么所谓。什么样的人生都会有不一样的遗憾而已
也对 回忆过去 不如珍惜现在