字节夏令营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的快乐值) + ........;

字节夏令营530 软件工程 AC

全站热榜

创作者周榜