京东0827笔试题解
第一题送分题不表
第二题长城，和网易0820笔试完全一样
题目：将一个数组变为长城的最小操作次数，每次操作可以修改任意一个元素。（长城即奇数位数字全部相等、偶数位数字全部相等的数组，如[1,4,1,4,1,4,1]）
分奇偶数位统计出现频率最高的数，然后ans = n - max_count_odd - max_count_even即可
但是要注意出现奇数和偶数频率最高的数相等的情况，所以需要同时记录出现频率第二多（或并列第一）的数字，在出现相等的情况时额外比较一下
第三题漂亮串
题目：一个只含小写字母的字符串如果含两个'red’即为漂亮串，如'redared'为漂亮串，‘reedred’不是漂亮串
输入n，输出以长度为n的字符串有多少种可能的漂亮串
（题解是事后想出来的，不确定能不能ac，测试了n<10的情况和手推的是一样的）
使用两个递推数组求解：
an 为长度为n的字符串中一个red都没有的可能数
递推公式：an = 26 * an-1 - an-3 （对于每个长度为n的串，在n-1的基础上尾加上一个字符有26 * an-1种情况，再减去填上一个字符恰好凑成一个red的情况an-3）
bn 为长度为n的字符串中恰好有一个red的可能数
递推公式：bn = 26^n - an
则有 
解释：枚举第一个red出现的位置，若第一个red出现的位置为i，那么在0~i-1的子串中不含有red，i+3~n-1的子串中含有至少一个red，共有ai * bn-i-3 种情况。枚举i的所有可能取值[0, n-3]
复杂度O(n)
python代码
投递百度搜索等公司10个岗位 >
