5.27携程笔试后台开发2道算法题
感觉题目不是很难，应该是在原题上进行修改的变种题，不过我都没AK😅，只做出了0.8+1，许愿有个面试机会吧！（春招到现在一个offer都没有，我太难了
）
）
t1：火车站中转方案
思路：建图，dfs搜索到终点y，去掉x，y首尾节点，路径经过的点个数不超过k就将路径节点序列化成字符串放到set去重即可，同时要注意不能访问相同的节点
这题有ac的大佬欢迎评论区讨论一下解法🤩
package xiecheng.t1;
import java.util.*;
public class Main {
static Set<String> set;
static int x, y;
static boolean[] vis;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
in.nextLine();
String str = in.nextLine();
String[] arr = str.split(" ");
List<Integer>[] link = new ArrayList[n + 1];
vis = new boolean[n + 1];
for (int i = 1; i <= n; i++) {
link[i] = new ArrayList<>();
}
int len = arr.length;
for (int i = 0; i < len; i++) {
String[] split = arr[i].split(",");
link[Integer.parseInt(split[0])].add(Integer.parseInt(split[1]));
}
x = in.nextInt();
y = in.nextInt();
int k = in.nextInt();
set = new HashSet<>();
vis[x] = true;
dfs(x, k, link, new ArrayList<Integer>() {{
add(x);
}}, "" + x);
System.out.println(set.size());
}
static void dfs(int cur, int k, List<Integer>[] link, List<Integer> list, String str) {
if (cur == y && list.size() > 1 && list.size() - 2 <= k) {
//System.out.println(str);
set.add(str);
return;
}
for (int j = 0, siz = link[cur].size(); j < siz; j++) {
if (vis[link[cur].get(j)]) continue;
vis[link[cur].get(j)] = true;
list.add(link[cur].get(j));
dfs(link[cur].get(j), k, link, list, str + link[cur].get(j));
list.remove(list.size() - 1);
vis[link[cur].get(j)] = false;
}
}
}
t2：最小子序列
思路：类似力扣原题76题吧，用双指针做即可。
package xiecheng.t2;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
static int winner(int[] s, int[] t) {
Map<Integer, Integer> cnt1 = new HashMap<>();
Map<Integer, Integer> cnt2 = new HashMap<>();
int kind = 0, num;
for (int i = 0; i < t.length; i++) {
num = cnt1.getOrDefault(t[i], 0);
if (num == 0) kind++;
cnt1.put(t[i], num + 1);
}
int lt = 0, rt = 0, len = s.length, curKind = 0;
int res = len + 1, startIndex = 0;
while (true) {
while (rt < len && curKind < kind) {
num = cnt2.getOrDefault(s[rt], 0);
if (cnt1.getOrDefault(s[rt], 0) == num + 1) curKind++;
cnt2.put(s[rt], num + 1);
rt++;
}
if (curKind < kind) break;
if (rt - lt < res) {
res = rt - lt;
startIndex = lt;
}
num = cnt2.getOrDefault(s[lt], 0);
if (cnt1.getOrDefault(s[lt], 0) == num) curKind--;
cnt2.put(s[lt], num - 1);
lt++;
}
return res == len + 1 ? 0 : startIndex + 1;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int res;
Scanner scanner = new Scanner(System.in);
String line = scanner.nextLine();
String[] values = line.split(",");
int[] s = new int[values.length];
for (int i = 0; i < values.length; i++) {
s[i] = Integer.parseInt(values[i]);
}
line = scanner.nextLine();
values = line.split(",");
int[] t = new int[values.length];
for (int i = 0; i < values.length; i++) {
t[i] = Integer.parseInt(values[i]);
}
res = winner(s, t);
System.out.println(res);
}
}
