腾讯2017暑期实习生编程题

向右看齐 2022-07-20 15:03 222阅读 0赞

1个小时三道题，通过两道，动态规划要系统的看一下了。

给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？  
输出需要删除的字符个数。

小Q最近遇到了一个难题：把一个字符串的大写字母放到字符串的后面，各个字符的相对位置不变，且不能申请额外的空间。  
你能帮帮小Q吗？

#include<iostream>
    #include<string>
     
    using namespace std;
     
    void trans(string&str)
        {
        bool f=true;
        while(f)
        {
            f=false;
            for(int i=0;i<str.length()-1;i++)
        {
            if(str[i]-92<0&&str[i+1]-92>=0)
                {
                f=true;
                char t=str[i];
                str[i]=str[i+1];
                str[i+1]=t;
            }
        }
        }
    }
     
    int main()
        {
        string str;
        while(cin>>str)
        {
            trans(str);
            cout<<str<<endl;
             
        }
        return 0;
    }

小Q今天在上厕所时想到了这个问题：有n个数，两两组成二元组，差的绝对值最小的有多少对呢？差的绝对值最大的呢？

#include<iostream>
    #include<map>
     
    using namespace std;
     
    int cn2(int n)
        {
        return n*(n-1)/2;
    }
     
    int main()
        {
        int N=0;
        while(cin>>N)
        {
            map<int,int>cnt;
            int num=0;
            for(int i=0;i<N;i++)
            {
                cin>>num;
                cnt[num]++;
            }
            int minpair=0;
            for(map<int,int>::iterator it1=cnt.begin();it1!=cnt.end();it1++)
                if(it1->second>1)
                minpair+=cn2(it1->second);
            if(minpair==0)
            {
                map<int,int>::iterator it=cnt.begin();
                int n1=it->first;
                it++;
                int mingap=it->first-n1;
                for(map<int,int>::iterator it1=it;it1!=cnt.end();it1++)
                {
                    if(it1->first-n1<mingap)
                    {
                    mingap=it1->first-n1;
                    minpair=1;
                    }
                    else if(it1->first-n1==mingap)
                         minpair+=1;
                    n1=it1->first;
                 }
            }
            map<int,int>::iterator it=cnt.end();
            it--;
            int maxpair=cnt.begin()->second*it->second;
            cout<<minpair<<" "<<maxpair<<endl;
        }
         
        return 0;
    }