双休在家的凯凯真的是太无聊了，他准备和他家的猫玩一个游戏。 凯凯随手写下一串01数列，定义这串数列的子串和为所有长度为2的子串的和。比如数列=010001，有如下长度为2的子串： 01 （前导0， =1） 10 00 （前导0，=0） 00 （前导0，=0） 01 （前导0，=1） 所以和为1+10+0+0+1 = 12
如果要只是算子串和的话，那对喵喵来说实在是太简单了，所以凯凯准备加大难度。 喵喵有k次机会可以交换数列里的相邻两个数（可以不用完这k次机会），使得交换完之后子串和最小。 这下喵喵不会做了，你可以帮帮它么？
输入为先输入一个t，代表t组。然后分别是n、k，字符串。 input: 3 4 0 1010 7 1 0010100 5 2 00110 output: 21 22 12
这个问题只需要分析 1 即可，只有 1 会增加子串和
如果 1 出现在头部，那么 1 的权重就是 10。原因：1xxx，所构成的子串为 1x
如果 1 出现在尾部，那么 1 的权重就是 1。原因：xxx1，所构成的子串为 x1
如果 1 出现在中间，那么 1 的权重就是 11。原因：xx1x，所构成的子串为 x1 和 1x，前者权重为 1 后者权重为 10
想要最小的子串和，所以尽量把 1 交换到「头部」或「尾部」，且「尾部」优先
xpublic int change(String s, int n, int k) { // 长度为 1，直接返回 if (n == 1) return s.charAt(0) - '0'; char[] str = s.toCharArray(); // sum 记录初始字串和 // firstOne 记录第一次出现 1 的位置 // lastOne 记录最后一次出现 1 的位置 int sum = 0, firstOne = -1, lastOne = -1; for (int i = 0; i < n; i++) { // 该位为 1 if (str[i] == '1') { // 如果在头部，权重为 10 if (i == 0) sum += 10; // 如果在尾部，权重为 1 else if (i == str.length - 1) sum += 1; // 其他位置，权重为 11 else sum += 11; // 更新 firstOne 和 lastOne if (firstOne == -1) firstOne = i; lastOne = i; } } // 交换次数为 0，直接返回 if (k == 0) return sum; // 没有 1，直接返回；否则至少存在一个 1 if (lastOne == -1) return sum; // 头尾都是 1，直接返回 if (str[0] == '1' && str[n - 1] == '1') return sum; // 头部是 1，表示尾部不是 1，否则就会走上一个判断 if (str[0] == '1') { // 距离尾部最近的 1 的下标是 lastOne // n - lastOne - 1 表示 1 移到尾部所需要的交换次数 // k 不够用的情况 if (n - lastOne - 1 > k) return sum; // 1 移到尾部，权重减少 10 return sum - 10; } // 尾部是 1，表示头部不是 1 if (str[n - 1] == '1') { // k 不够用 (同上) if (firstOne > k) return sum; // 1 移到尾部，权重减少 1 return sum - 1; } // 头尾都不为 1 的情况 // 只有一个 1 的情况 if (firstOne == lastOne) { // 需要判断移动到头还是尾，优先移动到尾部，因为可以减少更多权重 if (n - lastOne - 1 <= k) return sum - 10; // 移动到头部 if (firstOne <= k) return sum - 1; // 无法移动到头尾 return sum; } // 至少有两个 1 的情况 // 交换次数满足移动到头尾 if (n - lastOne - 1 + firstOne <= k) return sum - 11; // 优先移动到尾部 if (n - lastOne - 1 <= k) return sum - 10; // 移动到头部 if (firstOne <= k) return sum - 1;
return sum;}第一行输入两个整数n和m，表示迷宫的长和宽。 接下来n行，每行m 个字符， 用于描述迷宫构造，每个字符可能为以下几种： .表示空地， 玩家在空地时可以选择往 [上，下，左，右] 中的某个方向移动一格 U，D，L，R 分别表示朝向[上，下，左，右] 的传送带，站在传送带上的人会被强制移动到其指向的下一个位置 如果下一个位置还是传送带，会被继续传下去 如果传送带指向迷宫外，玩家会撞在墙上，昏过去，游戏结束，无法再到达出口 O表示迷宫出口
请你找到有多少点按照规则行走不能到达终点。
n<1e5，m<1e5，n*m<1e5 input: 5 5 ..... .RRD. .U.DR .ULL. ....O output: 10
从终点反向搜索，可以避免撞墙问题
xxxxxxxxxxprivate int m, n, cnt;private boolean[][] vis;public int maze(char[][] grids) { cnt = 0; m = grids.length; n = grids[0].length; vis = new boolean[m][n]; // 寻找出口 int x = -1, y = -1; boolean isFind = false; for (int i = 0; i < m && !isFind; i++) { for (int j = 0; j < n; j++) { if (grids[i][j] == 'O') { x = i; y = j; isFind = true; } } } dfs(grids, x, y); return m * n - cnt;}private void dfs(char[][] grids, int i, int j) { if (i < 0 || i >= m || j < 0 || j >= n) return ; if (vis[i][j]) return; vis[i][j] = true; cnt++; // 上 if (i - 1 >= 0) { if (grids[i - 1][j] == '.' || grids[i - 1][j] == 'D') { dfs(grids, i - 1, j); } } // 下 if (i + 1 < m) { if (grids[i + 1][j] == '.' || grids[i + 1][j] == 'U') { dfs(grids, i + 1, j); } } // 左 if (j - 1 >= 0) { if (grids[i][j - 1] == '.' || grids[i][j - 1] == 'R') { dfs(grids, i, j - 1); } } // 右 if (j + 1 < n) { if (grids[i][j + 1] == '.' || grids[i][j + 1] == 'L') { dfs(grids, i, j + 1); } }}在广告平台中，为了给广告主一定的自由性和效率，允许广告主在创造标题的时候以通配符的方式进行创意提交。线上服务的时候，会根据用户的搜索词触发的bidword对创意中的通配符（通配符是用成对{}括起来的字符串）进行替换（用0个或者多个字符替换通配符），用来提升广告投放体验。例如：{末日血战}，上线送SSR英雄，三天集鲚无敌阵容！”，会被替换成“帝国时代下载上线送SSR英雄，三天集齐无敌阵容！”。给定一个含有通配符的创意和一句标题，判断这句标题是否从该创意替换生成的。
输入一个n，有n个标题。第一行是带有通配符的创意，下面n行是所有标题。对于每一行标题，如果可以用通配符匹配，输出True否则输出False。
input: 4 ad{XYZ}cdc{Y}f{x}e adcdcefdfeffe adcdcefdfeff dcdcefdfeffe adcdcfe
output: True False False True
方案一：直接用String中的matches()函数
方案二：回溯 + 备忘录
xxxxxxxxxx// 方案一public boolean matchByReg(String s, String p) { StringBuffer reg = new StringBuffer(); for (int i = 0; i < p.length(); i++) { if (p.charAt(i) == '{') { while (p.charAt(i) != '}') { i++; } reg.append("(.*)"); } else { reg.append(p.charAt(i)); } } return s.matches(reg.toString());}// 方案二private int[][] emeo;public boolean isMathch(String s, String p) { emeo = new int[s.length()][p.length()]; return backtrack(s, p, 0, 0);}private boolean backtrack(String s, String p, int si, int pi) { if (si >= s.length() || pi >= p.length()) { if (si == s.length() && pi == p.length()) return true; return false; }
if (emeo[si][pi] != 0) return emeo[si][pi] == 1;
if (p.charAt(pi) == '{') { int k = pi; while (p.charAt(k) != '}') { k++; } pi = k + 1; for (int i = si; i < s.length(); i++) { if (backtrack(s, p, i, pi)) { emeo[si][pi] = 1; return true; } } emeo[si][pi] = -1; return false; } else { boolean r = s.charAt(si) == p.charAt(pi) && backtrack(s, p, si + 1, pi + 1); emeo[si][pi] = r ? 1 : -1; return r; }}小明和小红在玩摇骰子游戏，每个骰子有固定的面数k（2<=k<=8）,每一面对应的点数分别为1,2,.…,k。 小明有n（1<=n<=20）个骰子，对于骰子i（1<=i<=n），它的面数为a_i(2<=a_i<=8),摇到每一面的概率都是1/a_i。 小红有m（1<=m<=20）个骰子，对于骰子j（1<=j<=m），它的面数为bj(2<=bj<=8),摇到每一面的概率都是1/bj。 小明和小红分别摇各自拥有的全部骰子，然后把骰子朝上那一面的点数相加，最后比较谁的点数和最大，大的获胜，相同平手，小的获败。小明和小红只摇一把，平手不会继续重摇，小明想知道他获胜的概率，你能帮帮他吗？
输入 n、m。然后输入 n 个骰子和 m 个骰子 输出获胜概率，保留小数点后 3 位
input: 1 3 8 2 3 4
output: 0.255