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

Jaguar 发表于 Dev

美洲虎

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

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

获得博士学位后，克里斯蒂（Christie）在她的大学成为了名人，她的Facebook个人资料充满了朋友的要求。克里斯蒂（Christie）是个很漂亮的女孩，她接受了所有要求。

现在，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个朋友后，打印代表Christie朋友的受欢迎程度的NK号。

注意删除确切的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();
}}

亚诺斯

您读取输入数据的方式存在缺陷：您的实现假设每行一个整数，但这与问题描述不匹配：

每个测试用例的第一行包含N，科视Christie当前拥有的朋友数和K，科视Christie决定删除的朋友数。接下来的几行包含了她的朋友的受欢迎程度，但被空格隔开了。

如果不使用的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++;
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。