字节夏令营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];
}
