面试题目集合

野性酷女 2023-01-19 13:54 164阅读 0赞

1、寻找一个字符串中最长的重复子串。 如 abcdabc 最长重复串 是abc

#include <iostream>
    using namespace std;
     
    void substr(char *a)//统计数组a中重复出现的最长的子序列
    {       
    	for(int n = 0; a[n]!='\0'; ++n);	// 统计字符串长度
    	int count = 1;
    	for(int len=n-1; len>0; --len)		// len:子串的长度
    	{
    		for( int begin=0; begin<=n-1-len; ++begin)	// begin:子串的首字符的位置
    		{
    			//match_begin:匹配字符串与被匹配字符串的距离
    			for(int match_begin=1; match_begin<=n-len-begin; ++match_begin)
    			{
    				int i;
    				for( i = begin; i < begin+len; ++i)//字符串匹配
    				{
    					if(a[i]!=a[i+match_begin])
    					{
    						break;
    					}
    				}
    				
    				if(i==begin+len) // 匹配成功
    				{
    					++count; // 统计匹配成功的次数
    				}
    			}
    			
    			if(count >= 2)
    			{
    				for( int i = 0; i < len; ++i)
    				{
    					cout << a[begin+i];
    				}
    				return;
    			}
    			count= 1;
    		}
    	}
    	return;
    }
    
    int main(int argc, char* argv[])
    {
    	char*a = "abcdabc";
    	substr(a);
    	cout << endl;
    	return0;
    }

使用后缀树：

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAXCHAR 5000 //最长处理5000个字符
    
    char c[MAXCHAR], *a[MAXCHAR];
    
    int comlen( char *p, char *q ){
        int i = 0;
        while( *p && (*p++ == *q++) )
            ++i;
        return i;
    }
    
    int pstrcmp( const void *p1, const void *p2 ){
        return strcmp( *(char* const *)p1, *(char* const*)p2 );
    }
    
    int main( ){
        char ch;
        int  n=0;
        int  i, temp;
        int  maxlen=0, maxi=0;
        printf("Please input your string:\n");
        while( (ch=getchar())!='\n' ){
            a[n]=&c[n];
            c[n++]=ch;
        }
        c[n]='\0';
        qsort( a, n, sizeof(char*), pstrcmp );
        for(i=0; i<n-1; ++i ){
            temp=comlen( a[i], a[i+1] );
            if( temp>maxlen ){
                maxlen=temp;
                maxi=i;
            }
        }
        printf("%.*s\n",maxlen, a[maxi]);
        system("PAUSE");
        return 0;
    }

2. 货物传递 （转自： [http://blog.csdn.net/lanceleng/article/details/8891213][http_blog.csdn.net_lanceleng_article_details_8891213]）

昨天参加了2013年阿里巴巴实习生校园招聘的笔试。其中有一道题似曾相识，在快交卷的时候才隐约回想起这是一个数学问题。但具体怎么做的却想不起来了。为了避免再次遗忘，所以还是动手自己再写一写吧。

题目参考：http://blog.csdn.net/hnmjiayou/article/details/8887127

解法参考：http://blog.sina.com.cn/s/blog\_75683c7f0100q4va.html

代码参考：http://50vip.com/blog.php?i=223

有一个淘宝卖家，他在全国有n个仓库，这n个仓库正好构成一个环形，如下图一所示，开始他所有仓库的货物数是不等的，现在他想让所有仓库的货物数都相等，如何运输使总的运输成本最低（成本=运货量\*路程），其中一次运输只能在两个相邻的仓库之间发生。试设计算法。

![20130506163946134][]

分析：

首先，题目规定运输只能在两个相邻的仓库之间发生，但并没有规定相邻的两个仓库什么时候运输，运输的方向如何，以及运输的次数。

但事实上，由于题目只要求使总的运输成本最低，所以我们就我们只需要关心相邻的两个仓库之间谁向谁运输（即运输的方向），以及相邻两个仓库之间总的运货量。而不必去关心这些运货量是经过几次运输得来的。

考虑到要使总的运输成本最低，那么货物是不应该在相邻两个仓库之间来回折腾的。也就是说，相邻两个点之间的运输的方向是确定的、唯一的。于是，我们可以把图一中相邻的一条边看成是有向边，并定义该有向边的权值为在改边上要进行的总的运输的货物量。

我们还可对这个问题的描述做进一步的简化抽象。我们可以规定，如果相邻两个边的运输是顺时针进行的，那么这次运输的权值就是正的；如果运输是逆时针进行的，则运输的权值是负的。权值的绝对值表示相邻两个点之间运输的货物的总量。记每条边的权值为Pi。如图二所示。

![20130506164843414][]

好了，到这里，我们已经将问题简化为求出一个P1, P2,.....Pn的组合，在使运输后每个节点相等前提下，![20130506164252394][]最小。其中Pi在区间\[-total, total\]内取值，total表示n个节点总的货物量。问题转化为了一个枚举问题，但事实上这条路并不可行，因为要枚举的空间太庞大了。

接下来我们继续挖掘题目包含的信息。我们用Gi表示每一个仓库的库存量。用average表示平均的货物量。并令Ri=Gi-average，表示第i个仓库库存量与平均库存的差值。那么Pi与Ri之间应该满足如下条件：

0 = Pn + R1 - P1

0 = Pi-1+Ri - Pi （i≠1）

我们发现，通过不断递推，可以将Pi（i≠1）用P1的线性变换表示。令P1 = x。则有：

P2 = x + R2；

P3 = x + R2 + R3；

P4 = x + R2 + R3 + R4;

P5 = x + R2 + R3 + R4 + R5;

....

我们再次引入新的记号。令：

Pi = x - Ti。其中T1 = 0且Ti = Ti-1 - Ri。

现在，求出一个使![20130506164252394][]最小的Pi组合问题已经转化为求出使![20130506164832493][]最小的x的值的问题。其中Ti是常数。我们发现，在将n个变量缩减为一个变量之后，搜索空间已经大大减少。只需要在\[-total, total\]区间对x进行搜索即可（其中total表示n个节点总的货物量）。到这一步，我们已经大大的缩减了搜索空间，但这个问题还可以做进一步优化。

我们将\{ Ti\}按值散放在数轴上。通过观察分析可知，当x等于\{Ti\}的中位数时，![20130506164832493][]最小。

在求解出x的确定值之后。再利用Pi = x - Ti即可得推得每条边的权值。而从上面的讨论中可知。当Pi大于零时，表示仓库i要向仓库i+1运输Pi个货物（若i为n，则表示i仓库向1仓库运货）。当Pi小于零时，表示仓库i向仓库i-1运输|Pi|个货物（若i为1，表示仓库i向仓库n运货）。为零，则不进行操作。

参考代码：

#include <cstring>
    #include <iostream>
    #include <algorithm>
            
    using namespace std;
    const int X = 1000005;
    typedef long long ll;
    ll sum[X],a[X];
    ll n;
    ll Abs(ll x){
        return max(x,-x);
    }
    int main(){
        //freopen("sum.in","r",stdin);
        while(cin>>n){
            ll x;
            ll tot = 0;
            for(int i=1;i<=n;i++){
                scanf("%lld",&a[i]);
                tot += a[i];
            }
            ll ave = tot/n;
            for(int i=1;i<n;i++)
                sum[i] = a[i]+sum[i-1]-ave;
            sort(sum+1,sum+n);
            ll mid = sum[n/2];
            ll ans = Abs(mid);
            for(int i=1;i<n;i++)
                ans += Abs(sum[i]-mid);
            cout<<ans<<endl;//此处ans的值是总的运输代价。
        }
        return 0;
    }

上述代码中输出的ans是总的运输代价。要获取具体的运输方案，需要另开辟一个存储空间存储排序前的sum值。获取mid值之后再通过sum\[i\]推得每个仓库执行的运输操作。

3. 链表逆序

链表逆序包括递归与非递归两种形式

#include <iostream>
    using namespace std;
    typedef struct _list
    {
        char value;
        struct _list * next;
    }mylist;
    
    mylist *ReverserList( mylist* head)
    {
        if(head == NULL || head->next == NULL)
        {
            return head;
        }
    
        mylist *p = head, *q = head->next;
        p->next = NULL;
        while( q != NULL)
        {
            mylist * tmp = q->next;
            q->next = p;
            p = q;
            q = tmp;
        }
        return p;
    }
    
    mylist * ReverserListTran( mylist * head, mylist* &rhead)
    {
        if(head == NULL)
        {
            return head;
        }
    
        if(head->next != NULL)
        {
            mylist *p = ReverserListTran( head->next, rhead);
            p->next = head;
            head->next = NULL;
        }
        else
        {
            rhead = head;
        }
    
        return head;
    }
    
    mylist * CreateList()
    {
        char value = 0;
        mylist * ret = NULL;
        while( cin >> value)
        {
            if(value == '#')
            {
                break;
            }
    
            mylist * p = new mylist;
            p->value = value;
            p->next = NULL;
    
            if( ret == NULL)
            {
                ret = p;
            }
            else
            {
                p-> next = ret;
                ret = p;
            }
        }
    
        return ret;
    }
    
    void printlist( mylist* p)
    {
        while( p != NULL)
        {
            cout << p->value << " ";
            p = p->next;
        }
        cout << endl;
        return ;
    }
    
    int main()
    {
        mylist * head = CreateList();
        printlist(head);
    
        mylist *rhead = ReverserList(head);
        printlist(rhead);
    
        ReverserListTran( rhead, head);
        printlist(head);
    
        return 0;
    }

4. 求数组的最大子数组和

题目：  
输入一个整形数组，数组里有正数也有负数。  
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。  
求所有子数组的和的最大值。要求时间复杂度为O(n)。

#include <iostream>
    
    using namespace std;
    
    int MaxSum(int a[], int n)
    {
        if( a == NULL || n <= 0)
            return ;
    
        int sum = -(1 << 31);   // 去最小的int值
        int temp = 0;
        for(int i = 0; i < n; i++)
        {
            if(temp <= 0)
            {
                temp = a[i];
            }
            else
            {
                temp += a[i];
            }
    
            if(temp > sum)
            {
                sum = temp;
            }
        }
    
        return sum;
    }
    
    int main()
    {
        int a[] = {1, -2, 3, 10, -4, 7, 2, -5};
        int sum = MaxSum(a, 8);
    
        cout << "sum: " << sum << endl;
        return 0;
    }

5. 9月5日，华为2014校园招聘的机试题目

通过键盘输入一串小写字母(a~z)组成的字符串。请编写一个字符串压缩程序，将字符串中连续出席的重复字母进行压缩，并输出压缩后的字符串。

压缩规则：

1、仅压缩连续重复出现的字符。比如字符串"abcbc"由于无连续重复字符，压缩后的字符串还是"abcbc"。

2、压缩字段的格式为"字符重复的次数+字符"。例如：字符串"xxxyyyyyyz"压缩后就成为"3x6yz"。

要求实现函数：

void stringZip(const char \*pInputStr, long lInputLen, char \*pOutputStr);

输入pInputStr： 输入字符串lInputLen： 输入字符串长度

输出 pOutputStr： 输出字符串，空间已经开辟好，与输入字符串等长；

注意：只需要完成该函数功能算法，中间不需要有任何IO的输入输出

示例

输入：“cccddecc” 输出：“3c2de2c”

输入：“adef” 输出：“adef”

输入：“pppppppp” 输出：“8p”

#include <iostream>
    
    using namespace std;
    
    void ntostr( int n, char str[])
    {
        int len = 0;
        while( n > 0)
        {
            str[len] = '0' + n % 10;
            n /= 10;
        }
    
        for( int i = 0;i < len / 2; i++)
        {
            char c = str[i];
            str[i] = str[len-i-1];
            str[len-i-1] = c;
        }
    }
    
    void stringZip( const char * pInputStr, int nInputlen, char * pOutputstr)
    {
        int index = 0;
        int count = 1;
        int in = 1;
        while( in < nInputlen)
        {
            count = 1;
            while(pInputStr[in] == pInputStr[in-1])
            {
                count++;
                in++;
            }
    
            if(count > 1)
            {
                char countstr[64];
                memset(countstr, 0, sizeof(countstr));
                ntostr(count, countstr);
                strcpy(pOutputstr + index, countstr);
                while( count > 0)
                {
                    count /= 10;
                    index++;
                }
                pOutputstr[index++] = pInputStr[in-1];
            }
            else
            {
                pOutputstr[index++] = pInputStr[in-1];
    
                if(in+1 == nInputlen)
                {
                    pOutputstr[index++] = pInputStr[in];
                }
            }
            in++;
        }
    }
    
    int main()
    {
        char pstr[256];
        memset(pstr, 0, sizeof(pstr));
        stringZip("cccddecc", strlen("cccddecc"), pstr);
        cout << "cccddecc" << " -- " << pstr << endl;
    
        memset(pstr, 0, sizeof(pstr));
        stringZip("adef", strlen("adef"), pstr);
        cout << "adef" << " -- " << pstr << endl;
    
        memset(pstr, 0, sizeof(pstr));
        stringZip("pppppppp", strlen("pppppppp"), pstr);
        cout << "pppppppp" << " -- " << pstr << endl;
    
        return 0;
    }

6. 字符串左旋

方法一：编程珠玑中的字符串及其子串的求逆的过程中实现左旋或右旋。

方法二：cgi stl的旋转方法，使用类似gcd的求解过程。

#include <iostream>
    
    using namespace std;
    
    int gcd(int n, int k)
    {
        if( k == 0)
        {
            return n;
        }
    
        return gcd(k, n%k);
    }
    
    void my_rotate(char *begin, char *mid, char *end)
    {
        int n = end - begin;
        int k = mid - begin;
        int d = gcd(n, k);
        int i, j;
        for (i = 0; i < d; i ++)
        {
            int tmp = begin[i];
            int last = i;
    
            //i+k为i右移k的位置，%n是当i+k>n时从左重新开始。
            for (j = (i + k) % n; j != i; j = (j + k) % n)    //多谢laocpp指正。
            {
                begin[last] = begin[j];
                last = j;
                printf("%s\n", begin);
            }
            begin[last] = tmp;
    
            printf("%s\n\n", begin);
        }
    }
    
    /*  整个操作过程如下，每一步为从上一步进行一次操作的结果
        abcdefghij
        ebcdefghij
        ebcdifghij
        ebcdifghcj
        ebgdifghcj
        ebgdifahcj
    
        efgdifahcj
        efgdijahcj
        efgdijahcd
        efghijahcd
        efghijabcd
    */
    
    int main()
    {
        char str[] = "abcdefghij";
        printf("%s\n", str);
        my_rotate(str, str + 4, str + 10);
        return 0;
    }

[http_blog.csdn.net_lanceleng_article_details_8891213]: http://blog.csdn.net/lanceleng/article/details/8891213
[20130506163946134]: /images/20221021/128632aed09446919019001661c09196.png
[20130506164843414]: /images/20221021/6f8cda495fff429f945c6d0ada6d9ab1.png
[20130506164252394]: /images/20221021/f3349775a5b145c2b46adb85bceca0bb.png
[20130506164832493]: /images/20221021/15ce8094088d45b084b3def0cbea5cbd.png