莉莉丝游戏笔试记录
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）获取指定类型的消息。从哈希表中取出消息体，然后维护好messageQueue双端队列。
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
StringBuilder buf = new StringBuilder();
MessageQueue messageQueue = new MessageQueue();
while(n-- > 0) {
String opt = sc.next();
if (opt.equals("in")) {
messageQueue.put(sc.nextInt(), sc.next());
} else if (opt.equals("out")) {
buf.append(messageQueue.get(sc.nextInt())).append("\n");
}
}
System.out.println(buf);
}
}
class MessageQueue {
HashMap<Integer, LinkedList<Entity>> hashMap = new HashMap<>();
Entity head, tail;
public String get(int type) {
if (type == 0) {
if (head == null) {
return "-1";
}
type = head.type;
}
if (!hashMap.containsKey(type)) {
return "-1";
}
LinkedList<Entity> list = hashMap.get(type);
Entity entity = list.removeFirst();
if (list.isEmpty()) {
hashMap.remove(type);
}
if (head == entity && tail == entity) {
head = tail = null;
} else if (head == entity) {
removeHead();
} else if (entity == tail) {
removeTail();
} else {
entity.pre.next = entity.next;
entity.next.pre = entity.pre;
}
return entity.message;
}
public void put(int type, String value) {
Entity entity = new Entity(type, value);
if (tail == null) {
head = tail = entity;
} else {
entity.pre = tail;
tail.next = entity;
tail = entity;
}
LinkedList<Entity> list = hashMap.computeIfAbsent(type, k->new LinkedList<>());
list.add(entity);
}
private void removeHead() {
if (head == tail) {
head = tail = null;
} else {
head = head.next;
head.pre = null;
}
}
private void removeTail() {
if (head == tail) {
head = tail = null;
} else {
tail = tail.pre;
tail.next = null;
}
}
private static class Entity {
int type;
String message;
Entity pre;
Entity next;
public Entity(int type, String message) {
this.type = type;
this.message = message;
}
}
} 
