java - Hackerearth 删除好友 : Runtime Error - NZEC

Question

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

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

获得博士学位后，克里斯蒂已成为大学里的名人，她的 Facebook 个人资料上充满了好友请求。作为一个好女孩，克里斯蒂接受了所有的请求。

现在库尔迪普嫉妒她从其他男人那里得到的所有关注，所以他要求她从她的 friend 列表中删除一些男人。为了避免“场面”，克里斯蒂决定从她的 friend 列表中删除一些 friend ，因为她知道她所拥有的每个 friend 的受欢迎程度，所以她使用以下算法来删除 friend 。

算法删除(好友):

        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 当前拥有的 friend 数量)和 K(Christie 决定删除的 friend 数量)。下一行包含她 friend 的受欢迎程度，并用空格分隔。

输出:对于每个测试用例，打印 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

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

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();

        // ...
    }

    // ...
}

修复输入解析后，一些测试将通过。

但是由于另一个问题，其中许多仍然会失败，超出了时间限制。那是因为你的算法不够高效。在最坏的情况下，对于每个要删除的好友，它都会迭代，直到好友列表末尾。

可能有不同的算法:

• 对于每一位 friend
  • 虽然我们还需要删除更多好友，并且当前好友比之前的好友更受欢迎，但删除之前的好友
  • 将当前好友添加到堆栈
• 虽然我们仍然需要删除更多 friend ，但请从堆栈中删除最后一个

这是它的核心内容:

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