Hackerearth刪除朋友：運行時錯誤 - NZEC

Question

我被困在這個問題上。我的代碼通過了示例中給出的所有測試用例，但代碼中存在一些錯誤。請指出錯誤。

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

讓她的博士學位後，克里斯蒂已經成爲她的大學名人，她的Facebook個人資料是完整的好友申請。作爲她的好女孩，克里斯蒂已經接受了所有的要求。

現在Kuldeep嫉妒她從其他人那裏得到的所有關注，所以他讓她從她的朋友名單中刪除一些人。 爲了避免「場景」，科視決定從朋友列表中刪除一些朋友，因爲她知道每個朋友的受歡迎程度，她使用以下算法刪除朋友。

算法刪除（朋友）：

 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編號。每個測試案例的第一行包含N，科視Christie目前擁有的朋友數量以及K，Christie決定刪除的朋友數量。下一行包含她的朋友的空間分隔的流行。

輸出： 對於每個測試用例，打印表示克里斯蒂朋友在刪除K朋友之後流行的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

你讀的輸入數據的方式是有缺陷的： 你實現假定每行， 一個整數，但這種不匹配問題描述：

第一線每個測試案例包含N，科視Christie目前擁有的朋友數量以及科視Christie決定刪除的朋友數量K.下一行包含她的朋友的空間分隔的流行。

而不是使用一個BufferedReader， 的，我建議使用Scanner而嘗試，它更簡單， 是這樣的：

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()一次讀取一個輸入，看看是否可以解決您的問題。

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; 
}