携程筆記試験2020/04/01

3つのプログラミング問題を記録する
第一題

       
    ：C/C++   1000MS；     3000MS
    ：C/C++   65536KB；     589824KB
    ：
      7×24                ，           ，                   ，          。                 ，              ？

  
    n            ，     n ，            ，                     。   ：10,30，  [10,30)，   10   ， 30     ，  30         ；            ，                 ；

  
      ；

          ，              。


    
6
0,30
0,50
10,20
15,30
20,50
20,65
    
5

初めて、ac:20%で、方法を間違えて、考えが行き届いていないで、40分以上浪費して、最後の問題をする時間がありません

import java.util.ArrayList;
import java.util.Scanner;

public class First {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList list = new ArrayList();
        //  n   
        sc.nextLine();
        for(int i = 0; i < n; i++){
            String string = sc.nextLine();
            String[] s = string.split(",");
            Integer[] arr = new Integer[2];
            arr[0] = Integer.parseInt(s[0]);
            arr[1] = Integer.parseInt(s[1]);
            if(list.size() == 0){
                Person person1 = new Person();
                person1.time.add(arr);
                list.add(person1);
            } else {
                //                
                for(int j = 0; j < list.size(); j++){
                    if(judge(list.get(j), arr)){
                        list.get(j).time.add(arr);
                    } else {
                        Person person2 = new Person();
                        person2.time.add(arr);
                        list.add(person2);
                    }
                }
            }
        }
        //      
        System.out.println(list.size());
    }

    //             
    public static boolean judge(Person person, Integer[] arr){
        Integer[] temp;
        for(int i = 0; i < person.time.size(); i++){
            temp = person.time.get(i);
            //           
            if(temp[0] <= arr[0] && temp[1] >= arr[1]){
                return false;
            }
            //  
            if((temp[0] >= arr[0] && temp[0] < arr[1]) || (temp[1] > arr[0] && temp[1] <= arr[1])){
                return false;
            }
        }
        return true;
    }

}
class Person{
    ArrayList time = new ArrayList();
}

2回目:ac:100%メソッド:bitmap

import java.util.HashMap;
import java.util.Scanner;

public class First2 {
    public static void main(String[] args) {
        int count = 0;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        HashMap map = new HashMap<>();
        for(int i = 0; i < n; i++){
            String string = sc.nextLine();
            String[] split = string.split(",");
            int[] arr = new int[2];
            arr[0] = Integer.parseInt(split[0]);
            arr[1] = Integer.parseInt(split[1]);
            for(int j = arr[0];j < arr[1]; j++){
                if(map.get(j) == null){
                    map.put(j,1);
                } else {
                    map.put(j, map.get(j) + 1);
                }
                count = map.get(j) > count ? map.get(j) : count;
            }
        }
        System.out.println(count);
    }
}

第二題

           
    ：C/C++   1000MS；     3000MS
    ：C/C++   65536KB；     589824KB
    ：
        n        ，     0  ，          m  ，

         birthYear[i]              （1 <= birthYear[i] <= m），           0  。

  x   ，            ？

  
n（     ）

m（    ）

          (   p)

        1

...

        p

x（   ）

  
x  ，        


    
5
5
2
2
4
5
    
20

ac:38%

import java.util.HashMap;
import java.util.Scanner;

public class Second {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int p = sc.nextInt();
        int[] arr = new int[p];
        for(int i = 0; i < p; i++){
            arr[i] = sc.nextInt();
        }
        int x = sc.nextInt();
        HashMap map = new HashMap<>();
        map.put(1,n);
        int temp = 0;
        for(int i = 1; i <= x; i++){
            if(map.get(i) != null) {
                temp = map.get(i);
                for (int j = 0; j < arr.length; j++) {
                    if (map.get(i + arr[j]) == null) {
                        map.put(i + arr[j], temp);
                    } else {
                        map.put(i + arr[j], map.get(i + arr[j]) + temp);
                    }
                }
            }
        }
        int count = 0;
        for(int i = x - m + 1; i <= x; i++){
            if(map.get(i) != null){
                count += map.get(i);
            }
        }
        System.out.println(count);

    }
}

第三題

  ElasticSearch  FuzzyQuery      
    ：C/C++   1000MS；     3000MS
    ：C/C++   65536KB；     589824KB
    ：
ElasticSearch           ，  fuzzyQuery          。

       ，surprize     ， z  s     surprise，       ，

          。

  ， surprize z   s，       d，    surprised。


    [ "surprise", "happy", "ctrip", "travel", "wellcome","student","system","program","editor"]

     。


        ，          2(  )              。

         ，

1：           ;

2：           ;

3：           。

  
      1

...

      n

  
      ,         ,

      ,      null


    
hipp
    
happy

やる時間がない