笔试题目
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;
//}
个人资料
推荐圈子
上一篇：
暴风影音2018届校园招聘技术类笔试题
下一篇：2018华为校招机试题目
猜你感兴趣的圈子：
标签： ivec、dp、int、len、cyqueue、面试题
