第一题 反转每对括号间的子串
题目
给出一个字符串s（仅包含小写英文字母和括号），请你按照从内层到外层的顺序，逐层反转每对匹配括号内包含的字符串，并返回最终的结果。
输入描述：输入为一行带有括号的字符串
输出描述：反转括号内字符串并输出
示例：(u(love)i) 经过内层括号翻转变成(uevoli)，再经过翻转得到iloveu。
解析
实现思路： 以 abc(u(love)i)ab 为例，从左向右遍历字符串时，会出现括号里有括号的情况。对于里面的括号(love)，显然要先翻转，然后再与前面的u合并；再处理外面的括号(u(love)i)，再与前面的abc结合。这实现前面的这两步，必然需要用到栈。
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
string func(string s)
{
stack<string> stk;
string word = "";
for(char c : s)
{
if(c=='(')
{
stk.push(word); //把当前(前的一段字母存入栈中
word=""; //清零，重新记录新的一段字母
}
else if(c==')')
{
reverse(word.begin(), word.end()); //翻转
word = stk.top()+word; //加上括号前最近的一段字符串
stk.pop();
}
else
{
word.push_back(c);
}
}
return word;
}
int main()
{
string str;
cin>>str;
cout<<func(str)<<endl;
return 0;
}
第二题 自动驾驶计速
题目
建立云端数据库，汽车将自身的运行信息上报到云端，汽车自身每隔0.5s生成一次速度数据。
数据上报方式：
- 周期上报：每30s上报一次，启动后的第一个速度开始计算，第一帧需要上报。
- AEB（自动紧急制动）上报：当汽车速度比上一次生成的速度减少了9及以上时，认为触发AEB流程，如果连续2s均保持AEB状态，触发AEB上报，上报内容有：（1）本次AEB过程中的所有速度数据，触发AEB前2s的数据和AEB结束后2s的数据。（2）该范围内的数据中如果包含了已经周期上报的数据，重复上报。（3）如果两次AEB上报的数据有重叠，重叠数据上报一次。
- 在满足AEB上报条件时会立刻暂停周期上报，即此时即使进入周期上报的周期也不再上报了。在AEB上报结束后重新启动周期上报，新的周期从AEB上报的最后一个数据开始计算。
请根据输入的速度信息，输出上报到云端的内容。
解析
此题比较长，能做出本题在于细心审题。如果觉得考虑所有情况很麻烦，只写周期上报也是能通过一些案例的。
#include<bits/stdc++.h>
using namespace std;
vector<int> uploadSpeeds(vector<int>& speed){
vector<int> ret;
int len = speed.size();
int lastAEB = -1; //prevent repeating report
int timer = 1; //normal timer
int curAEB = 0; //the timer for AEB
bool AEB = false; //is current AEB
ret.push_back(speed[0]);
for(int i=1;i<len;i++)
{
//在AEB状态下，单独处理
if(AEB==true)
{
//判断AEB结束
if(speed[i-1]-speed[i]<9)
{
for(int j=0;j<4;j++)
if(i+j<len)
{
ret.push_back(speed[i+j]);
//这里需要注意，在AEB结束的2s内是需要判断下一次AEB的
if(speed[i+j-1]-speed[i+j]>=9)
curAEB++;
else
curAEB==0;
}
timer = 0;
lastAEB = i+3;
i += 3;
AEB = false;
}
else{
ret.push_back(speed[i]);
}
}
//判断AEB开始
else if(speed[i-1]-speed[i]>=9)
{
curAEB++;
if(curAEB>=4){
curAEB = 0;
AEB = true;
timer = 0;
//找前四个点，看是不是比上一次的末尾大，推入
for(int j=i-7;j<=i;j++)
if(j>lastAEB)
ret.push_back(speed[j]);
}
}
else
curAEB = 0;
//正常计速
if(timer==60&&!AEB)
{
timer = 0;
ret.push_back(speed[i]);
}
timer++;
}
return ret;
}
int main(){
int n;
cin>>n;
vector<int> speed(n);
for(int i=0;i<n;i++)
{
cin>>speed[i];
}
vector<int> upload = uploadSpeeds(speed);
int len = upload.size();
for(int i =0;i<len-1;i++)
cout<<upload[i]<<',';
cout<<upload[len-1]<<endl;
}
第三题 无线设备传输
题目
无线设备传输过程中，数据经常需要通过各种中继设备进行中转。有某段传输路径，每隔1km放置1个中继设备用于数据中转，现用一数组来描述包括起始点的所有中继设备的最大传输距离。求从起点到终点，能完成信号传输的最少中转次数。
输入描述：
4
2 3 1 1
第一行代表总共中转设备台数，4台
第二行表示各中转设备的最大传输能力。
解析
读完这道题目，发现这是一道跳跃游戏类的题，只是把问题实际化了。所以本题可以用贪心算法来做，贪心算法的主要思想就是由局部最优得到全局最优。
比如输入是【2，1，3，1，2】，本题想得到的最少的中转次数。我们可以从尾往前看：先找到能一次达到尾巴的最远点，即3的位置；第二步，再找3之前能到达3的最远的，那么直接就是2。由局部最优得全局最优，得到最小中转次数，也就是2次。
#include<iostream>
#include<vector>
using namespace std;
int jump(vector<int>& nums)
{
int count = 0; //记录中转次数
int len = nums.size(); //记录中转站台的数量
int i=0;
while(len>1)
{
if(nums[i]>=len-1-i) //当前站台的传送距离>距离尾距离
{
count++; //计数
len = i+1; //更新剩下的站台数量
i=0; //清零，从头开始遍历
}
else
i++; //如果不是最佳的传送距离，则继续往后找
}
return count;
}
int main()
{
int n=0;//数组元素数量
cin>>n;
vector<int> input(n);//初始化数组
for(int i=0; i<n; ++i)
cin>>input[i];
cout<<jump(input)<<endl;
return 0;
}
转载：https://blog.csdn.net/wjinjie/article/details/115979659
查看评论