字节笔试 20210307

两个小时 4 道题，题目其实不算特别难（虽然最后一道题不知道错哪了），估计是超时？（如果部分超时不知道牛客会不会提醒，如果知道超时的话，当时应该还能再优化点）

第一题

给定一个数组，求数组中每一个数，距离下一个比他大的数的距离

LeetCode 1019. 链表中的下一个更大节点
LeetCode 503. 下一个更大元素 II

类似这两个题的结合，与 II 的区别是，数组不是循环的，与 I 的区别是，题目是一个数组，而非链表。
不过这两道题要求的是下一个数是谁，而笔试中是距离，所以单调栈应该使用大小作比较，最后计算下标差。

标准思路应该是 倒序单调栈

用单调栈存储当前位置后面所有的数（从小到大）
如果新的数 $k$ 需要插入，就把所有比 $k$ 小的都删去，然后把 $k$ 存入
（因为只需要找距离最近的下一个最大的数，在 $k$ 右面还比 $k$ 小的已经没用了）

除去最后一个数必定是 $-1$ 外，前面的数只需要在单调栈里做个二分查找就行

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
}

第二题

一群人需要围城一圈，为了看着整齐，需要让相邻人的身高差的最大值取最小，求这个值是多少

牛客 庆祝61

因为目标是身高差的最大值，因此实际上其他人再参差不齐，只需要保证最大的极端差值尽可能小即可。

如果不是围城一个圈，那么很显然直接排序遍历一遍，求最大差值即可。
但由于需要围成圈，最大值和最小值的差值将会非常大。因此，需要用其他数来尽可能弥补这个落差。

从最大值和最小值交接的地方开始思考，如果要让这个落差缓和，那么需要塞入一个中间值，比如让身高第三高的，和身高第三低的人，插在这里（身高第二高和第二低，需要在另一侧存在），那么这个差值就被缓解了一点。
从整体思路上来看，如果将整个队伍按顺序分成两部分，分别从两侧站，那么最后落差将会比较缓和

也即站成一个薯片的形状（双曲抛物面）

图片来自 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 10029 - Edit Step Ladders

出 Uva 原题我是没想到的……

按道理说大概思路也很明确，动态规划 $dp[i]$ 表示以 $i$ 结尾的子序列能达到的最大的长度
用 $O(n^2)$ 的时间可以计算出所有的 $dp$，找到其中的最大值即可

中间需要判断两个字符串能否通过一次操作变换得到，因此需要有一个check(a, b)函数判断。

虽然 LeetCode 上有类似的题目，使用 DP 实现计算最小操作次数，不过实际上没必要用动态规划，因为只能用一次，实际上直接双指针跑最多三轮就行了，时间复杂度是 $O(n)$

可惜的是，最后只过了 $40.91$，据说是需要考虑条件中给的字典序

由于 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()