标题简介与问题概述
探险家小扣在每次探险后都会留下一串记载，记载中包含了他访问过的营地名单。这些营地名以字符串形式出现，通过”->”符号衔接。咱们的使命是剖析小扣的探险记载，找出他在哪一次探险中发现了最多的新营地。
探险记载是一个字符串数组，其中每个字符串代表一次探险的途径。初始探险的记载包含了小扣已知的一切营地。在随后的探险中，假如记载包含了新的营地，那么这些营地被视为新发现。咱们需求确定在哪次探险中，小扣发现了最多的新营地，并回来那次探险的索引。假如一切探险都没有发现新营地，咱们则回来-1。
在这个问题中，每个营地都是独一无二的，即使是大小写不同也被视为不同的营地。每个营地的称号都对错空的，确保了至少存在一个字符。
此问题的挑战在于怎么有效地解析这些记载，并准确地辨认出新发现的营地。
原始处理计划剖析
为了找出小扣在哪次探险中发现了最多的新营地，咱们需求对探险记载进行剖析。原始的处理计划可能是按照以下步骤进行：
- 初始化一个调集originCamp，用于存储第一次探险已知的一切营地。
- 遍历expeditions数组，从第二个元素开始，因为第一个元素代表的是已知营地。
- 关于每个后续的探险记载，使用字符串切割操作，将营地称号切割开来。
- 遍历切割后得到的营地称号数组，检查每个称号是否在originCamp调集中。
- 假如发现了不在调集中的新营地，将其添加到调集中，并更新本次探险的新发现营地计数。
- 记载新发现营地数量最多的探险索引和对应的新营地数量。
完结遍历后，回来新发现营地数量最多的探险索引，假如没有新发现的营地，则回来-1。
这个计划的首要问题在于，它需求执行大量的字符串切割操作和调集成员检查，这在探险记载较多或营地称号较长时，会导致功率低下。
参阅代码如下：
class Solution {
public int adventureCamp(String[] expeditions) {
// 关于起点的地址树立HashSet
Set<String> originCamp = new HashSet<>();
if (expeditions[0].length() > 0) {
String[] camps = expeditions[0].trim().split("->");
for (String camp : camps) {
originCamp.add(camp);
}
}
// 记载结果
int res = -1;
int mx = 0;
for (int i = 1; i < expeditions.length; i ) {
if (expeditions[i].length() == 0) {
continue;
}
String[] camps = expeditions[i].trim().split("->");
int hasCamp = 0;
for (String camp : camps) {
// 若既不在开始营地，也不在访问过的营地
boolean originFlag = originCamp.contains(camp);
if (!originFlag) {
hasCamp ;
originCamp.add(camp);
}
}
if (hasCamp > mx) {
res = i;
mx = hasCamp;
}
}
return res;
}
}
优化计划：哈希值
在处理“探险营地”问题的原始处理计划中，咱们直接操作字符串来辨认新发现的营地。这种方法在数据量较小的情况下是可行的，但随着数据量的增加，字符串比较的开销也随之增大，这直接影响了算法的功能。为了提高功率，咱们将处理计划从直接处理字符串转变为处理哈希值。
哈希值处理的优势
处理哈希值比较于处理完整的字符串有两个首要优势：
- 功能提升：哈希值一般为整数，整数之间的比较远比长字符串之间的比较愈加高效。
- 空间节省：在存储和操作时，整数占用的空间远小于长字符串。
应对哈希抵触
但是，直接使用标准的hashCode方法可能会引发哈希抵触，即不同的字符串可能发生相同的哈希值。以Java默许的hashCode算法为例。咱们给出代码：
public int hashCode() {
int h = hash; // 默以为0
if (h == 0 && value.length > 0) {
char val[] = value; // 字符串的字符数组
for (int i = 0; i < value.length; i ) {
h = 31 * h val[i];
}
hash = h;
}
return h;
}
在本题中，选用默许的hashCode方法会导致hash抵触。为了处理这个问题，咱们选用了自定义哈希算法。
应用自定义哈希算法
咱们将选用以下步骤以应用自定义哈希算法：
- 设计一个自定义哈希函数，该函数能够依据营地称号生成唯一的哈希值。
- 创建一个哈希表来存储营地称号与其哈希值的映射。
- 在处理探险记载时，首先通过自定义哈希函数核算每个营地称号的哈希值。
- 使用核算出的哈希值来更新已知营地调集，并统计新发现的营地数量。
- 依据新发现的营地数量更新记载，并维护最多新营地发现的探险索引。
- 遍历完结后，回来新营地发现最多的探险索引，若无新发现，则回来-1。
改善后的代码如下：
class Solution {
// 获取字符串的哈希值，以'->'切割
private List<Long> getStringHshs(String str) {
int i = 0;
long hsh = 0;
char[] chs = str.toCharArray();
List<Long> hshs = new ArrayList<>();
if (chs.length > 0) {
for (; i < chs.length; ) {
if (chs[i] == '-') {
i = 2;
hshs.add(hsh);
hsh = 0;
} else {
hsh = hsh * 199 chs[i];
i ;
}
}
}
if (hsh != 0) {
hshs.add(hsh);
}
return hshs;
}
public int adventureCamp(String[] expeditions) {
// 关于起点的地址树立HashSet
Set<Long> originCamp = new HashSet<>();
if (expeditions[0].trim().length() > 0) {
List<Long> hshs = getStringHshs(expeditions[0]);
for (Long hsh : hshs) {
originCamp.add(hsh);
}
}
// 记载结果
int res = -1;
int mx = 0;
for (int i = 1; i < expeditions.length; i ) {
if (expeditions[i].length() == 0) {
continue;
}
List<Long> hshs = getStringHshs(expeditions[i]);
System.out.println();
int hasCamp = 0;
for (Long hsh : hshs) {
// 若既不在开始营地，也不在访问过的营地
boolean originFlag = originCamp.contains(hsh);
if (!originFlag) {
hasCamp ;
originCamp.add(hsh);
}
}
if (hasCamp > mx) {
res = i;
mx = hasCamp;
}
}
return res;
}
}
总结
通过引入自定义哈希算法，在处理时刻上有了明显的改变。
原始计划处理探险记载的时刻为187毫秒，而通过优化后，时刻缩短至96毫秒。这一改善减少了近一半的执行时刻，证明了优化的有效性。
