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);
    }
}


#笔经##携程##笔试题目#

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
5 14 评论
分享

全站热榜

正在热议