2019华为暑期实习编程题

一、字符串对称性问题:

#include <iostream>
#include <string>
#include <cstring>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <iterator>
#include <set>
using namespace std;
bool duichen(string s,int len)
{

    for (int i = 0; i <=len/2; i++)
    {
        int t = len - 1 - i;
        if (s[i] != s[len - 1 - i])
            return false;
    }
    return true;
}
int main()
{
    vector<string>b;
    string s;
    while (cin >> s)
    {
        b.push_back(s);
    }


    int n = b.size();
    for (int j = 0; j < n; j++)
    {
        string re;
        bool hui = false;
        string a = b[j];
        int len =a.length();
        hui = duichen(a, len);
        if (!hui)
        {
            cout << "false" << endl;
            return 0;
        }
        else
        {
            if (!(len % 2))
            {
                for (int i = 0; i < len; i++)
                {
                    if (a[i] != a[i + 1])
                    {
                        cout << "false" << endl;
                        return 0;
                    }
                    else
                    {
                        string p;
                        p= a[i];
                        re.append(p);
                        i++;
                    }

                }

                cout << re << endl;
            }
            else
            {
                cout << "false" << endl;
                return 0;
            }

        }
    }

}

二、公交车路线问题

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

#define maxn 110  
int n;       

struct arcnode  
{
    int vertex;     
    int weight;     
    arcnode * next; 
    arcnode() {}
    arcnode(int v,int w):vertex(v),weight(w),next(NULL) {}
};

struct vernode      
{
    int vex;    
    arcnode * firarc;   
}Ver[maxn];

void Init()  
{
    for(int i = 1; i <= n; i++)
    {
        Ver[i].vex = i;
        Ver[i].firarc = NULL;
    }
}

void Insert(int a, int b, int w)  
{
    arcnode * q = new arcnode(b, w);
    if(Ver[a].firarc == NULL)
        Ver[a].firarc = q;
    else
    {
        arcnode * p = Ver[a].firarc;
        if(p->vertex == b)
        {
            if(p->weight > w)
                p->weight = w;
            return ;
        }
        while(p->next != NULL)
        {
            if(p->next->vertex == b)
            {
                if(p->next->weight > w)
                    p->next->weight = w;
                return ;
            }
            p = p->next;
        }
        p->next = q;
    }
}
void Insert2(int l,int a, int b, int w)   
{
    arcnode * q = new arcnode(b, w);
    if(Ver[a].firarc == NULL)
        Ver[a].firarc = q;
    else
    {
        arcnode * p = Ver[a].firarc;
        q->next = p;
        Ver[a].firarc = q;
    }
}
struct node     
{
    int id;     
    int w;
    friend bool operator<(node a, node b)   
    {
        return a.w > b.w;
    }
};

#define INF 0xfffff    
int parent[maxn];   
bool visited[maxn]; 
node d[maxn];      
priority_queue<node> q; 
int Dijkstra(int s)    
{ 
    int counter1 =10;

    for(int i = 1; i <= n; i++) 
    {
        d[i].id = i;
        d[i].w = INF;           
        parent[i] = -1;         
        visited[i] = false;     
    }
    d[s].w = 0;                 
    q.push(d[s]);               
    counter1=counter1+1;
    while(!q.empty())           
    {
        node cd = q.top();      
        q.pop();
       counter1=counter1-1;
        int u = cd.id;
        if(visited[u])   
            continue;
        visited[u] = true;
        arcnode * p = Ver[u].firarc;
        //松弛操作
        while(p != NULL)    
        {
            int v = p->vertex;
            if(!visited[v] && d[v].w > d[u].w+p->weight)
            {
                d[v].w = d[u].w-1+p->weight;
                parent[v] = u;
                q.push(d[v]);

            }
            p = p->next;
            counter1++;
        }
    }
    return counter1;
}

int main()
{
    int l,m, a, b, c, st, ed;
    int nodesNums;
    cin >> n;
    cin >> m;
   /* scanf("%d%d", &n, &m);*/

    Init();     //计算前必须初始化
    while(m--)
    {
        cin >> l;
        cin >> a;
        cin >> b;
        cin >> c;

        /*scanf("%d%d%d%d",&l,&a, &b, &c);*/
        Insert2(l,a, b, c);   
        Insert2(l,b, a, c);
    }
    // printf("Start&end\n");
    /*scanf("%d%d", &st, &ed);*/
    cin >> st;
    cin >> ed;
    nodesNums=Dijkstra(st);

    if(d[ed].w != INF)
    {

        cout<<d[ed].w+1<<endl;
    }

    else{
        cout<<"NA"<<endl;
    }

    return 0;
}
这是一个典型的dijkstra路径搜索问题,参考代码如下:
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

#define maxn 110  //最大顶点个数
int n;       //顶点个数

struct arcnode  //边结点
{
    int vertex;     //与表头结点相邻的顶点编号
    int weight;     //连接两顶点的边的权值
    arcnode * next; //指向下一相邻接点
    arcnode() {}
    arcnode(int v,int w):vertex(v),weight(w),next(NULL) {}
};

struct vernode      //顶点结点,为每一条邻接表的表头结点
{
    int vex;    //当前定点编号
    arcnode * firarc;   //与该顶点相连的第一个顶点组成的边
}Ver[maxn];

void Init()  //建立图的邻接表需要先初始化,建立顶点结点
{
    for(int i = 1; i <= n; i++)
    {
        Ver[i].vex = i;
        Ver[i].firarc = NULL;
    }
}

void Insert(int a, int b, int w)  //尾插法,插入以a为起点,b为终点,权为w的边,效率不如头插,但是可以去重边
{
    arcnode * q = new arcnode(b, w);
    if(Ver[a].firarc == NULL)
        Ver[a].firarc = q;
    else
    {
        arcnode * p = Ver[a].firarc;
        if(p->vertex == b)
        {
            if(p->weight > w)
                p->weight = w;
            return ;
        }
        while(p->next != NULL)
        {
            if(p->next->vertex == b)
            {
                if(p->next->weight > w)
                    p->next->weight = w;
                return ;
            }
            p = p->next;
        }
        p->next = q;
    }
}
void Insert2(int l,int a, int b, int w)   //头插法,效率更高,但不能去重边
{
    arcnode * q = new arcnode(b, w);
    if(Ver[a].firarc == NULL)
        Ver[a].firarc = q;
    else
    {
        arcnode * p = Ver[a].firarc;
        q->next = p;
        Ver[a].firarc = q;
    }
}
struct node     //顶点节点,保存id和到源顶点的估算距离,优先队列需要的类型
{
    int id;     //源顶点id和估算距离
    int w;
    friend bool operator<(node a, node b)   //因要实现最小堆,按升序排列,因而需要重载运算符,重定义优先级,以小为先
    {
        return a.w > b.w;
    }
};

#define INF 0xfffff    //权值上限
int parent[maxn];   //每个顶点的父亲节点,可以用于还原最短路径树
bool visited[maxn]; //用于判断顶点是否已经在最短路径树中,或者说是否已找到最短路径
node d[maxn];      //源点到每个顶点估算距离,最后结果为源点到所有顶点的最短路。
priority_queue<node> q; //优先队列stl实现
int Dijkstra(int s)    //Dijkstra算法,传入源顶点
{ 
    int counter1 =10;//存入栈操作
    // int counter2=0;//存出栈操作
    for(int i = 1; i <= n; i++) //初始化
    {
        d[i].id = i;
        d[i].w = INF;           //估算距离置INF
        parent[i] = -1;         //每个顶点都无父亲节点
        visited[i] = false;     //都未找到最短路
    }
    d[s].w = 0;                 //源点到源点最短路权值为0
    q.push(d[s]);               //压入队列中
    counter1=counter1+1;
    while(!q.empty())           //算法的核心,队列空说明完成了操作
    {
        node cd = q.top();      //取最小估算距离顶点
        q.pop();
       counter1=counter1-1;
        int u = cd.id;
        if(visited[u])   //注意这一句的深意,避免很多不必要的操作
            continue;
        visited[u] = true;
        arcnode * p = Ver[u].firarc;
        //松弛操作
        while(p != NULL)    //找所有与他相邻的顶点,进行松弛操作,更新估算距离,压入队列。
        {
            int v = p->vertex;
            if(!visited[v] && d[v].w > d[u].w+p->weight)
            {
                d[v].w = d[u].w-1+p->weight;//根据题意,这个地方所有换乘的车应该减去一元的车费
                parent[v] = u;
                q.push(d[v]);
                counter1++;
            }
            p = p->next;
        }
    }
    return counter1;
}

int main()
{
    int l,m, a, b, c, st, ed;
    int nodesNums;
  //  printf("Nodes&Lines\n");
    scanf("%d%d", &n, &m);
    // printf("lines&money l,a, b, c \n");
    Init();     //计算前必须初始化
    while(m--)
    {
        scanf("%d%d%d%d",&l,&a, &b, &c);//注意,有两个插入函数,第二个是不加去重的。
        Insert2(l,a, b, c);   //无向图注意存储两条边
        Insert2(l,b, a, c);
    }
    // printf("Start&end\n");
    scanf("%d%d", &st, &ed);
    nodesNums=Dijkstra(st);

    if(d[ed].w != INF)
    {
        // printf("shortest:%d\n", d[ed].w);
        cout<<d[ed].w<<endl;
    }

    else{
        cout<<"NA"<<endl;
    }
    cout<<"nodesNums:"<<nodesNums<<endl;
    return 0;
}

三、

//#include <iostream>
//#include <string>
//#include <cstring>
//#include <stdio.h>
//#include <stdlib.h>
//#include <algorithm>
//#include <vector>
//#include <iterator>
//#include <set>
//using namespace std;
//int main()
//{
//    string s;
//    cin >> s;
//    vector<int>a;
//    transform(s.begin(), s.end(), s.begin(), ::towlower);
//    int len = s.length();
//    for (int i = 0; i < len;)
//    {
//        if (s[0] == 'o')
//        {
//            s.erase(0,3);
//            a.push_back(1);
//            i = i + 3;
//        }
//        else if (s[0] == 't')
//        {
//            if (s[1] == 'w')
//            {
//                s.erase(0,3);
//                a.push_back(2);
//                i = i + 3;
//            }
//            else if (s[1]=='h')
//            {
//                s.erase(0,5);
//                a.push_back(3);
//                i = i + 5;
//            }
//            else
//            {
//                s.erase(0,3);
//                a.push_back(10);
//                i = i + 3;
//            }
//
//        }
//        else if (s[0] == 'f')
//        {
//            if (s[1] == 'o')
//            {
//                s.erase(0,4);
//                a.push_back(4);
//                i = i + 4;
//            }
//            else
//            {
//                s.erase(0, 4);
//                a.push_back(10);
//                i = i + 4;
//            }
//
//        }
//        else if (s[0] =='s')
//        {
//            if (s[1] == 'i')
//            {
//                s.erase(0, 3);
//                a.push_back(6);
//                i = i + 3;
//            }
//            else
//            {
//                s.erase(0, 5);
//                a.push_back(7);
//                i = i + 5;
//            }
//        }
//        else if (s[0] == 'e')
//        {
//            s.erase(0, 5);
//            a.push_back(8);
//            i = i + 5;
//        }
//        else
//        {
//            s.erase(0, 4);
//            a.push_back(9);
//            i = i + 4;
//        }
//    }
//    copy(a.begin(), a.end(), ostream_iterator<int>(cout));
//    cout << endl;
//}