Hackerearth 删除好友：运行时错误 - NZEC

Question

我被这个问题困住了。我的代码通过了示例中给出的所有测试用例，但代码中存在一些错误。错误之处还请指出。

问题陈述（https://www.hackerearth.com/problem/algorithm/remove-friends-5）

获得博士学位后，克里斯蒂在她的大学里成了名人，她的 facebook 个人资料上满是朋友请求。作为一个乖乖女，克里斯蒂接受了所有的要求。

现在 Kuldeep 嫉妒她从其他男人那里得到的所有关注，所以他要求她从她的朋友列表中删除一些男人。为了避免 'scene'，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 个测试用例。每个测试用例的第一行包含 N，Christie 当前拥有的朋友数量和 K，Christie 决定删除的朋友数量。下一行包含由 space.

分隔的她朋友的受欢迎程度

输出：对于每个测试用例打印N-K个数字，代表删除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

如果您能分享您遇到的错误，将会有所帮助。您的 br.readLine() 正在读取包含朋友数量和要删除的朋友数量的完整行，并对其进行解析以仅获取朋友数量将给出您的错误。尝试使用 Scanner 或 br.read() 一次读取一个输入，看看是否能解决您的问题。

Answer 2

我正在为这个问题获取 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;
}

Answer 3

您读取输入数据的方式有缺陷：您的实现假定每行一个整数，但这与问题描述不符：

First line of each test case contains N, the number of friends Christie currently has and K ,the number of friends Christie decides to delete. Next lines contains popularity of her friends separated by space.

而不是使用 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++;
}

Hackerearth 删除好友：运行时错误 - NZEC

Hackerearth Remove Friends: Runtime Error - NZEC

java

puzzle

runtime-error

linked-list