阿里实习生笔试

先求字符数量是否一样，不一样就return，一样的话按第二个串的顺序，在第一个串找这个顺序的序列能匹配到的长度，如acdk, ckad，第一个串有ck，长度为2，那用字符串长-匹配长度就行了

最长公共子序列没法满足一种情况，就是主串是xxx匹配匹配匹配副串是匹配匹配匹配xxx的这种情况下面是ac代码const int CHAR_SIZE = 26;int main(){ int cn[2][CHAR_SIZE] = {0}; string s1, s2; cin >> s1 >> s2; int len = s1.size(); int j = 0, ans = 0; for (int i = 0; i < len; i++) { if(s1[i] == s2[j]){ j++; }else{ ans++; } cn[0][s1[i] - 'a']++; cn[1][s2[i] - 'a']++; } bool hasRes = true; for (int i = 0; i < CHAR_SIZE; i++) { if(cn[0][i] != cn[1][i]){ hasRes = false; break; } } DEBUG(hasRes ? ans : -1); return 0;}

能问一下 第一题具体的是怎么个情况求最少移动次数么

第一题一样想法

第二题证明为 E[min] = sum(i * Pr[min=i]) = sum(Pr[min>=i]) =sum(Pr[a>=i]*Pr[b>=i]*Pr[c>=i] .....) 复杂度O(n^2)

第一题代码粗略为

第一题直接匹配T的每个字符，比如s= bcda, t=abcd, 那就只能匹配一个，所以答案为3， 第二题直接计算SUM(Pr[min>=1]+Pr[min>=2]....)

感觉第一题是求最大公共子序列，自己测试了几个都行，但是就是通过0

两道题都爆零  心态崩了