算法题：不同的子序列
最近我刷到一个有点意思的算法题。题目大概是这样的：
有一个用户行程问题，输入是多个用户的行程数据，每条行程包含用户ID、出发地和目的地。我们需要根据这些行程，把同一个用户的所有行程串起来，输出每个用户完整的行程链条。行程数据可能是无序的，需要自己动手整理好。
题目虽然看起来简单，但里面有几个需要特别注意的点：
行程无序，需要排序； 行程可能不连续，需要“拼接”； 每个用户的行程独立处理，不能串了线。
为了实现这个目标，我的思路是：用一个哈希表，把每个行程的出发地和目的地映射起来，然后利用图的遍历来拼出完整的路径链条。既然是聊代码，那我就直接上伪代码来解释一下：
import java.util.*;
public class UserTrip {
public static void main(String[] args) {
// 输入行程数据
List<String[]> trips = Arrays.asList(
new String[]{"User1", "A", "B"},
new String[]{"User1", "B", "C"},
new String[]{"User1", "C", "D"},
new String[]{"User2", "X", "Y"},
new String[]{"User2", "Y", "Z"}
);
// 结果存储
Map<String, List<String>> userItinerary = new HashMap<>();
// Step 1: 整理每个用户的行程
for (String[] trip : trips) {
String user = trip[0];
String from = trip[1];
String to = trip[2];
userItinerary.putIfAbsent(user, new ArrayList<>());
userItinerary.get(user).add(from + "->" + to);
}
// Step 2: 输出每个用户完整行程
for (String user : userItinerary.keySet()) {
System.out.println("User: " + user);
System.out.println("Itinerary: " + userItinerary.get(user));
}
}
}
这个伪代码基本实现了需求，但我觉得还有提升空间。比如，我们可以用更优雅的方式实现行程拼接，让数据结构更简洁。
比如，把每个用户的行程整理成链表结构，然后用拓扑排序的思路来拼接完整路径。看起来是小题大做，其实是在用更“技术化”的思路解决问题，提升代码的鲁棒性。💪
如果再刁钻一点，比如数据有可能是“断开的”（比如User1的行程数据里突然少了段B到C的路），那就需要在拼接过程中检查路径的完整性。
对于这种情况，我们可以先构建一个邻接表，然后通过深度优先搜索（DFS）来探测路径。改进后的代码示例：
// Step 1: 构建邻接表
Map<String, String> fromToMap = new HashMap<>();
Set<String> destinations = new HashSet<>();
for (String[] trip : trips) {
String from = trip[1];
String to = trip[2];
fromToMap.put(from, to);
destinations.add(to);
}
// Step 2: 找起点
String start = null;
for (String from : fromToMap.keySet()) {
if (!destinations.contains(from)) {
start = from;
break;
}
}
// Step 3: 拼接路径
StringBuilder fullPath = new StringBuilder();
while (start != null) {
fullPath.append(start).append("->");
start = fromToMap.get(start);
}
System.out.println("User1 Full Path: " + fullPath.substring(0, fullPath.length() - 2));
这段代码解决了无序和断裂的情况，用到了邻接表和简单的图遍历，能保证拼接出来的路径是完整的。
总的来说，这题有点像我们平时开发中的“数据清洗”工作。原始数据很可能是混乱的，需要自己理清逻辑和关系，才能输出有用的信息。
对编程、职场感兴趣的同学，可以链接我，微信：coder301 拉你进入“程序员交流群”。
