class Solution {
public:
int adventureCamp(vector<string>& expeditions) {
}
};
LCP 73. 探险营地
探险家小扣的行动轨迹，都将保存在记录仪中。expeditions[i] 表示小扣第 i 次探险记录，用一个字符串数组表示。其中的每个「营地」由大小写字母组成，通过子串 -> 连接。
例："Leet->code->Campsite"，表示到访了 "Leet"、"code"、"Campsite" 三个营地。
expeditions[0] 包含了初始小扣已知的所有营地；对于之后的第 i 次探险(即 expeditions[i] 且 i > 0)，如果记录中包含了之前均没出现的营地，则表示小扣 新发现 的营地。
请你找出小扣发现新营地最多且索引最小的那次探险，并返回对应的记录索引。如果所有探险记录都没有发现新的营地，返回 -1
注意：
0。示例 1：
输入：
expeditions = ["leet->code","leet->code->Campsite->Leet","leet->code->leet->courier"]输出：
1解释： 初始已知的所有营地为 "leet" 和 "code" 第 1 次，到访了 "leet"、"code"、"Campsite"、"Leet"，新发现营地 2 处："Campsite"、"Leet" 第 2 次，到访了 "leet"、"code"、"courier"，新发现营地 1 处："courier" 第 1 次探险发现的新营地数量最多，因此返回
1
示例 2：
输入：
expeditions = ["Alice->Dex","","Dex"]输出：
-1解释： 初始已知的所有营地为 "Alice" 和 "Dex" 第 1 次，未到访任何营地； 第 2 次，到访了 "Dex"，未新发现营地； 因为两次探险均未发现新的营地，返回
-1
示例 3：
输入：
expeditions = ["","Gryffindor->Slytherin->Gryffindor","Hogwarts->Hufflepuff->Ravenclaw"]输出：
2解释： 初始未发现任何营地； 第 1 次，到访 "Gryffindor"、"Slytherin" 营地，其中重复到访 "Gryffindor" 两次， 因此新发现营地为 2 处："Gryffindor"、"Slytherin" 第 2 次，到访 "Hogwarts"、"Hufflepuff"、"Ravenclaw" 营地； 新发现营地 3 处："Hogwarts"、"Hufflepuff"、"Ravenclaw"； 第 2 次探险发现的新营地数量最多，因此返回
2
提示：
1 <= expeditions.length <= 10000 <= expeditions[i].length <= 1000原站题解
java 解法, 执行用时: 178 ms, 内存消耗: 49.3 MB, 提交时间: 2023-04-23 10:36:21
class Solution {
public int adventureCamp(String[] expeditions) {
Set<String> set = new HashSet<>();
int ans = -1;
int max = 0;
String[] spilt = expeditions[0].split("->");
for(String s: spilt) {
set.add(s);
}
for(int i=1; i<expeditions.length; ++i){
int cnt = 0;
spilt = expeditions[i].split("->");
for(String s: spilt) {
if(!s.equals("") && !set.contains(s)) {
set.add(s);
++cnt;
}
}
if(cnt > max) {
ans = i;
max = cnt;
}
}
return ans;
}
}
golang 解法, 执行用时: 128 ms, 内存消耗: 10.8 MB, 提交时间: 2023-04-23 10:35:57
func adventureCamp(a []string) int {
vis := map[string]bool{}
for _, s := range strings.Split(a[0], "->") { // 这样可能会把空串插入，但是没有关系
vis[s] = true
}
maxCnt, ans := 0, -1
for i := 1; i < len(a); i++ {
if a[i] == "" {
continue
}
cnt := 0
for _, s := range strings.Split(a[i], "->") {
if !vis[s] {
vis[s] = true
cnt++
}
}
if cnt > maxCnt {
maxCnt, ans = cnt, i
}
}
return ans
}
python3 解法, 执行用时: 168 ms, 内存消耗: 24.1 MB, 提交时间: 2023-04-23 10:35:35
# 模拟
class Solution:
def adventureCamp(self, a: List[str]) -> int:
vis = set(a[0].split('->')) # 这样可能会把空串插入，但是没有关系
max_cnt, ans = 0, -1
for i in range(1, len(a)):
if a[i] == "": continue
cnt = 0
for t in a[i].split('->'):
if t not in vis:
vis.add(t)
cnt += 1
if cnt > max_cnt:
max_cnt, ans = cnt, i
return ans