阿里笔试2020.3.27

一般第一题字符串问题算是阿里给的送分题，不要想的太复杂了，想复杂了反而错。

第一题就不想那么复杂，遍历一遍，上下两个指针，如果不同就次数加一，上面后移，相同就都后移一位。第二题不知道dfs能不能过..

第二题，可惜当时没想清楚

卑微的附上我的**代码…请各位大佬轻喷🤕

想了很多，第一题还是没过

str_1 = input() str_2 = input() i = j = k = 0 length = len(str_1) for i in range(length):     if str_1[i] == str_2[j]:         j += 1     else:         k += 1          print(k)

上来先看第二题的，但是紧张了算法没想好...后续发现可以将区间先排序这样可以从小到大枚举0-2000然后再计算这样是n方的不是n三次方的😁第二页60%以后超时（n三方做法，写的时候一度以为是n方的），就先去看了眼第一题，然后莫名其妙遍历一遍感觉能过一交就通过了感觉10分钟不到就a了...但是后续没时间改第二题了。面试一定要预估好啊，60%真的运气好了😂

第二题交卷了来思路了😂😂

我是这么做的，首先判断一下能不能对上，也就是26个字母的数量是不是一样的，然后从第一个字符串中找跟第二个字符串首部匹配的最大子序列数目count，返回n-count

第一题贪心，t串每一个字符和s串比较，相同的位置s串打个记号，下一轮从记号处往后扫描，直到s串结束，最后总长度-t串已经扫描的长度。

我也是第一题idea一直没啥问题，但是就是过不去。最后十分钟发现了问题，不一定是第一个先扔后面，可以先第二个字符扔后面，然后第一个再扔，这个情况没考虑，看下时间，最后十分钟，双手离开了键盘

问哈你们在哪里参加的笔试啊？

我保存并调试了 只能看到过不过样例 怎么知道有没有AC啊

有没有大佬帮我看看 怎么就指针越界了, 30% 指针越界访问, 这么简单的代码越界, 我想了半个小时没想到case

第二题，枚举最小值 x ，然后算 x*( 最小值为x的情况总数 )之和sum。最后用sum / 所有的情况数。这种方法能过吗？我这么写只过了10%。 代码： #include<bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 2005; int l[maxn],r[maxn],cnt[maxn][maxn]; double sum[maxn]; int main(){     int n;     scanf("%d",&n);     int mnl = 2001,mnr = 2001;     for( int i = 1;i <= n;i++ ){         scanf("%d",&l[i]);         mnl = min( mnl,l[i] );     }     for( int i = 1;i <= n;i++ ){         scanf("%d",&r[i]);         mnr = min(mnr,r[i]);     }     for( int i = 1;i <= 2000;i++ ){         sum[i] = 1;         for( int j = 1;j <= n;j++ ){             if( i <= r[j] ){                 cnt[j][i] = min( r[j]-l[j]+1,r[j]-i+1 );             }             sum[i] *= cnt[j][i];         }     }     double cc = 1;     for( int i = 1;i <= n;i++ ){         cc *= r[i]-l[i]+1;     }     double ans;     for( int i = mnl;i < mnr;i++ ){         ans += i*(sum[i]-sum[i+1]);     }     ans += mnr*( sum[mnr] );     ans /= cc;     cout << ans;     return 0; }

第一题调着调着莫名其妙过了，不知道时不时出现了幻觉🤣，感觉还没判断-1的情况啊，大佬们给看看

import collections s1 = str(input()) s2 = str(input()) if collections.Counter(s1)!=collections.Counter(s2):     print(-1) else:     pref = ""     for s in s2:         if s in s1:             pref += s             s1 = s1[s1.index(s)+1:]         else:             break     print(len(s2)-len(pref))

第二题这样能解，但是sum感觉会爆炸，怎么解决比较好呀？