GridlandメトロHackerrankジャワ

Question

I [1] Hackerrankにこの問題を解決しています：https://www.hackerrank.com/challenges/gridland-metro

Gridlandの都市は、行が1からnまで番号付けされているMによってN行列として表されますであり、列には1からmという番号が付けられています。

グリッドランドには、常に列に沿って直線の水平線で走る列車のネットワークがあります。換言すれば、列車のトラックの開始点と終了点は、RはC1が開始列、およびC2を表し、行番号を表す（R、C1）及び（R、C2）、ありますは列車の終了列を表す。

市長が都市を調査して、街灯柱を配置できる場所の数を決定しています。電柱は電車のトラックで占められていないセルに配置できます。 GridlandとそのK列車のトラックのマップを考えると

、市長が街灯柱を配置することができ、細胞の数を見つけて印刷します。

注：列車のトラックは、同じ列内の他の列車のトラックと重複する場合もあれば、重ならない場合もあります。

入力形式

最初の行は、Nのそれぞれの値を記述する3スペースで区切られた整数（行数）、メートル（列の数）を、含まk（列車のトラック数）。 各行iはK後続の行の列車軌道を定義R、C1、とC2のそれぞれの値を記述する3スペースで区切られた整数を含みます。

市長がランプポストをインストールできるセルの数を示す単一の整数を出力します。ここで

は私のソリューションです：

import java.io. * ; 
import java.util. * ; 

public class Solution { 

    public static void main(String[] args) { 
     /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ 
     Scanner input = new Scanner(System. in); 
     int n = input.nextInt(); 
     int m = input.nextInt(); 
     int k = input.nextInt(); 
     int[][] arr = new int[n][m]; 
     int occupied = 0; 
     for (int i = 0; i < n; i++) { 
      Arrays.fill(arr[i], 0); 
     } 
     for (int i = 0; i < k; i++) { 
      int r = input.nextInt() - 1; 
      int c1 = input.nextInt() - 1; 
      int c2 = input.nextInt() - 1; 
      for (int j = c1; j <= c2; j++) { 
       arr[r][j] = -1; 
      } 
     } 
     int count = 0; 
     for (int i = 0; i < n; i++) { 
      for (int j = 0; j < m; j++) { 
       if (arr[i][j] != -1) { 
        count++; 
       } 
      } 
     } 
     System.out.println(count); 
    } 
} 

誰もが私のコードで問題を指摘することはできますか？ （提出時に4つのテストケースを渡すだけです）

Answer 1

質問の制約は1<=n,m<=10^9です。

たとえば、n、mがともに10^9の場合、arrのサイズは10^18 * 4 /(1024 * 1024 * 1024) Gbとなるため、膨大な量のヒープスペースを必要とするため、このようなサイズの2次元配列を宣言することはできません。

この大きな問題は、この大きな配列を使用せずに解決できます。あなたが正しい方法で助けが必要な場合は、私は助けることができるが、まずあなた自身で試してみてください。

Answer 2

私はHashMapを使用してこのソリューションを作成しました。マップを維持しています。Integerは行番号で、hashsetは特定の行にアクセスした列のセットです。このマップは、トラックが重なっているかどうかを確認するために維持されます。このコードは小さなテストケースについて正解を返します。しかし、ほとんどのテストケースでは、タイムアウトのために失敗します。このコードを最適化するための助けがあれば非常に感謝しています。

import java.io.*; 
import java.util.*; 
import java.text.*; 
import java.math.*; 
import java.util.regex.*; 

public class Solution { 

    public static void main(String[] args) { 

     Scanner sc = new Scanner(System.in); 
     long n = sc.nextInt(); 
     long m = sc.nextInt(); 
     int k = sc.nextInt();   
     HashMap<Integer,HashSet> map = new HashMap<Integer,HashSet>(); 
     long count = n*m; 
     for (int i =0;i<k;i++) 
      { 
      HashSet<Integer> set = new HashSet<Integer>();  
      int row = sc.nextInt(); 
      int c1 = sc.nextInt(); 
      int c2 = sc.nextInt(); 
      //System.out.println(row+" "+ c1+" "+c2); 
      if (map.containsKey(row)) 
       { 
       set = map.get(row); 
       for (int j = c1;j<=c2;j++) 
       { 
        if(set.add(j)) count--; 
       } 
       //if (set.add(c2)) count--; 
       map.put(row,set); 
      } 
       else 
       { 
        for (int p = c1;p<=c2;p++) 
        { 
         if (set.add(p)) count --; 
        } 
        //if (set.add(c2)) count--; 

        map.put(row,set); 
       } 
     } 
     System.out.println(count); 

    } 
    } 

Answer 3

私はそれがHackerRankの精神にあるとは思わないので、ここで解決策を提示するつもりはありません。しかし、私はいくつかのヒントを提供し、あなたのコードの問題を特定しました。

Scanner input = new Scanner(System.in); 
int n = input.nextInt();//ERROR: n ranges from 1 to 10E9, read in as a String 
int m = input.nextInt();//ERROR: m ranges from 1 to 10E9, read in as String 
int k = input.nextInt(); 
int[][] arr = new int[n][m];/*ERROR: The range of an int is 2E31-1 and large 
            integers will cause stack overflow anyway. 
            You'll need to consider a data structure 
            that's compatible w/ strings. Hint, consider 
            a hash table. */ 
int occupied = 0; 
for (int i = 0; i < n; i++) { 
    Arrays.fill(arr[i], 0); 
} 
for (int i = 0; i < k; i++) { 
    int r = input.nextInt() - 1;//ERROR: r ranges from 1 to 10E9, read in as a String 
    int c1 = input.nextInt() - 1;//ERROR: c1 ranges from 1 to 10E9, read in as a String 
    int c2 = input.nextInt() - 1;//ERROR: c2 ranges from 1 to 10E9, read in as a String 
    for (int j = c1; j <= c2; j++) { 
     arr[r][j] = -1; 
    } 
} 
/* NOTE: A train track may (or may not) overlap other train tracks within the 
    same row. Hence, your algorithm will need to account for track overlaps 
    and tracks that are in between of each other. For example, if a track 
    overlaps with another track in the same the row, the tracks should be 
    merged into a single track. If a smaller track is contained in a bigger 
    track, the smaller track should be ignored.*/ 
int count = 0; 
for (int i = 0; i < n; i++) { 
    for (int j = 0; j < m; j++) { 
     if (arr[i][j] != -1) { 
      count++; 
     } 
    } 
} 

System.out.println(count);