常见面试题学习（2）

快来打我* 2022-03-28 19:28 158阅读 0赞

来自：

[http://www.cnblogs.com/hlxs/archive/2011/08/24/2151828.html][http_www.cnblogs.com_hlxs_archive_2011_08_24_2151828.html]

1. 数组相关

在排序找出数组中的两个数，他们之和为n

2. 数组中连续的数字之和为n的所有对数

3. 输出所以字符串的排列与组合

4. 序列化分问题

1. 数组相关

在排序找出数组中的两个数，他们之和为n，当然如果数组不是有序的，先排序在找时间复杂度O（nlogn + n），更简单的当然还是hash或者如果元素不重复的话位图，bloom filter更好

#include <iostream>
    
    using namespace std;
    //在排序找出数组中的两个数，他们之和为n
    //两个指针，一个指向开始，一个指向结尾，比较他们指向的数的和与n的大小
    //比n小，则begin ++，比n大，则end --，直到begin !< end
    void findTow(int *a,int size,int n)
    {
         
    if(n < 1 || size < 1)
    return ;
    int begin = 0,end = size -1;
    while(begin < end)
        {
         
    if(a[begin] + a[end] < n)
            {
         
    ++begin;
            }
    else if(a[begin] + a[end] > n)
            {
         
    --end;
            }
    else
            {
         
                cout << a[begin] << " " << a[end] << endl;
    break;
            }
        }
    }
    int main()
    {
         
    int a[10] = {
         1,2,3,4,6,7,8,9,10,13};
        findTow(a,10,20);
    
    return 0;
    }

2. 数组中连续的数字之和为n的所有对数

#include <iostream>
    
    using namespace std;
    void findContinueSequence(int *a,int size,int n)
    {
         
    if(size < 1 || n < 1)
    return;
    
    int begin = a[1];
    int begin_i = 1;
    int end = a[2];
    int end_i = 2;
    int sum = begin + end;
    while(begin_i < size)
        {
         
    if(sum == n)
            {
         
                cout << begin << " " << end << endl;
    for(int i = begin_i;i < end_i; i ++)
                     cout << a[i] << " ";
                cout << endl;
            }
    while(sum > n)
            {
         
                sum -= begin ++;
                begin_i ++;
    if(sum == n)
                {
         
                    cout << begin << " " << end << endl;
    for(int i = begin_i;i < end_i; i ++)
                        cout << a[i] << " ";
                    cout << endl;
                }
            }
    
            sum += ++ end;
    ++ end_i;
        }
    }
    int main()
    {
         
    int a[10] = {
         1,2,3,4,6,7,8,9,10,13};
        findContinueSequence(a,10,40);
    
    return 0;
    }

3. 输出所以字符串的排列与组合

排列（下转自：[http://www.cnblogs.com/dolphin0520/archive/2011/07/10/2102174.html][http_www.cnblogs.com_dolphin0520_archive_2011_07_10_2102174.html] ）

对给出的n个数，求出其所有的排列。

思路：对于R=\{r1,r2,r3.......rn\}，其全排列可以这样去计算，

perm(R)=riperm(R-ri);(1<=i<=n)

即以ri为前缀不变，对剩下所有的元素进行排列。即分别以r1,r2,r3,....rn作为前缀不变，对剩下的所有元素进行全排列即为所得到的结果。同理对于perm(R-ri)的求解也是一个相同的过程，因此可以采用递归的思想去解决。

#include <iostream>
    
    using namespace std;
    
    void permutation(char *a,int start,int n)
    {
         
    int end = n ;
    if(start == end)
        {
         
            cout << a << endl;
    return ;
        }
    else
        {
         
    static char tmp = NULL;
    for(int i = start; i < end; i ++)
            {
         
                tmp=a[start];
                a[start]=a[i];
                a[i]=tmp;
    
                permutation(a, start+1,n);
    
                tmp=a[start];
                a[start]=a[i];
                a[i]=tmp;
            }
        }
    }
    int main()
    {
         
    char a[] = "wtx";
    int len = 0;
    for(int i = 0;a[i] != '\0'; i ++)
        len ++;
    
        permutation(a,0,len);
    return 0;
    }

组合，也不是很懂，明天在说

#include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <vector>
    #include <iterator>
    using namespace std;
    void combine1(char* str, int num, vector<char>& res)
        {
         
    if(num== 0)
            {
         
                vector<char>::iterator iter = res.begin();
    for(; iter < res.end(); ++ iter)
                {
         
                    cout<< *iter<<"\t";
                }
                cout<<endl;
            }else{
         
    if(*str == '\0')
                {
         
    return;
                }
    
                res.push_back(*str);
                combine1(str + 1, num - 1, res);
                res.pop_back();
                combine1(str + 1, num, res);
            }
        }
    
    void combine(char* str)
        {
         
    if(str == NULL)
            {
         
    return;
            }
    
    int length = strlen(str);
            vector<char> res;
    for(int i = 1; i <= length; ++ i)
            {
         
                combine1(str, i, res);
            }
        }
    
    
    int main()
    {
         
    char a[] = "wtx";
        combine(a);
    return 0;
    }

4. 序列化分问题

#include <iostream>
    
    using namespace std;
    int f(int n,int m)
    {
         
    if(m == 1|| m == n)
    return 1;
    else
    return f(n - 1,m - 1) + f(n - 1, m) * m;
    }
    int main()
    {
         
    int n;
        cin >> n;
    int sum = 0;
    for(int i = 1;i <=n;i ++)
        {
         
            sum += f(n,i);
        }
        cout << sum << endl;
    return 0;
    }

[http_www.cnblogs.com_hlxs_archive_2011_08_24_2151828.html]: http://www.cnblogs.com/hlxs/archive/2011/08/24/2151828.html
[http_www.cnblogs.com_dolphin0520_archive_2011_07_10_2102174.html]: http://www.cnblogs.com/dolphin0520/archive/2011/07/10/2102174.html