字节秋招笔试第六轮

T1 字符排序 AC

给出一个由问号？，大小写字母，数字组成的字符串，要求1.问号位置不变2.数字位置不变，相对位置按从大到小排3.字母位置不变，相对位置按字典序排

solution

读入字符串，把字母数字分别存在数组里sort再塞回去就行了

T2 火柴棒数字 暴毙

给出n根火柴，要求给出一个其组成的最大数字和最小数字，不能有剩余。 0~9分别由6,2,5,5,4,5,6,3,7,6根火柴组成。

solution

最大数：考虑令num位数最多，那必然是111……1或者7111……1。

最小数：考虑令num位数最小，那num中有很多个8，len = ceil(n / 7)，然后就开始分类讨论，n % 7 = 1 时开头为10, n % 7 = 2 时开头为18…… n < 7的时候特判一下。

做题的时候因为最大数len为奇数的情况写成了111……7而暴毙，刚反应过来。

T3 最小绝对值 不会

给出长度为n的数组a,长度为m的数组b,和k。求|（a[i] - b[j]）² - k²|的最小值。

Solution

k = 0 的情况好想，分别排序之后扫一遍就出来了。

k != 0 的情况。|(a - x)² - k²| = |a² - 2ax + a² - k²| Δ > 0 的时候在b上二分两个根，Δ <= 0 的时候在b上二分a。

T4 猜数字 AC

给出一个范围1~n，A和B在轮流猜数字，会得到等于，大于，小于的反馈。A先手。两人足够机智且理性。求A获胜的概率。

Solution

笔试的时候我盲猜n为偶数时是0.5，奇数时是 1/n + (n - 1) / n / 2，然后就过了。

用第二数学归纳可以证一下。 设n <= k 时满足f(2k) = 1/2,f(2k + 1) = (k + 1) / (2k + 1)。 则对f(2k + 2)，任意猜一个数的概率为1 / (2k + 2) + a / (2k + 2) * (1 - f(a)) + (2k + 1 - a) / (2k + 2)(1 - f(2k + 1 - a)，讨论a的奇偶带入易得f(2k + 2) = 1 / 2。

对f(2k + 3)，任意猜一个数的概率为1 / (2k + 3) + a / (2k + 3) * (1 - f(a)) + (2k + 2 - a) / (2k + 3)(1 - f(2k + 2 - a)，讨论a的奇偶带入得a为偶数的时候f(2k + 3) = (k + 3) / (2k + 3), a为奇数时f(2k + 3) < (k + 3) / (2k + 3。因为决策是明智的，所以f(2k + 3) = (k + 3) / (2k + 3)。