🍎道阻且长，行则将至。🍓

🌻算法，不如说它是一种思考方式🍀

算法专栏： 👉🏻123

一、🌱2023-spring 2.探险营地

• 题目描述：探险家小扣的行动轨迹，都将保存在记录仪中。expeditions[i] 表示小扣第 i 次探险记录，用一个字符串数组表示。其中的每个「营地」由大小写字母组成，通过子串 -> 连接。
  例："Leet->code->Campsite"，表示到访了 “Leet”、“code”、“Campsite” 三个营地。
  expeditions[0] 包含了初始小扣已知的所有营地；对于之后的第 i 次探险(即 expeditions[i] 且 i > 0)，如果记录中包含了之前均没出现的营地，则表示小扣 新发现 的营地。
  请你找出小扣发现新营地最多且索引最小的那次探险，并返回对应的记录索引。如果所有探险记录都没有发现新的营地，返回 -1

• 来源：力扣（LeetCode）

• 难度：中等

• 注意：
  大小写不同的营地视为不同的营地；
  营地的名称长度均大于 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

🌴解题

字符串的处理

这个应该算是简单题，不过当时题看错了卡了好久~

最简单做法就是对字符串数组的每一个字符串进行拆分：找 - 或者 ->，字符串拆分加入到集合中 HashSet ，不会出现重复。
这里我们需要两个集合，一个集合 aSet 保存之前到访过的所有营地，另一个集合 bSet保存当前字符串所记录的到访的营地，看集合 aSet 中有没有集合 bSet 的元素，记为 k。于是这一次（第 i 次）的到访记录中新营地数 n 为：aSet 的大小 - k，当 n > num && n != 0 时就让 num=n，index = i (num初始赋值为 -1)。
按顺序遍历完最后返回最大新营地数的记录下标 index。

class Solution {public int adventureCamp(String[] expeditions) {/* 处理第一个*/int ans=-1;// 最大新到访的个数// 拆解字符串到hashsetSet<String> setstr0=new HashSet<>();int count0;if(expeditions[0].length()!=0){count0=1;for (int i = 0; i < expeditions[0].length(); i++) {if (expeditions[0].charAt(i) == '-')count0++;}int bigen = 0, end;for (int i = 0; i < count0; i++) {//取出已知的营地end = bigen;while (end < expeditions[0].length() && expeditions[0].charAt(end) != '-') {end++;}setstr0.add(expeditions[0].substring(bigen, end));bigen = end + 2;}}int index=10000;//记录下标最小for (int i = 1; i < expeditions.length; i++) {//看当前有几个 包含前面的/* 处理第i个记录*/if(expeditions[i].length()==0)continue;int countexp=1;//有多少个地方for (int j = 0; j < expeditions[i].length(); j++) {if (expeditions[i].charAt(j) == '-')countexp++;}Set<String> setstr=new HashSet<>();int bigen = 0, end;for (int j = 0; j < countexp; j++) { //取出记录i到达的营地end = bigen;while (end < expeditions[i].length() && expeditions[i].charAt(end) != '-') {end++;}setstr.add(expeditions[i].substring(bigen, end));bigen = end + 2;}//比较 setstr0  - setstr还要把 setstr的内容加入setstr0count0=setstr0.size();int countn=setstr.size();if(count0==0){//初始营地为空if(ans<countn){//当前 new到访记录更多ans=countn;index=i;}}else{int k=0;for (String s : setstr) {//看初始到访记录是否存在于当前到访记录if(setstr0.contains(s))k++;}if(countn-k <= 0)//当前new到访记录 0continue;if(ans<countn-k){//当前 new到访记录更多ans=countn-k;index=i;}}setstr0.addAll(setstr);}if(index==10000)//不变，表示没新的到访地return -1;return index;}
}

过啦！

返回第一页。☝

☕物有本末，事有终始，知所先后。🍭

🍎☝☝☝☝☝我的CSDN☝☝☝☝☝☝🍓