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