5.30 字节夏令营笔试题目

第一题双指针扫一遍就可以了 前指针先向前扫直到两个指针之间的子串包含所有字符 然后后指针跟着往前扫逐个删字符 更新答案 第二题bfs从对方的将的位置倒着往前递推 记录每个位置能到达终点的路径数 对于某个位置A如果能从另一个位置B跳过来  那么位置B的路径数就要加上位置A的路径数 不合法的情况包含别马脚和被小A的马踩（小A的马也可能被小A自己的将别马脚） 第三题在树上做dp 对于一个节点A如果所有以A的子节点为根节点的树的总愉悦值都被求出来了 以节点A为根节点的树的总愉悦值就是A的三个颜色里最大的那个 状态转移是 dp[i][s_x]=max(dp[j][p]) j是i的所有子节点 p是所有不等于s_x的状态 从叶子节点倒着往上推就可以了

要睡觉了，所以只看了第一题，用滑动窗口应该可以解，首先遍历一遍字符串，统计不同字符的个数count，然后用一个26大小的数组存窗口内的每个字符次数。用另外一个变量cur,存当前窗口的不同字符数量。遍历的时候如果，当前要进入或者滑出的字符，对应次数是0到1，或者1到0才调整cur,只要cur==count就更新结果。感觉行得通，有错误的话，请指正

有人面试了吗

第一题，完全没思路。 第二题，感觉回溯就可以，但测试用例一直没看明白，我理解的题目意思每次马只能向右上方走，走的步长为（1，2）或（2，1），那马从（2，2）应该无法走到（6，3）这个位置，希望帮忙大神解答下困惑。

第三题，部分代码如下，只通过了10%的测试用例，自己写了几个例子， 还是没发现问题在哪，希望大家指点。 int val[5000][3], relation[5000]; vector<int> records(5000, -1);     int n;     ll maxHappy = -1, happy = -1;     cin >> n;     for (int i = 0; i < n; ++i)         for (int j = 0; j < 3; ++j)             cin >> val[i][j];     for (int i = 1; i < n; ++i) { // 1-n         int a, b;         cin >> a >> b;         relation[b] = a;     }     for (int j = 0; j < 3; ++j) {         records[0] = j;         happy = val[0][j];         for (int i = 1; i < n; ++i) {             int tmpMax = -1;             for (int k = 0; k < 3; ++k) {                 if (k == j || k == records[relation[i]])                     continue;                                  if (val[i][k] > tmpMax) {                     records[i] = k;                     tmpMax = val[i][k];                 }             }             // printf("%d-%d: %d\n", j, i, tmpMax);             happy += tmpMax;         }         if (happy > maxHappy)             maxHappy = happy;     }

#第一题python解法不知道对不对 ''' 思路 1、将字符长set成集合提取非重复唯一字符 abbbaaccb->abc？ 2、滑窗，left由[0,字符结尾减掉不重复的字符] [0,10-3+1] 因为range左开右闭所以要加1 right由[不重复字符，字符尾] [3,10+1] 3、假设res是全字符串[0,len(str1)],每次滑窗后对滑窗字符串进行set后对比，如果长度(right-left)比res小，则替换 ''' str1 = input() only = set(str1) res = [0,len(str1)] for left in range(len(str1)-len(only)+1): for right in range(left+len(only),len(str1)+1): if left>len(str1)-len(only): break if only == set(str1[left:right]): if res[1] > right - left: res = [left,right-left] break print(res) print(res[1],str1[res[0]:res[0]+res[1]])

第一题：         char[] chars = s.toCharArray();         //记录不同的字符，并将值置为2         HashMap<Character, Integer> map = new HashMap<>();         for (char aChar : chars) {             map.put(aChar, 2);         }                  int left = 0;         int right = 0;         // 从左往右遍历 直到当前窗口包含所有字符 遍历结束后得到  从左往右最长的字符串         for (int i = 0; i < chars.length; i++) {             // 为2 说明当前字符没有加入当前窗口中 所以加入并将值设为1             if (map.get(chars[i]) == 2) {                 //加入后 当前字符就不必考虑了                 map.put(chars[i], 1);                 //更新右边区间                 right = i;             }         }         // 从右往左遍历 直到当前窗口包含所有字符 遍历结束后得到  从左往右最短的字符串         for (int i = right; i >= 0; i--) {             // 为1 说明当前字符没有加入当前窗口 所以加入并将值设为0             if (map.get(chars[i]) == 1) {                 //加入后 当前字符就不必考虑了                 map.put(chars[i], 0);                 //更新左边区间                 left = i;             }         }         return new int[]{left,right-left+1}; 优化一下，可以提前终止，想不到其他的了，太菜了

题都没做出来会有面试吗?

m