美团4.6笔试

1.给定一个长度为7的字符串，每次操作可以修改一个字符，要求把字符串改成meituan需要几次操作。

遍历字符串，记录有几个字符不同即可

2.在几个复数中找实数个数

遍历即可

3.有一个长度为n(n<=1e5)值各不相同的数组a，b是数组a删除了一个数ai，然后求前缀和打乱顺序，c是数组a删除了一个数aj，然后求前缀和打乱顺序，现在给你b和c，求数组a，保证有唯一解

分别对两个数组排序然后做差分，将差分的值分别放入两个set，命名为stb和stc，使用两个指针lb，lc分别指向当前位置，判断stb中是否有(c[lc]-c[lc - 1])这个值，如果没有说明这个值是b中被删除的那个，把他添加到ans数组中并且lc++，再判断stc中是否有(b[lb]-b[lb - 1])这个值，如果没有说明这个值是c中被删除的那个,把他添加到ans数组中并且lb++,否则则为两个人公有的（感觉写复杂了）

4.给定n个字符串，保证字符串中不存在重复字符，每次可以选择一个字符且要求与上一次选择的字符不同，求有多少种方式

dp[i][j]表示前i个字符，第i个字符选择j共有多少种方式，直接枚举相邻两个字符串转移即可，记得给第一个字符串赋初值1

5.小美和小团在一个大小为n*m的矩阵中，小美在（x1,y1)，小团在（x2,y2)，小美每次只能向左下，下，右下随机走一格，小团每次只能向左上，上，右上随机走一格，要求两个人相遇的概率（n,m<=3000)

先特判m=1的情况，这种情况下如果小美在小团的上方或者两人重合，则为1，否则为0

求两个二维dp，f[i][j]分别代表小美走到当前格是多少概率，注意当小美在左边界和右边界的概率只有两种走法，所以是二分之一的概率到下一个点（在这里卡了快20分钟），同理g[i][j]表示小团走到当前格的概率，不过小团需要行倒序枚举，因为小团是往上走。两个人的相遇只能在中间点，所以只需要判断在(x1 + x2 + 1)/2这行相遇的概率，上取整的原因是因为小美先走。最后枚举这一行相遇的概率求和即可，也就是对j从1到m的f[x][j]*g[x][j]求和，x为(x1 + x2 + 1)/2