莉莉丝游戏笔试记录

1题重排链表。

时间复杂度O(n)，空间复杂度O(1)

class ListNode {
  int val;
  ListNode next = null;
  public ListNode(int val) {
    this.val = val;
  }
}


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode formatList (ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode tail = head;
        ListNode p = head.next;
        ListNode next = null;
        while(p != null) {
            tail.next = p;
            tail = p;
            p = p.next;
            if (p == null) {
                break;
            }
            next = p.next;
            p.next = head;
            head = p;
            p = next;
        }
        tail.next = null;
        return head;
    }
}

2题有约束的链表排序
时间复杂度O(n*logk) ，空间复杂O(n)，其中n为链表长度，k为链表中不重复的数字个数。

import java.util.*;

class ListNode {
  int val;
  ListNode next = null;
  public ListNode(int val) {
    this.val = val;
  }
}


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode sortList (ListNode head) {
        if (head == null) {
            return null;
        }
        TreeMap<Integer, LinkedList<ListNode>> sortedMap = new TreeMap<>();
        ListNode p = head;
        while(p != null) {
            List<ListNode> list = sortedMap.computeIfAbsent(p.val, k -> new LinkedList<>());
            list.add(p);
            p = p.next;
        }
        head = null;
        while(!sortedMap.isEmpty()) {
            Iterator<LinkedList<ListNode>> it = sortedMap.values().iterator();
            while (it.hasNext()) {
                LinkedList<ListNode> list = it.next();
                if (head == null) {
                    head = p = list.removeFirst();
                } else {
                    p.next = list.removeFirst();
                    p = p.next;
                }
                if (list.isEmpty()) {
                    it.remove();
                }
            }
        }
        if (p != null) {
            p.next = null;
        }
        return head;
    }
}

3题消息队列。

时间复杂度O(n)，空间复杂度O(n)，其中获取队首消息、获取指定类型的消息、添加消息单次操作的时间复杂度都是O(1)。

消息队列设计思想：使用一个双端队列messageQueue存放消息，再使用一个哈希表将指定类型消息串联起来，键为消息类型，值为队列。

添加消息：将消息添加到messageQueue，同时添加也添加到哈希表中的特定队列中。由于存的都是引用变量，所以每个消息并没有占两份内存。

获取消息：

（1）当消息类型为0，也就是获取messgeQueue队首的消息时，将消息类型置为队首消息的类型；此时获队首消息转换成了获取特定类型的第一个消息。
（1）获取指定类型的消息。从哈希表中取出消息体，然后维护好messageQueue双端队列。

莉莉丝游戏笔试记录

全站热榜