华为2018届校园招聘软件开发岗笔试题

笔试题目

1、括号匹配

//01 括号匹配  

#define _CRT_SECURE_NO_WARNINGS  

/*

括号匹配

给定一个字符串,里边可能包含“()”、“[]”、“{}”三种括号,请编写程序检查该字符串中的括号是否成对出现,且嵌套关系正确。

输出:true:若括号成对出现且嵌套关系正确,或该字符串中无括号字符;

false:若未正确使用括号字符。

实现时,无需考虑非法输入。

输入描述:

输入为:

字符串

例子:(1+2)/(0.5+1)

输出描述:

输出为:

字符串

例子:true

*/   


代码:

#include <iostream>  
#include <cstring>  
#include <string>  
#include <map>  
#include <vector>  
#include <algorithm>  
using namespace std;  
bool isLeft(char a)  
{  
   return (a == '(') || (a == '[') || (a == '{');  
}   
bool isRight(char a)  
{  
   return (a == ')') || (a == ']') || (a == '}');  
}   
bool isMatch(char a, char b)  
{  
   if(a == '('&&b == ')')  
   {  
       return true;  
   }  
   else if(a == '['&&b == ']')  
   {  
       return true;  
   }  
   else if(a == '{'&&b == '}')  
   {  
       return true;  
   }  
   return false;  
}  
 
int main()  
{  
#if 0  
   freopen("in.txt", "r", stdin);  
   //freopen("out.txt", "w", stdout);  
#endif  
   string str;  
   vector<char> cvec;  
   cvec.reserve(200);  
   while(cin >> str)  
   {  
       auto iter = str.begin();  
       for(; iter != str.end(); ++iter)  
       {  
           //左括号直接进栈  
           if(isLeft(*iter))  
           {  
               cvec.push_back(*iter);  
           }  
           //如果出现右括号  
           else if(isRight(*iter))  
           {  
               //不合理情况1: 栈空的话,直接退出    这里情况一开始忘记考虑,但是华为机试仍然100%通过  
               if(cvec.empty())  
               {  
                   break;  
               }  
               char c = cvec.back();  
               cvec.pop_back();  
               //不合理情况2:判断栈中左括号与现在的右括号是否匹配  
               if(!isMatch(c, *iter))  
               {  
                   break;  
               }  
           }  
       }  
       //处理不合理情况1,2  以及不合理情况3:字符已经遍历结束,但是栈仍然非空  
       if(iter != str.end()||!cvec.empty())  
       {  
           cout << "false" << endl;  
       }  
       else  
       {  
           cout << "true" << endl;  
       }  
   }  
   return 0;  
}  

2、 打印队列

//02 打印机任务  

#define _CRT_SECURE_NO_WARNINGS  

/*

打印机任务

简要描述:

某个打印机根据打印机队列执行打印任务,打印任务分为九个优先级,分别用数字1~9表示,数字越大优先级越高。打印机每次从队列头部取出第一个任务A,然后检查队列余下任务中有没有比A优先级更高的任务,则将任务A放在队列尾部,否则就执行任务A的打印。请编写一个程序,根据输入的打印队列,编出实际的打印顺序。

输入描述:

函数原型: void printOrder(const int input[], int len, int output[])

输入参数input表示打印队列,为一个由整数1~9(优先级)组成的数组,数组索引0表示打印队列头部。对于C/C++,参数len表示input数组的长度。可以假定输入的参数总是合法有效的,input数组长度有可能为0,但不会是空指针。

输出为一个表示实际打印顺序的数组,其数组项为打印任务在输入数组中的索引值(从0开始)。Java通过返回值输出。C/C++通过输出参数output[]输出,可以假定为存放结果分配了足够的空间

。。。。题目其余部分没有记录,有人记录的,可以希望在留言处补全,大家一起分享交流。

输入样例:

9, 3, 5

输出样例:

0, 2, 1

*/   

#define _CRT_SECURE_NO_WARNINGS  
#include <iostream>  
#include <cstring>  
#include <string>  
#include <map>  
#include <vector>  
#include <algorithm>  
using namespace std;   
#define MAX 500   
int input[MAX];   
//循环队列的结点数据元素  
struct QNode  
{  
   int num;  
   int idx;  
};  
 
typedef struct Que  
{  
   QNode* elem;  
   int front;  
   int rear;  
   int len;  
   int sz;  
}CyQueue;  
 
void initQueue(CyQueue& Q)  
{  
   Q.front = Q.rear = 0;  
   Q.len = Q.sz = 0;  
   Q.elem = nullptr;  
}  
 
bool isEmpty(CyQueue Q)  
{  
   return Q.len == 0;  
}  
 
int nextIdx(CyQueue Q, int cur)  
{  
   return (cur + 1) % (Q.sz + 1);  
}  

 

//Q 非空  
//返回循环队列的最大优先级的索引号  
int getMax(CyQueue Q)  
{  
   int maxNum = Q.front;  
   int i = nextIdx(Q, Q.front);  
   for(; i != Q.rear; i = nextIdx(Q, i))  
   {  
       if(Q.elem[i].num > Q.elem[maxNum].num)  
       {  
           maxNum = i;  
       }  
   }  
   return maxNum;  
}  
 
//删除节点  
void Pop(CyQueue& Q)  
{  
   Q.front = nextIdx(Q, Q.front);  
   --Q.len;  
}  
 
//获得队头元素  
QNode getFront(CyQueue& Q)  
{  
   return Q.elem[Q.front];  
}  
 
//插入节点  
void Push(CyQueue& Q, QNode& q)  
{  
   Q.elem[Q.rear] = q;  
   Q.rear = nextIdx(Q, Q.rear);  
   ++Q.len;  
}  
 
//主函数  打印序列  
void printOrder(const int input[], int len, int output[])  
{  
   CyQueue Q;  
   initQueue(Q);  
   Q.len = len;  
   Q.sz = len + 1;  
   Q.elem = new QNode[len + 1];  
   for(int i = 0; i < len; ++i)  
   {  
       Q.elem[i].num = input[i];  
       Q.elem[i].idx = i;  
   }  
   Q.front = 0;  
   Q.rear = len;  
   int numOut = 0;  
   while(!isEmpty(Q))  
   {  
       int pos = getMax(Q);  
       for(int i = Q.front; i != pos; i = nextIdx(Q, i))  
       {  
           QNode q = getFront(Q);  
           Pop(Q);  
           Push(Q, q);  
       }  
       QNode q = getFront(Q);  
       output[numOut++] = q.idx;  
       Pop(Q);  
   }  
}  
 
int main()  
{  
#if 1  
   freopen("in01.txt", "r", stdin);  
   //freopen("out.txt", "w", stdout);  
#endif  
   int len = 0;  
   int num;  
   char c;  
   while(cin >> num)  
   {  
       //处理逗号的输入  
       cin >> c;  
       input[len++] = num;  
   }  
   int output[MAX] = {0};  
   printOrder(input, len, output);  
 
   for(int i = 0; i < len; ++i)  
   {  
       if(i != len - 1)  
       {  
           cout << output[i] << ", ";  
       }  
       else  
       {  
           cout << output[i];  
       }  
   }  
   return 0;  
} 

3、平安果

#define _CRT_SECURE_NO_WARNINGS  

/*

平安果

简要描述:

给定一个M行N列的矩阵(M*N个格子),每个格子中放着一定数量的平安果。

你从左上角的各自开始,只能向下或者向右走,目的地是右下角的格子。

每走过一个格子,就把格子上的平安果都收集起来。求你最多能收集到多少平安果。

注意:当经过一个格子时,需要一次性把格子里的平安果都拿走。

限制条件:1<N,M<=50;每个格子里的平安果数量是0到1000(包含0和1000).

输入描述:

输入包含两部分:

第一行M, N

接下来M行,包含N个平安果数量

输出描述:

一个整数

最多拿走的平安果的数量

示例:

输入

2 4

1 2 3 40

6 7 8 90

输出

136


代码:

#include <vector>  
#include <iostream>  
using namespace std;  
 
//一道简单的dp问题  
int main()  
{  
#if 1  
   freopen("in.txt", "r", stdin);  
#endif  
   int m, n;  
   while(cin >> m >> n)  
   {  
       vector<vector<int>> ivec(m, vector<int>(n));  
       for(int i = 0; i < m; ++i)  
       {  
           for(int j = 0; j < n; ++j)  
           {  
               cin >> ivec[i][j];  
           }  
       }  
       vector<vector<int>> dp(ivec);  
       //--------预处理  
       //初始化dp第一列  
       for(int i = 1; i < m; ++i)  
       {  
           dp[i][0] += dp[i - 1][0];  
       }  
       //初始化dp第一行  
       for(int j = 1; j < n; ++j)  
       {  
           dp[0][j] += dp[0][j - 1];  
       }  
       //计算dp的其他部分  
       for(int i = 1; i < m; ++i)  
       {  
           for(int j = 1; j < n; ++j)  
           {  
               //原始dp[i][j]==ivec[i][j],所以这里没有另外再加+ivec[i][j]  
               dp[i][j] += (dp[i - 1][j] < dp[i][j - 1]) ? dp[i][j - 1] : dp[i - 1][j];  
           }  
       }  
       cout << dp[m - 1][n - 1] << endl;  
   }  
   return 0;  
}  
 
//以下为自己提交代码,想的直接用递归求解,但是如果数据量很大的话,这种方法容易爆栈。  
//int getAppleIn(vector<vector<int> >& ivec, int m, int n, int row, int col)  
//{  
//  if(row >= m||col >= n)  
//  {  
//      return 0;  
//  }  
//  else if(row == m - 1)  
//  {  
//      int sum = 0;  
//      for(int i = col; i < n; ++i)  
//      {  
//          sum += ivec[row][i];  
//      }  
//      return sum;  
//  }  
//  else if(col == n - 1)  
//  {  
//      int sum = 0;  
//      for(int i = row; i < m; ++i)  
//      {  
//          sum += ivec[i][col];  
//      }  
//      return sum;  
//  }  
//  else  
//  {  
//      int sum = ivec[row][col];  
//      int sum1 = getAppleIn(ivec, m, n, row + 1, col);  
//      int sum2 = getAppleIn(ivec, m, n, row, col + 1);  
//      return sum + (sum1 < sum2 ? sum2 : sum1);  
//  }  
//}  
//  
//int getApple(vector<vector<int> >& ivec, int m, int n)  
//{  
//  int sum = getAppleIn(ivec, m, n, 0, 0);  
//  return sum;  
//}  
//  
//int main()  
//{  
//#if 1  
//  freopen("in.txt", "r", stdin);  
//#endif  
//  int m, n;  
//  vector<vector<int>> ivec;  
//  while(cin >> m >> n)  
//  {  
//      for(int i = 0; i < m; ++i)  
//      {  
//          vector<int> tem;  
//          for(int j = 0; j < n; ++j)  
//          {  
//              int num;  
//              cin >> num;  
//              tem.push_back(num);  
//          }  
//          ivec.push_back(tem);  
//      }  
//      int res = getApple(ivec, m, n);  
//      cout << res;  
//  }  
//  return 0;  
//}  

个人资料
crazybean
等级:8
文章:61篇
访问:15.7w
排名: 5
上一篇: 暴风影音2018届校园招聘技术类笔试题
下一篇:2018华为校招机试题目
猜你感兴趣的圈子:
华为笔试面试圈
标签: ivec、dp、int、len、cyqueue、面试题
隐藏