在看雪论坛下载的，谁有兴趣逆向下？
https://pwrliang.com/share/MFSocket.apk

没错，我现在就在写 Hive SQL，就是 SQL boy …

然而不遍历怎么知道有重复，至少的扫描一遍吧，用 set/bitmap 记录访问过的元素来判断是否重复。这种又不是什么复杂度高的操作，我觉得没必要深思…

因为你使用 BFS，题目给的例子中：
1--2
| |
4--3

1 入队，1 出队，然后 2，4 入队；然后 2 出队，1 访问过了跳过，3 入队；然后 4 出队，1 访问过了跳过，3 入队。
此时，你发现队列存在两个“ 3 ”，造成了重复访问。因此，你在入队前应该检查入队的元素是否访问过。
把你的代码：
for(Node neighbor : current.neighbors)
if(!map.keySet().contains(neighbor))
queue.offer(neighbor);
改成：
for (Node neighbor : current.neighbors)
if (!map.keySet().contains(neighbor)) {
// 检查是否访问过，即可 AC
map.put(neighbor, new Node(neighbor.val, new ArrayList(neighbor.neighbors.size())));
queue.offer(neighbor);
}

@WebKit 你这个真的很快哈

我用的 vultr+cloudflare，你试试速度如何？
https://blog.pwrliang.com

@greenlake 一到公司就迫不及待，花了有半小时吧，写出来了。包含一个编码、测试，用了 Idea 做调试，直接白板写估计够呛。

-------------------
```
import java.util.*;

class Solution {
class Node {
Node next;
int val;

Node() {

}

Node(int val) {
this.val = val;
}

@Override
public String toString() {
return val + (next != null ? "->" + next.toString() : "");
}
}

boolean check(Node head) {
Node p = head.next;

while (p.next != null) {
if (p.val > p.next.val) {
return false;
}
p = p.next;
}

return true;
}

Node asNode(int[] array) {
Node head = new Node();
Node p = head;

for (int e : array) {
p.next = new Node(e);
p = p.next;
}

return head;
}

void sort(Node head) {
if (head == null || head.next == null)
return;

Node prev = head;
Node curr = prev.next;

while (prev.next != null) {
Node p = head;
boolean changed = false;
while (p != curr) {
if (p == head && curr.val < p.next.val || curr.val >= p.val && curr.val < p.next.val) {
prev.next = curr.next;
Node tmp = p.next;
p.next = curr;
curr.next = tmp;
changed = true;
break;
}
p = p.next;
}

if (changed) {
curr = prev.next;
} else {
prev = prev.next;
curr = prev.next;
}
}
}
}


测试：

Solution solution = new Solution();
{
Solution.Node head = solution.asNode(new int[]{5, 1, 5, 3, 4, 2});
solution.sort(head);
assert solution.check(head);
}

{
Solution.Node head = solution.asNode(new int[]{1});
solution.sort(head);
assert solution.check(head);
}

for (int times = 0; times < 1000; times++) {
int len = 2000;
int[] test = new int[len];
Random random = new Random();
for (int i = 0; i < len; i++)
test[i] = random.nextInt();

Solution.Node head = solution.asNode(test);
solution.sort(head);
assert solution.check(head);
}

```

我认为大多场景都是申请空间，然后灌满，再读取多次。主动填 0，会不会在大多数场景都影响性能？

我觉得给我半个点能写出来…我中午午休试试

是 single source 吗，是的话用 B-F 算法求 shortest path，然后用大小为 k 的 heap 维护最短路径，时间复杂度 O(VE)，我在 GPU 上做过这个算法，对于百万级的顶点，亿级的边能够在 1000 毫秒内算完，不知道你这个算法是刷题用还是实际应用…

直接回：“不在了”

你说的是字符串，不是子串吧？把*替换成 0 最小，123005608，替换成 9 最大,123995698。枚举 000-999，填到对应的三个*上不就可以了？

之前用过，后来因为长文字贴渲染很慢，就卸载掉了…