首页 > 字节夏令营530 软件工程 AC
头像
智纱酱,Byebye。。。
编辑于 2021-05-30 22:33
+ 关注

字节夏令营530 软件工程 AC

1、给定字符串S,找出包含S所有字符的最短字串。
思路:滑动窗口,先往右滑,满足条件后立刻收缩。
static void zj1(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put((c), map.getOrDefault(c, 0) + 1);
        }

        Map<Character, Integer> newMap = new HashMap<>();
        int[] ans = new int[]{0, s.length() - 1};
        int l = 0;
        for (int i = 0; i < s.length(); i++) {
            char cur = s.charAt(i);
            newMap.put(cur, newMap.getOrDefault(cur, 0) + 1);
            while (newMap.size() >= map.size()) {
                if (i - l < ans[1] - ans[0]) {
                    ans = new int[]{l, i};
                }
                char cl = s.charAt(l);
                int cnt = newMap.get(cl);
                if (cnt <= 1) {
                    newMap.remove(cl);
                } else {
                    newMap.put(cl, cnt - 1);
                }
                l++;
            }
        }
        System.out.println(ans[0] + "," + (ans[1] - ans[0] + 1));
    }

2、下象棋,双方只有1马,1将,你的马在原点,给定对方的马和将的位置,问有几种方法可以将军,同时不被对方攻击(只能向右上方走)。
思路:一开始看到的时候比较慌,后来做出来后发现还可以。
dp[i][j]表示走法,dp[i][j] = dp[i-1][[j-2] + dp[i-2][j-1]; 但是有些地方是没法转移的,1是对方马能攻击的范围,2是对方马的左下角。
static void main(){
        int[] ints = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
        int x = ints[0], y = ints[1];
        int[][] baned = new int[][]{{x - 1, y - 2}, {x + 1, y + 2}, {x - 2, y - 1}, {x + 2, y + 1},
                {x + 1, y -2}, {x + 2, y - 1}, {x - 1, y + 2}, {x - 2, y + 1}, {x + 1, y+ 1}};
        zjmemo[0][0] = 1L;
        zjmemo[x][y] = 0L;
        System.out.println(zj2(ints[2], ints[3], x, y, baned));
}

static long zj2(int i, int j, int f, int g, int[][] baned) {
        if (i < 0 || j < 0) {
            return 0;
        }
        for (int[] b : baned) {
            if (i == b[0] && j == b[1]) {
                return 0;
            }
        }
        if (zjmemo[i][j] != null) {
            return zjmemo[i][j];
        }
//        if (i - 1 == f && j - 1 == g) {
//            return 0;
//        }
        zjmemo[i][j] = 0L;
        for (int[] dir : dirs) {
            int x = i + dir[0], y = j + dir[1];
            zjmemo[i][j] += zj2(x, y, f, g, baned);
        }
        return zjmemo[i][j];

    }
3、公司举办派对,有a,b,c三种衣服,int[][3] happy表示每个人穿不同衣服能获得的快乐值,f[][2] 表示每个人的直属上级,每个人不会跟直属上级穿同样的衣服,问能获得的最大快乐值是多少。
思路:树形dp, dp[i][j] 表示 第i人穿j衣服能获得的最大值,dp[i][j] = max(下属1穿j+1的快乐值,下属1穿j+2的快乐值) + max(下属2穿j+1的快乐值,下属2穿j+2的快乐值) + ........;
所以我们返回max(dp[boss][0], dp[boss][1], dp[boss][2]);
这里求boss可以使用并查集的思路,或者入度。我是用的并查集。
static long zj2(int i, int t, List<List<Integer>> children, int[][] happy) {
        if (zjmemo[i][t] != null) {
            return zjmemo[i][t];
        }

        zjmemo[i][t] = happy[i][t];
        for (Integer integer : children.get(i)) {
            zjmemo[i][t] += Math.max(zj2(integer, (t + 1) % 3, children, happy), zj2(integer, (t + 2) % 3, children, happy));
        }

        return zjmemo[i][t];
    }


全部评论

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

推荐话题

相关热帖

近期精华帖

热门推荐