阿里2020.03.27笔试

阿里2020.03.27笔试
第1题

• 题目：给出两个字符串s,t, 可以执行的操作是把s的任意一个字符移到字符串最后面，求出把s转变成t的最小操作次数，如果不能转变，则返回-1
• 思路：
  1. 判断能否转变：只要s,t中的元素和对应的个数相同，就能完成转变，这个用s和t排序后是否相等判断；
  2. 最小操作数：对s从t的第一位开始找公共子序列，操作数等于字符串长度减去匹配的字符数

代码入下

s='acdk'
t='ckad'

def solution(s,t):
    if sorted(s)!=sorted(t):
        return -1
    idx_t=0
    idx_s=0
    while idx_s<len(s):
        if s[idx_s]==t[idx_t]:
            idx_s+=1
            idx_t+=1
        else:
            idx_s+=1
    return len(t)-idx_t
print(solution(s,c))

比如上面的例子对于s='acdk'，t='ckad'，s对于t从头开始能匹配到的子序列是ck,所以只需要对没匹配到的ad进行操作，操作次数为2，由于可以把任意位置的字符直接放到最后而且没有限制操作顺序，所以没匹配的元素具体是怎样的排序都不会影响结果。

第2题

• 题目：要抽取n个随机数，对于每一个随机数i,抽取的范围是[l_i,r_i]（闭区间）,在这个区间里抽取到每个数的概率相同，求出这n个随机数最小值的期望,答案浮点误差精度为6位；
• 例子：n=2, l=[1,2], r=[3,3], 输出1.83333333
• 题意理解：对应的数学模型就是求多个独立离散均匀分布的最小值期望问题，参考：离散型最值的期望计算
  第2题做出来的朋友麻烦share一下哈