首页 > 5.27携程笔试后台开发2道算法题
头像
字节内推滴滴me
编辑于 2021-05-28 10:18
+ 关注

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


全部评论

(3) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐