Hackerearthは友達を削除します：ランタイムエラー - NZEC

Question

私はこの問題に固執しています。私のコードは、この例で示したすべてのテストケースを渡しますが、コードには何らかのエラーがあります。エラーを親切に指摘してください。

問題文（https://www.hackerearth.com/problem/algorithm/remove-friends-5）

彼女の博士号を取得した後、クリスティは、彼女の大学で有名人になってきている、と彼女のFacebookのプロフィールには、友達リクエストがいっぱいです。彼女は素敵な女の子なので、クリスティはすべての要求を受け入れました。

今、Kuldeepは彼女が他の人から得ているすべての注意を嫉妬しているので、友人のリストから少年を削除するように彼女に求めます。 「シーン」を避けるために、Christieは友人のリストからいくつかの友人を削除することに決めました。彼女はそれぞれの友人の人気を知っているので、次のアルゴリズムを使って友人を削除します。

アルゴリズム削除（友人）：

 DeleteFriend=false 
for i = 1 to Friend.length-1 
    if (Friend[i].popularity < Friend[i+1].popularity) 
     delete i th friend 
     DeleteFriend=true 
     break 
if(DeleteFriend == false) 
    delete the last friend 

入力： 最初の行は、テストケースのT番号を含みます。各テストケースの最初の行には、Christieが現在持っている友人の人数Nと、Christieが削除を決定した友人の人数Kが含まれています。次の行には、スペースで区切られた友人の人気が含まれています。

出力： 各テストケースでは、Kの友人を削除した後のChristie friendの人気を表すN-K番号を印刷します。

注記 正確にK人の友人を削除した後の友人の注文は、入力したとおりに維持する必要があります。

マイソリューション

class TestClass { 
static class Node 
{ 
    int data; 
    Node next; 
    Node(int d) 
    { 
     data = d; 
     next = null; 
    }} 
static Node head = null; 
public static void main(String args[]) throws Exception { 
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
    String line = br.readLine(); 
    int cases = Integer.parseInt(line); 
    for (int i = 0; i < cases; i++) { 
     line = br.readLine(); 
     int friends = Integer.parseInt(line); 
     line = br.readLine(); 
     int delete = Integer.parseInt(line); 
     head = null; 
     Node p =null; 
     for(int j=0;j < friends;j++){ 
      line = br.readLine(); 
      int temp = Integer.parseInt(line); 
      if(head == null){ 
       head = new Node(temp); 
       p = head; 
      } 
      else{ 
       Node q = new Node(temp); 
       p.next = q; 
       p = q; 
      }} 
     delete_friend(head , delete); 
     print_list(head); 
    }} 
static void delete_friend(Node h, int delete){ 
    Node p = head; 
    Node q = null; 
    int flag = 0; 
    for (int x = 1; x<=delete;x++){ 
     p = head; 
     flag = 0; 
     q = p.next; 
     while(p.next != null){ 
      q = p.next; 
      if(p.data < q.data){ 
       p.data = q.data; 
       p.next = q.next; 
       flag=1; 
       p = head; 
       break; 
      } 
      if (flag == 0 && q.next == null){ 
       if (p.data >= q.data) { 
        p.next = null; 
        break; 
       }} 
      p = p.next; 
     }}} 
static void print_list(Node head){ 
    Node tnode = head; 
    while (tnode != null) 
    { 
     System.out.print(tnode.data+" "); 
     tnode = tnode.next; 
    } 
    System.out.println(); 
}} 

Answer 1

あなたが入力されたデータは欠陥がある読ん方法： あなたの実装は、1行に1つの整数を前提としてい が、これは問題の説明と一致しません：

最初の行を各テストケースのNには、現在クリスティが持っている友達の数とK、クリスティが削除することを決めた人の数が含まれています。次の行には、スペースで区切られた友人の人気が含まれています。

私が代わりにScannerを使用してみてくださいすることをお勧め代わりにBufferedReader、 を使用するのでは、それは簡単です、このような 何か：あなたはパース入力を確定した後

Scanner scanner = new Scanner(System.in); 
int t = scanner.nextInt(); 

for (int i = 0; i < t; i++) { 
    int friendsNum = scanner.nextInt(); 
    int toDeleteNum = scanner.nextInt(); 

    // ... 

    for (int j = 0; j < friendsNum; j++) { 
     int current = scanner.nextInt(); 

     // ... 
    } 

    // ... 
} 

は、テストの一部が通過します。

しかし、多くの問題は、異なる問題のために、の制限時間を超えて、を超えます。 あなたのアルゴリズムが十分に効率的でないためです。 最悪の場合、削除する友達ごとに、友達のリストの最後まで繰り返されます。

異なるアルゴリズムが可能である：

• 各友人
  • ために、我々はまだ多くの友人を削除する必要があり、現在の友人が以前よりも人気ですが、以前
  • を削除スタックに現在の友人を追加する
さらに友人を削除する必要がありますが、最後のスタックをスタックから削除してくださいここでは

はそれの肉です：

for (int j = 0; j < friendsNum; j++) { 
    int current = scanner.nextInt(); 
    while (deleted < toDeleteNum && !stack.isEmpty() && stack.peek() < current) { 
     stack.pop(); 
     deleted++; 
    } 
    stack.push(current); 
} 
while (deleted < toDeleteNum) { 
    stack.pop(); 
    deleted++; 
} 

Answer 2

あなたが取得しているエラーを共有することができればそれが役立つだろう。 あなたのbr.readLine()は、削除する友人数と友人数の両方を含む完全な行を読み上げており、それを解析して数だけの友人を取得するとエラーが発生します。スキャナまたはbr.read()を使用して一度に1つの入力を読み、その問題が解決するかどうか確認してください。

Answer 3

この問題のためにTLEを取得しています。どうしてか分かりません ？

https://www.hackerearth.com/problem/algorithm/remove-friends-5/

#include <stdio.h> 
#include <stdlib.h> 
struct node 
{ 
    int popularity; 
    struct node *link; 
}*start=NULL; 

void delete(struct node **start,int d) 
{ 

    struct node *current = *start; 
    struct node *max = *start; 
    struct node *temp; 

    while (current != NULL && current->link != NULL && d) 
    { 
     if(current->link->popularity < max->popularity) 
     { 
      temp = current->link; 
      current->link = temp->link; 
      free(temp); 
      d--; 
     } 
      else 
     { 
      current = current->link; 
      max = current; 
     } 
    } 

} 

struct node* reverse(struct node *root) 
{ 
    struct node *temp; 
    if(root==NULL || root->link==NULL) 
     return root; 
    temp=reverse(root->link); 
    root->link->link=root; 
    root->link=NULL; 
    return temp; 
} 

int main() 
{ 
    struct node *tmp,*p; 
    int t,n,i,item,k,d; 
    scanf("%d",&t); 
    while(t--) 
    { 
     p=start=NULL; 
     scanf("%d",&n); 
     scanf("%d",&d); 
     for(i=0;i<n;i++) 
     { 
      scanf("%d",&item); 
      tmp=(struct node *)malloc(sizeof(struct node)); 
      tmp->popularity=item; 
      tmp->link=NULL; 
      if(start==NULL) 
       start=tmp; 
      else 
      { 
       p=start; 
       while(p->link) 
        p=p->link; 
       p->link=tmp; 
      } 
     } 
     start=reverse(start); 
     delete(&start,d); 
     start=reverse(start); 
     p=start; 
     while(p!=NULL) 
     { 
      printf("%d ",p->popularity); 
      p=p->link; 
     } 
     printf("\n"); 
    } 

    return 0; 
}