爱奇艺秋季校招Android工程师（第一场）-2018年

一、单项选择题

1、下面代码输出的结果为（ ）

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Test{
    public static void main(String[] args) {
        List<Student> students = new ArrayList<Student>();
        students.add(new Student(10));
        students.add(new Student(18));
        students.add(new Student(15));
        Collections.sort(students);
        System.out.print(students.get(1).age);
    }
}
class Student implements Comparable<Student> {
    Integer age;
    public Student(Integer age) {
      this.age = age;
    }
    public int compareTo(Student s) {
        return s.age.compareTo(this.age);
    }
}

A、15
B、10
C、18
D、编译失败
2、在Linux系统中哪个程序是特定的时间上安排特定的作业或者程序的运行（ ）
A、vi
B、Outlook
C、Scheduler
D、cron
3、一个提供NAT服务的路由器在转发一个源IP地址为10.0.0.1、目的IP地址为131.12.1.1的IP分组时，可能重写的IP分组首部字段是（ ）
Ⅰ.TTL
Ⅱ.片偏移量
Ⅲ.源IP地址
Ⅳ.目的IP地址
A、仅Ⅰ
B、仅I、Ⅱ
C、仅Ⅰ、Ⅱ、III
D、Ⅰ、Ⅱ、Ⅲ、Ⅳ
4、下列关于Android目录结构说明错误的是（ ）
A、assest下主要存放资源文件,如字体库,db库等
B、anim下主要存放一些以XML方式存在的动画源文件
C、values下可以放诸如string,attrs,style等各种属性,样式文件
D、drawable有很多个文件夹,根据手机屏幕密度依次增高,对应的图片文件夹分别是drawable-mdpi, drawable-ldpi, drawable-hdpi, drawable-xhdpi, drawable-xxhdpi
5、关于Android手势分发顺序下列正确的是（ ）
A、dispatchTouchEvent→onInterceptTouchEvent→onTouchEvent
B、dispatchTouchEvent→onTouchEvent→onInterceptTouchEvent
C、onInterceptTouchEvent→dispatchTouchEvent→onTouchEvent
D、onTouchEvent→onInterceptTouchEvent→dispatchTouchEvent
6、线程是Android中经常用到的场景,一般都是继承Runnable然后实现run方法,当开启线程时,调用以下哪个方法,就会自动执行run方法（ ）
A、doRun()
B、start();
C、doAction();
D、doStart();

7、现定义如下三个类,

public class A{
    Private static A a = new A();
    Private A(){};
    Public static A getA(){
        return a;
    }
}
public class B{
    private static B b = null;
    private B(){};
    public static B getB(){
        b = new B();
        return b;
    }
}
public class C{
    private static C c = null;
    static{
        c = new C();
    }
    private C(){};
    public static C getC(){
        return c;
    }
}

请问属于单例模式的类是（ ）

A、classA和classB
B、classB和classC
C、只有classA
D、classA 和classC
8、对于字符串"ABCDADA"的二进制哈夫曼编码有多少位（ ）
A、11
B、12
C、13
D、14
9、下面关于选择排序说法正确的是（ ）
A、每扫描一遍数组，需要多次交换
B、选择排序是稳定的排序方法,因为时间复杂度是固定的O（n^2）
C、选择排序排序速度一般要比冒泡排序快
D、空间复杂度为O（1）
10、在UML建模中，下列哪个UML的图一般用于描述软件系统的需求（ ）
A、状态图
B、协作图
C、用例图
D、顺序图

二、编程题

1、牛牛有一些排成一行的正方形。每个正方形已经被染成红色或者绿色。牛牛现在可以选择任意一个正方形然后用这两种颜色的任意一种进行染色,这个正方形的颜色将会被覆盖。牛牛的目标是在完成染色之后,每个红色R都比每个绿色G距离最左侧近。牛牛想知道他最少需要涂染几个正方形。
如样例所示: s = RGRGR
我们涂染之后变成RRRGG满足要求了,涂染的个数为2,没有比这个更好的涂染方案。
2、
牛牛手中有三根木棍,长度分别是a,b,c。牛牛可以把任一一根木棍长度削短,牛牛的目标是让这三根木棍构成一个三角形,并且牛牛还希望这个三角形的周长越大越好。
3、一个合法的括号匹配序列有以下定义:
(1)、空串""是一个合法的括号匹配序列
(2)、如果"X"和"Y"都是合法的括号匹配序列,"XY"也是一个合法的括号匹配序列
(3)、如果"X"是一个合法的括号匹配序列,那么"(X)"也是一个合法的括号匹配序列
(4)、每个合法的括号序列都可以由以上规则生成。
例如: "","()","()()","((()))"都是合法的括号序列
对于一个合法的括号序列我们又有以下定义它的深度:
(1)、空串""的深度是0
(2)、如果字符串"X"的深度是x,字符串"Y"的深度是y,那么字符串"XY"的深度为max(x,y) 3、如果"X"的深度是x,那么字符串"(X)"的深度是x+1
例如: "()()()"的深度是1,"((()))"的深度是3。牛牛现在给你一个合法的括号序列,需要你计算出其深度。

参考答案

一、
1~5：ADCDA
6~10：BDCDC
二、
1、

import java.util.Scanner;
public class Main {
   public static void main(String[] args)
   {
      Scanner scanner = new Scanner(System.in);
      char[] charArray = scanner.nextLine().toCharArray();
      int length = charArray.length;
     // int number[] = new int[length];
      int lIndex = 0;
      int rIndex = length-1;
      int RCount = 0;
      int GCount = 0;
 
      while(lIndex<1||rIndex>=1)
      {
         if(lIndex<1&&charArray[lIndex]=='G')
         {
            GCount++;
         }
         lIndex++;
         if(rIndex>=1&&charArray[rIndex]=='R')
         {
            RCount++;
         }
         rIndex--;
      }
      int min = GCount + RCount;
 
      for(int i=1;i<length;i++)
      {
         if(charArray[i]=='R')
         {
            if(RCount>0)
            RCount--;
         }
         else if(charArray[i]=='G')
         {
            GCount++;
         }
         if(min>GCount+RCount)
            min = GCount + RCount;
      }
      int ToGNumber = 0;
      for(int i=0;i<length;i++)
      {
         if(charArray[i]=='R')
         ToGNumber++;
      }
      if(ToGNumber<min)
         min = ToGNumber;
      System.out.println(min);
   }
 
}

2、

import java.util.Scanner;
public class Main {
   public static void main(String[] args)
   {
     Scanner scanner = new Scanner(System.in);
     int a = scanner.nextInt();
     int b = scanner.nextInt();
     int c = scanner.nextInt();
     int max = length(a,b,c);
     int middle = length(a,c,b);
     if(max<middle)
        max = middle;
     middle = length(b,c,a);
      if(max<middle)
         max = middle;
      middle = length(c,b,a);
      if(max<middle)
         max = middle;
      middle = length(c,a,b);
      if(max<middle)
         max = middle;
      middle = length(b,a,c);
      if(max<middle)
         max = middle;
      System.out.println(max);
   }
   public static int length(int x,int y,int z)
   {
      if(x + y <= z)
      {
        z = x + y - 1;
      }
      if(x + z <= y)
      {
         y = x + z - 1;
      }
      if(y + z <= x)
      {
         x = y + z - 1;
      }
      return x + y + z;
   }
}

3、

import java.util.Scanner;
import java.util.Stack;
public class Main {
   public static void main(String[] args)
   {
      Stack<Character>stack = new Stack<Character>();
      Scanner scanner = new Scanner(System.in);
      char[]chars = scanner.nextLine().toCharArray();
      int max = 0;
      for (char c:chars
           ) {
         if(c=='(') {
            stack.push(c);
            if(max<stack.size())
               max = stack.size();
         }
         else if(c==')')
            stack.pop();
      }
      System.out.println(max);
   }
}