10个选择题，3个编程题，还有4个Android/iOS的附加题，附加题不记得了，记录一下选择题和编程题。

一、选择题

1.有6个不同颜色的珠子，可以串成多少种不同的手环？（旋转、翻转能变成一样的认为是一种）

A.30   B.60   C.120   D.720

2、在主线程中int i = 0，再并发同时执行A和B两个函数，函数A的内容是i++;i++;函数B的内容是i+=2;则i的结果可能为？（多选）

A.0   B.1   C.2   D.3   E.4   F.5   G.6

3、bash中不是用来处理字符串的是？

A.cut   B.awk   C.sed   D.pushd

4、【1，2，3，4，5】入栈，出栈不可能为？

A.【23415】   B.【54132】   C.【23145】   D.【15432】

5、已知一颗二叉树的先序遍历序列为GDAFEMHZ，中序遍历序列为ADEFGHMZ，则后序遍历序列为？

A.ADEFGHMZ   B.DAEFHZMG   C.AEFDHZMG   D.AFEDHMZG

6、不属于操作系统进程间实现同步的方式是？

A.临界区   B.互斥量   C.进程锁   D.事件

7、在传输层中未使用TCP协议的是？

A.SMTP   B.FTP   C.TELNET   D.DNS

8、下列哪个排序方式的平均时间复杂度不是O(nlogn)？

A.选择排序   B.快速排序   C.归并排序   D.堆排序

9、下列不是死锁产生条件的是？

A.互斥   B.请求与保持   C.竞争   D.循环等待

10、TCP的可靠传输实现不包括下列哪个选项？

A.滑动窗口   B.冗余校验   C.超时重传   D.确认机制

二、编程题

1.定义一个数据结构Edge

class Edge{
    private int a;
    private int b;
}

表示节点a和节点b是连接在一起的。

实现如下方法，即给定一个Edge数组Edge[]graph，以及任意两个节点p和q，返回p和q是否联通。

bool isConnected(Edge[]graph , int p , int q)

2.实现一个方法：给定股票的价格序列数组prices[n]，找到在该区间内股票的最大回撤值。

（找到p1，p2两个点需满足以下条件：p1在p2左边，prices[p1]>=prices[p2]，prices[p1] – prices[p2]在整个区间最大）

示例：

prices[n] = {2,3,4,1,10,8,5,1,7,2}

最大回撤：prices[4] – prices[7] = 10 – 1 = 9

prices[n] = {9,8,7,6,5}

最大回撤：prices[0] – prices[4] = 9 – 5 = 4

double getMaxDrawdown(double prices[])

3.已知M*N矩阵，矩阵的每行从左到右递增，每列从上到下递增，给定目标值，写程序计算给出的目标值是否存在矩阵中。

bool isExist (double  matrix[][] , double value)

RT，来自网龙笔试题，判断一个整数的二进制是否是01交替。

不知道我的答案对不对。。。负数的情况略复杂。

代码如下：

bool isZeroAndOne(int num)
{
    if(num<0){
        num = -num;
        num = num ^ 2147483647;
        num++;
    }
     if(num==1||num==0)
        {
                return false;
        }
        else {
        int last = num & 1;
        while (num)
        {
                num = num >> 1;
                int cur = num & 1;
                if ((last == 1 && cur == 1) || (last == 0 && cur == 0))
                {
                        return false;
                }
                last = cur;
        }
        return true;
        }
}

假设有标注了 1, 2, 3, …, n 各个数字的 n 张卡片。当第 1 张卡片的 数字为 k 时，则把前 k 张卡片逆向排序，并一直重复这个操作。举个例 子，当 n ＝ 6 时，如果由“362154”这个序列开始，则卡片的变化情况 如下。

这种情况下，卡片顺序一共变化 8 次后就无法继续变化了。

求使卡片顺序变化次数最多的 n 张卡片的顺序以及最大的变化次数。

1.顺序暴力递归思路：使用C++生成n位数的全排列，按照题意暴力模拟即可。

代码：

#include<cstdio>
#include<algorithm>
using namespace std;

void all_permutation(int arr[], int n);//获得数组的全排列
int fun(int a[],int deep);//求该数组翻转多少次后第一个数为1

int tempList[99];
int maxList[99];
int maxi = 0;

void all_permutation(int arr[], int n)//获得数组的全排列
{
    sort(arr,arr+n);    // sort arr[] in ascending order
    do{
      for(int i = 0;i<n;i++){
        tempList[i] = arr[i];//临时数组存储此时的全排列
      }
      int b = fun(tempList,0);//获得该排列翻转的次数，保存给b
      if(b > maxi){//如果b大于此时最大的数
        maxi = b;//最大的翻转次数更改为b
        for(int i = 0;i<n;i++){
            maxList[i] = arr[i];//存储翻转次数最多的数组更新
        }
      }
    }while(next_permutation(arr,arr+n));//获得下一个排列
}

int fun(int a[],int deep){
    if(a[0]==1){
        return deep;//如果第一个数是1的时候，返回结果
    }
   else{
    reverse(a,a+a[0]);//翻转数组的前a[0]个数
    fun(a,deep+1);//调用递归且deep+1，deep是我们的翻转次数
   }
}

int main(){
    int t;
     while(scanf("%d",&t)){
     if(t>=2 && t < 10){
     maxi = 0;
     int a[t+10];
     for(int i = 0;i<t;i++){
        a[i] = i+1;
     }
      all_permutation(a,t);
      printf("array is :");
      for(int i = 0;i<t;i++){
        printf("%d ",maxList[i]);
      }
      printf("\n");
      printf("max count = %d\n",maxi);
     }
     else{
        printf("please input number of 2~9!\n");
     }
     }
}

2.倒推优化递归思路：首先，数组的全排列需要第一个数是1，其次当一个数组中第i个数字是i的时候，这个数组一定有递推的上一步，否则这个数组就是最初情况。

代码：

#include<cstdio>
#include<algorithm>
using namespace std;

void all_permutation(int arr[], int n);//获得数组的全排列
void fun(int a[],int n,int deep);//递归函数

int tempList[99];//存储临时数组
int maxList[99];//存储变化次数最多的数组结果
int maxi = 0;//存储变化的最大次数

void all_permutation(int arr[], int n)//获得数组的全排列
{
    sort(arr,arr+n);    // sort arr[] in ascending order
    do
    {
        if(arr[0] == 1)
        {
            for(int i = 0; i<n; i++)
            {
                tempList[i] = arr[i];
            }
            fun(tempList,n,0);
        }
    }
    while(next_permutation(arr,arr+n));
}

void fun(int a[],int n,int deep)//递归函数
{
    if(deep > maxi){//获得最大翻转次数且存储此时的数组
        maxi = deep;
        for(int i = 0;i<n;i++){
            maxList[i] = a[i];
        }
    }
    for(int i = 1;i<n;i++){
        if(a[i]==i+1){//如果数组的第i个数等于i+1（因为数组从0开始）
            reverse(a,a+i+1);//翻转前i个数
            fun(a,n,deep+1);//开始递归，deep+1
            reverse(a,a+i+1);//翻转回去
        }
    }
}

int main()
{
    int t;
    while(scanf("%d",&t))
    {
        if(t>=2 && t < 10)
        {
            maxi = 0;
            int a[t+10];
            for(int i = 0; i<t; i++)
            {
                a[i] = i+1;
            }
            all_permutation(a,t);
            printf("array is :");
            for(int i = 0; i<t; i++)
            {
                printf("%d ",maxList[i]);
            }
            printf("\n");
            printf("max count = %d\n",maxi);
        }
        else
        {
            printf("please input number of 2~9!\n");
        }
    }
}

题目描述：

输入：

输出：

#include<iostream>
#include<limits.h>
#include<algorithm>
using namespace std;

struct maoxianjia
{
    double att;
    double mesos;
};

int comp(const maoxianjia &a,const maoxianjia &b)
{
    if(a.att == b.att)
    {
        return a.mesos<b.mesos;
    }
    else
        return a.att>b.att;
}

int main()
{
    int t = 0;
    int n = 0;
    int m = 0;
    int sum = 0;
    int mini;
    cin>>t;
    while(t--)
    {
        sum = 0;
        cin>>n>>m;
        int a[n+1];
        for(int i = 0; i < n; i++)
        {
            cin>>a[i];
        }
        maoxianjia b[m+1];
        for(int i = 0; i < m ; i++)
        {
            cin>>b[i].att>>b[i].mesos;
        }
        sort(a,a+n);
        sort(b,b+m,comp);
        if(b[0].att<a[n-1])
        {
            cout<<"Kingdom fall"<<endl;
            continue;
        }
        else
        {
            mini = INT_MAX;
            for(int i = 0; i <n ; i++)
            {
                for(int j = 0; j<m ; j++)
                {
                    if(a[i] > b[j].att)
                    {
                        break;
                    }
                    if(mini > b[j].mesos)
                    {
                        mini = b[j].mesos;
                    }
                }
                sum = sum + mini;
                mini = INT_MAX;
            }
        }
        cout<<sum<<endl;
    }
}

奇数回文串

定义奇数回文串是一个正读和反读都一样的，长度为奇数的字符串，比如“level”或者“non”就是奇数回文串。

请用不高于O（n^2）复杂度（以str.length()为准）的算法写出以下函数的实现代码。

int func(const std::string& str);

str中的字符只可能是小写的拉丁字母，该函数的返回值为str中最长的奇数回文子串的长度。 例如： str为“abba”，则函数的返回值为1。

str为“abcba”，则函数的返回值为5。

str为“eabcmcbad”，则函数的返回值为7。

str为“dddcbamabc”，则函数的返回值为7。

str为“cbamabcddd”，则函数的返回值为7。

我的代码

#include<iostream>
using namespace std;

int func(string str){
      int maxi = 0;
      int temp = 0;
      int count = 0;
      for(int i = 0; i < str.length()  ;i++){
            temp = i;
           int j = i;
           j -- ;
           i ++ ;
           while(j >= 0 && i <= str.length()-1 && str[i] == str[j]){
                count = count + 2;
                i++;
                j--;
           }
           if(count > maxi){
            maxi = count;
           }
           count = 0;
           i = temp;
      }
      return maxi+1;
}

int main(){
       string str1 = "abba";
       string str2 = "abcba";
       string str3 = "eabcmcbad";
       string str4 = "dddcbamabc";
       string str5 = "cbamabcddd";
       cout<<func(str1)<<endl;
       cout<<func(str2)<<endl;
       cout<<func(str3)<<endl;
       cout<<func(str4)<<endl;
       cout<<func(str5)<<endl;
}