Java:前缀字符串的棘手排序(ArrayLists)

Question

(无需任何网络知识.这纯粹是字符串和列表).

假设我有一个函数,一个接受String IPv4点缀地址列表的函数,并按升序对它们进行排序.(不是按字母顺序排列的,真正的ip长格式排序).我们称之为:

public static ArrayList<String> sortListOfIpv4s(ArrayList<String> unsortedIPv4s);

此功能已正常工作.给出一个输入:

192.168.1.1, 8.8.8.8, 4.5.6.7, 244.244.244.244, 146.144.111.6

它将输出列表:

4.5.6.7, 8.8.8.8, 146.144.111.6, 192.168.1.1, 244.244.244.244

(让我们不讨论它是否应该修改列表或返回一个新列表.它只返回一个新列表.此外,由于种种原因,该函数无法修改.)

但是,我的输入列表如下所示:

e192.168.1.1, f8.8.8.8, e4.5.6.7, f244.244.244.244, e146.144.111.6

当我删除前缀(只有一个e或f,非NECESSARILY交替)并创建一个干净的数组传递给排序函数时,我丢失了前缀信息.我想要的是类型的输出:

e4.5.6.7, f8.8.8.8, e146.144.111.6, e192.168.1.1, f244.244.244.244

基本上,在排序之前,对于未排序列表中的每个元素存在任何前缀,需要将相同的前缀添加回排序列表中的元素.

注意事项:

• IP地址可以在原始列表中重复,最多两次
• 重复两次时,两个元素中的每一个都将具有相同的前缀,保证
• 排序算法不会删除重复项.

有点算法帮助吗？(请记住,我们已经有一个可以对干净的IPv4 String arraylists进行排序的函数).

Answer 1

在将前缀传递给排序函数之前，请勿删除前缀。相反，在该sortListOfIpv4s方法中，始终使用 比较字符串s.substring(1)，这将为您提供不带前缀的整个字符串，并将其添加s到结果排序数组中。

如果sortListOfIpv4s是一个黑盒，并且需要传递无前缀字符串，那么您可以预先将前缀缓存在 fromMap中prefix-free IP -> prefix：

Map<String, String> prefixMap = new HashMap<String, String>();
for (String ip : unsortedIPv4s) {
  prefixMap.put(ip.substring(1), ip.substring(0, 1));
}

然后对前缀进行排序并恢复Map：

List<String> sortedIPV4s = sortListOfIpv4s(unsortedIPv4s);
for (String ip : sortedIPV4s) {
  String prefix = prefixMap.get(ip);
  String originalIp = prefix + ip;
}