小米算法岗三道题(全AC)

第一道,字符串匹配,利用窗口滑移:
#include<iostream>
#include<map>
using namespace std;
int main(){
string s1,s2;
while(cin>>s1>>s2){
map<char,int> mp1;
map<char,int>mp2;
int len1=s1.length();
int len2=s2.length();
if(len1==0||len2==0)  cout<<-1<<" "<<-1<<endl;
for(int i=0;i<len2;i++){
mp1[s2[i]]++;
mp2[s2[i]]++;
}
int l=-1,r=-1;
int i=0;
int count=len2;
int ll=0;
while(i<len1){
if(mp2[s1[i]]>0){
if(mp1[s1[i]]>0){
count--;
}
mp1[s1[i]]--;
}
if(count==0){
while(mp2[s1[ll]]==0||mp1[s1[ll]]<0){
if(mp1[s1[ll]]<0) mp1[s1[ll]]++;
ll++;
}
//    cout<<ll<<" "<<i<<endl;
if((l==-1&&r==-1)||r-l+1>i-ll+1){
int s=0;
for(int j=ll;j<=i;j++){
if(s1[j]==s2[s]) s++;
}
if(s==len2) {
l=ll;
r=i;
}
}
}
i++;
}
cout<<l<<" "<<r<<endl;
}
}
第二道 大数阶乘,HDUOJ上的原题
#include <iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
int main()
{  int m,i,j;
while (cin>>m)
{   int flag=1;
int carry=0,diff=0;
int weishu[4000];
weishu[0]=1;
for (i=2;i<=m;i++)
{
for (j=1;j<=flag;j++) {
diff=weishu[j-1]*i+carry;
weishu[j-1]=diff%10;
carry=diff/10;
//  cout<<diff<<" "<<carry<<endl;
}
while (carry)
{
flag++;
weishu[flag-1]=carry%10;
carry/=10;
}
}
for (i=flag-1;i>=0;i--)
{  cout<<weishu[i];
if(i==0) cout<<endl;
}
}
return 0;
}
第三道题,其实就是,一看就懂,哈哈
#include<iostream>
using namespace std;
int main(){
int n;
int d[10000];
d[0]=1;
d[1]=1;
for(int i=2;i<10000;i++){
d[i]=d[i-1]+d[i-2];
}
while(cin>>n){
cout<<d[n]<<endl;
}
}

#小米#
全部评论
第一题我暴力的,居然也能通过。我是不是应该感到很幸运啊
点赞 回复 分享
发布于 2017-09-18 22:54
第一道题有一点BUG,但是全AC了,严格意义上讲应该先判断是否是正确的窗口,再滑移,因为会导致输入aabcad    aabcd的时候出现错误的-1,-1但是用例全过了,就懒得改了
点赞 回复 分享
发布于 2017-09-18 21:13
第三题求解,为啥一直是25,不就是普通的fibonacci吗
点赞 回复 分享
发布于 2017-09-18 21:15
第三题,斐波拉契数在46的时候貌似就爆了吧
点赞 回复 分享
发布于 2017-09-18 21:18
什么岗的啊
点赞 回复 分享
发布于 2017-09-18 21:27
只AC了2.25的看来没戏了
点赞 回复 分享
发布于 2017-09-18 21:34
第一道题,滑窗内字母的顺序需要考虑吗
点赞 回复 分享
发布于 2017-09-18 21:42
点赞 回复 分享
发布于 2017-09-18 22:37
第三题还可以更简单 空间复杂度o(1)
点赞 回复 分享
发布于 2017-09-19 09:17

相关推荐

不愿透露姓名的神秘牛友
2024-12-29 00:19
快手 Java工程师 26.0k*16.0
点赞 评论 收藏
分享
2024-12-07 21:21
东北大学 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务