字节笔试 20210307
两个小时 4 道题，题目其实不算特别难（虽然最后一道题不知道错哪了），估计是超时？（如果部分超时不知道牛客会不会提醒，如果知道超时的话，当时应该还能再优化点）
第一题
给定一个数组，求数组中每一个数，距离下一个比他大的数的距离
LeetCode 1019. 链表中的下一个更大节点
LeetCode 503. 下一个更大元素 II
类似这两个题的结合，与 II 的区别是，数组不是循环的，与 I 的区别是，题目是一个数组，而非链表。
不过这两道题要求的是下一个数是谁，而笔试中是距离，所以单调栈应该使用大小作比较，最后计算下标差。
标准思路应该是 倒序单调栈
用单调栈存储当前位置后面所有的数（从小到大）
如果新的数 需要插入，就把所有比 小的都删去，然后把 存入
（因为只需要找距离最近的下一个最大的数，在 右面还比 小的已经没用了）
除去最后一个数必定是 外，前面的数只需要在单调栈里做个二分查找就行
II 的思路类似，不过需要先找到最大值的位置，然后从最大值开始循环倒序遍历
可悲的是，笔试的时候，单调栈只过了 80%，不知道是哪写错了。所以最后 Python 交了发暴力，100%……
下面是 503 和 1019 的代码（实际上笔试里我也这么写的……但是就是 20% 过不了，不知道为啥，还好字节卡的不严，暴力也能过）
import ( "sort" ) func nextGreaterElements(nums []int) []int { n := len(nums) if n == 0 { return []int{} } // 先找到最大值的位置 maxPos := 0 for i:=1; i<n; i++ { if nums[maxPos] < nums[i] { maxPos = i } } // 栈需要保证单调递减 // 新的数必定更接近于在判断的数，如果新的数更大，那么老数没有意义 stack := make([]int, n) stackLen := 0 stack[stackLen] = nums[maxPos] stackLen++ res := make([]int, n) res[maxPos] = -1 for i:=0; i<n; i++ { pos := (maxPos + n - 1 - i) % n num := nums[pos] // 找到栈中第一个小于等于 num 的数（其左侧就是第一个的大于的数） lstPos := sort.Search(stackLen, func (p int) bool { return stack[p] <= num }) // fmt.Println("find", num, "in", stack[:stackLen], lstPos) if lstPos == 0 { // 没有更大的数了 res[pos] = -1 } else { res[pos] = stack[lstPos-1] } // 栈内所有比当前数小的都可移除掉 stack[lstPos] = num stackLen = lstPos + 1 } return res }
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ import ( "sort" ) func nextLargerNodes(head *ListNode) []int { arr := make([]int, 0) it := head for it != nil { arr = append(arr, it.Val) it = it.Next } n := len(arr) stack := make([]int, n) pos := 0 res := make([]int, n) for i:=n-1; i>=0; i-- { num := arr[i] // 找到下一个比当前元素大的元素的距离 if i == n-1 { res[i] = 0 } else { idx := sort.Search( pos, func (i int) bool { return stack[i] <= num }, ) if idx == 0 { res[i] = 0 } else { res[i] = stack[idx-1] } } // 更新单调栈 for pos != 0 && num >= stack[pos-1] { pos-- } stack[pos] = num pos++ } return res }
第二题
一群人需要围城一圈，为了看着整齐，需要让相邻人的身高差的最大值取最小，求这个值是多少
因为目标是身高差的最大值，因此实际上其他人再参差不齐，只需要保证最大的极端差值尽可能小即可。
如果不是围城一个圈，那么很显然直接排序遍历一遍，求最大差值即可。
但由于需要围成圈，最大值和最小值的差值将会非常大。因此，需要用其他数来尽可能弥补这个落差。
从最大值和最小值交接的地方开始思考，如果要让这个落差缓和，那么需要塞入一个中间值，比如让身高第三高的，和身高第三低的人，插在这里（身高第二高和第二低，需要在另一侧存在），那么这个差值就被缓解了一点。
从整体思路上来看，如果将整个队伍按顺序分成两部分，分别从两侧站，那么最后落差将会比较缓和
也即站成一个薯片的形状（双曲抛物面）
图片来自 https://blog.csdn.net/lanchunhui/article/details/52888402参考之前排序站队的思路，现在仍然应该排队站，第一个人站定后，第二个人站在他左边，第三个人站在第一个人右边，第四个人接着第二个人，第五个人接着第三个人……
知道最后一个人站定，将左右两侧并拢即可
以 1 2 3 4 5 6 7 为例，应该站成 1 3 5 7 6 4 2 (1)
那么可以看出，实际上要求的就是最小值和次小值，最大值和次大值的差，与任意间隔为 2 的数的差中的最大值即可
package main import ( "fmt" "sort" ) func max(a, b int) int { if a > b { return a } return b } func main() { var n int fmt.Scanf("%d", &n) h := make([]int, n) for i:=0; i<n; i++ { fmt.Scanf("%d", &h[i]) } sort.Ints(h) res := max(h[1]-h[0], h[n-1]-h[n-2]) for i:=0; i<n-2; i++ { res = max(res, h[i+2] - h[i]) } fmt.Println(res) }
第三题
图书管理员有两种要求
1 x y，将书x和y放置到一个书架2 x y，不允许将x和y放置到一个书架
找出有几个操作 2 不能实现
唔，没啥可想的，就是个并查集，1 操作将两个书连起来，2 操作判断两个书是不是在一个并查集。（几周前 LeetCode 疯狂出并查集，应该都能想到怎么写吧）
唯一需要注意的是，题目没说书的序号连续，也即有可能存在这种输入数据
2 1 100 99999999 2 1 99999
所以不能使用数组来存并查集，换成哈希表就行了
没找到原题，大概按照思路写了下，附赠两组测试用例，分别输出 1 和 2
5 1 1 2 1 2 3 1 4 5 2 1 3 2 1 4 -------- 6 1 100000 9999999 1 1 2 2 1 2 2 5 3 1 1 100000 2 1 9999999
package main import ( "fmt" ) var f = make(map[int]int) func getF(x int) int { _, exist := f[x] if !exist { f[x] = x } fx := f[x] if fx != x { f[x] = getF(fx) return f[x] } return x } func connect(x, y int) { fx := getF(x) fy := getF(y) f[fx] = fy } func check(x, y int) bool { return getF(x) == getF(y) } func main() { var n int fmt.Scanf("%d", &n) var command, x, y int num2 := 0 xs := make([]int, 0) ys := make([]int, 0) for i := 0; i < n; i++ { fmt.Scanf("%d %d %d", &command, &x, &y) if command == 1 { connect(x, y) } else { xs = append(xs, x) ys = append(ys, y) num2++ } } res := 0 for i := 0; i < num2; i++ { if check(xs[i], ys[i]) { res++ } } fmt.Println(res) }
第四题
两个字符串 a、b 有如下操作:
- 增加一个字符
- 删除一个字符
- 修改一个字符
给定一个字典序排序的字符串数组，从中选择一个子序列，使得后一个字符串，可以从前一个字符串通过一次操作变换得到
求子序列的最长长度
出 Uva 原题我是没想到的……
按道理说大概思路也很明确，动态规划 表示以 结尾的子序列能达到的最大的长度
用 的时间可以计算出所有的 ，找到其中的最大值即可
中间需要判断两个字符串能否通过一次操作变换得到，因此需要有一个check(a, b)函数判断。
虽然 LeetCode 上有类似的题目，使用 DP 实现计算最小操作次数，不过实际上没必要用动态规划，因为只能用一次，实际上直接双指针跑最多三轮就行了，时间复杂度是
可惜的是，最后只过了 ，据说是需要考虑条件中给的字典序
由于 Uva 不能交 Go，所以给一份能 AC 的 C++ 代码
#include <cstdio> #include <cstring> #include <string> #include <vector> using namespace std; #define MAXN 25005 #define MAXM 20 char ss[MAXN][MAXM]; int dp[MAXN]; bool check(char *a, char *b) { int la = strlen(a); int lb = strlen(b); if (abs(la - lb) > 1) return false; int flag = -1; int i = 0, j = 0, pos = 0; while (1) { // printf("%d %d %d\n", i, j, flag); // 都已经遍历到结束了 if (i == la && j == lb) break; // 有一个遍历到结束，同时还有一次操作的机会，可以直接补足另一个 if ((i == la || j == lb) && flag == -1) break; // 有一个遍历到结束，继续尝试别的修改方案 // 还未遍历结束，继续遍历 if ((i == la || j == lb) || a[i] != b[j]) { switch (flag) { case -1: // 当前未使用过操作机会 // 使用“修改” flag = 1; pos = i; i++; j++; break; case 1: // 上一次使用的“修改” // 尝试使用“增加” flag = 2; i = pos; j = pos + 1; break; case 2: // 上一次使用“增加” // 尝试使用“删除” flag = 3; i = pos + 1; j = pos; break; default: // 上一次使用“删除” // 都无法满足条件 // printf("%s %s false\n", a, b); return false; } continue; } ++i; ++j; } // printf("%s %s true\n", a, b); return true; } int main() { int n = 0; while (~scanf("%s", ss[n++])); --n; int res = 0; for (int i = 0; i < n; ++i) { dp[i] = 1; for (int j = i-1; j >= 0; --j) { if (dp[i] < dp[j] + 1 && check(ss[i], ss[j])) { // printf("%d %d\n", i, j); dp[i] = max(dp[i], dp[j] + 1); } } res = max(res, dp[i]); } printf("%d\n", res); return 0; }
需要注意的是，这部分的时间复杂度并不好，在 Uva 是刚好卡着时间 AC。
和笔试时的提交不同，这里加了个简单的小优化，提升了一部分速度。
就是在 DP 时，从后往前遍历 j，当发现即使 j 可以操作成 i，数据也不会变得更长时，就不再判断是否合法。
这样可以减少一些判断，不过按照这个时间复杂度，估计也还是过不了
一个效率更高的思路是 UVa 10029 - Edit Step Ladders
大概思想是通过对每一个字符串尝试增删改生成新的字符串，而后查找新字符串是否存在，如果存在，则使用其对应的值更新 DP
由于数据使用字典序排序，因此很多新字符串实际上不需要生成（比如abca在删除时，不需要考虑删除ab，因为删除后不可能字典序小于abcd；插入时，则需要保证插入的新字符比原本在这里的字符更大；修改同理）
查找可以使用二分查找，也可以使用哈希表查找，总之快速找到对应字符串的下标即可
这个思路的时间复杂度取决于生成新字符串，如果可以尽可能避免无用字符串的生成，效率会比较高（因为每个字符串最长只有 16）
似乎是受限于字符串拼接，毕竟论字符串处理，C/C++ 的char[]吊打所以高级语言，这里耗时近 2 秒，而上面题解的 C 只用了 300ms。不过考虑到字符串拼接以及 Python 本身的低效，应该属于合理范围
chars = list('abcdefghijklmnopqrstuvwxyz') def main(): ss = [] n = 0 m = {} while 1: try: s = input() ss.append(s) m[s] = n n += 1 except: # EOF break res = 0 dp = [1] * n def solveNewString(s, i): # print(s) idx = m.get(s, -1) if idx != -1 and idx < i: # print(current, ss[idx]) dp[i] = max(dp[i], dp[idx] + 1) for i in range(n): current = ss[i] l = len(current) # 删除 for j in range(l): if j+1 < l and current[j] < current[j + 1]: continue temp = f"{current[0:j]}{current[j + 1:]}" solveNewString(temp, i) # 增加 for j in range(l): for char in chars: if j < l and char >= current[j]: continue temp = f"{current[0:j]}{char}{current[j:]}" solveNewString(temp, i) # 修改 for j in range(l): for char in chars: if char >= current[j]: continue temp = f"{current[0:j]}{char}{current[j + 1:]}" solveNewString(temp, i) res = max(res, dp[i]) print(res) if __name__ == "__main__": main()
萌ICP备20213456号
