LeetCode刷题笔记——LCP 73探险营地
内容提要
这篇文章介绍了LeetCode刷题笔记中的LCP 73探险营地问题。文章首先讲述了原始处理计划的问题，即字符串切割操作和调集成员检查的低效率。然后介绍了使用哈希值处理的优势，包括功能提升和空间节省。接着讲解了哈希抵触问题，并提出了应用自定义哈希算法的方法。最后总结了通过优化后的代码，执行时刻减少了近一半的有效性。
延伸解读
字符串切割与集合检查的性能瓶颈
原始方案每次处理探险记录时，都需对字符串进行切割，并将每个营地名与已知集合进行成员检查。当探险记录数量多或营地名称较长时，字符串比较和切割的开销会显著增加，导致整体效率低下。这种直接操作字符串的方式在数据量增大时，性能下降尤为明显。
哈希值处理的优势与潜在风险
将营地名转换为哈希值后，比较和存储都从字符串变为整数，提升了比较效率并节省了空间。但标准hashCode方法可能产生哈希冲突，即不同字符串得到相同哈希值，这会导致错误判断。因此，文章提出使用自定义哈希算法来避免冲突，确保每个营地名对应唯一哈希值。
自定义哈希算法的实现要点
自定义哈希函数通过遍历字符并乘以特定基数（如199）来生成哈希值，同时处理分隔符“->”以分割营地名。在遍历探险记录时，先计算每个营地名的哈希值，再用哈希值更新已知营地集合并统计新发现数量。这种方法避免了字符串直接比较，同时降低了哈希冲突概率。
优化效果与适用场景
优化后代码执行时间从187毫秒缩短至96毫秒，减少近一半，证明了哈希值处理的有效性。这种优化尤其适用于探险记录多、营地名称长的场景。但需注意，自定义哈希算法仍可能冲突，只是概率较低；若对正确性要求极高，可考虑进一步校验或使用更复杂的哈希方案。
Q&A
探险营地问题的主要目标是什么？
主要目标是找出探险中发现最多新营地的索引。
原始处理计划中存在哪些效率问题？
原始处理计划需要大量字符串切割和成员检查，导致效率低下。
使用哈希值处理有什么优势？
哈希值处理相比字符串处理有功能提升和空间节省的优势。
如何应对哈希抵触问题？
可以通过自定义哈希算法生成唯一哈希值来避免哈希抵触。
优化后的代码执行时刻有何变化？
优化后的代码执行时刻从187毫秒缩短至96毫秒，减少了近一半的执行时刻。
自定义哈希算法的应用步骤是什么？
设计自定义哈希函数、创建哈希表、计算哈希值并更新已知营地集合。
