华为笔试题4月14日

文章目录

• • 第一题 反转每对括号间的子串
  • • 题目
    • 解析
  • 第二题 自动驾驶计速
  • • 题目
    • 解析
  • 第三题 无线设备传输
  • • 题目
    • 解析

第一题 反转每对括号间的子串

题目

给出一个字符串s（仅包含小写英文字母和括号），请你按照从内层到外层的顺序，逐层反转每对匹配括号内包含的字符串，并返回最终的结果。

输入描述：输入为一行带有括号的字符串
输出描述：反转括号内字符串并输出

示例：(u(love)i) 经过内层括号翻转变成(uevoli)，再经过翻转得到iloveu。

解析

实现思路： 以 abc(u(love)i)ab 为例，从左向右遍历字符串时，会出现括号里有括号的情况。对于里面的括号(love)，显然要先翻转，然后再与前面的u合并；再处理外面的括号(u(love)i)，再与前面的abc结合。这实现前面的这两步，必然需要用到栈。

#include
#include
#include 
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生成一次速度数据。

数据上报方式：

1. 周期上报：每30s上报一次，启动后的第一个速度开始计算，第一帧需要上报。
2. AEB（自动紧急制动）上报：当汽车速度比上一次生成的速度减少了9及以上时，认为触发AEB流程，如果连续2s均保持AEB状态，触发AEB上报，上报内容有：（1）本次AEB过程中的所有速度数据，触发AEB前2s的数据和AEB结束后2s的数据。（2）该范围内的数据中如果包含了已经周期上报的数据，重复上报。（3）如果两次AEB上报的数据有重叠，重叠数据上报一次。
3. 在满足AEB上报条件时会立刻暂停周期上报，即此时即使进入周期上报的周期也不再上报了。在AEB上报结束后重新启动周期上报，新的周期从AEB上报的最后一个数据开始计算。

请根据输入的速度信息，输出上报到云端的内容。

解析

此题比较长，能做出本题在于细心审题。如果觉得考虑所有情况很麻烦，只写周期上报也是能通过一些案例的。

#include
using namespace std;vector<int> uploadSpeeds(vector<int>& speed){vector<int> ret;int len = speed.size();int lastAEB = -1; //prevent repeating reportint timer = 1; //normal timerint curAEB = 0; //the timer for AEBbool AEB = false; //is current AEBret.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++;elsecurAEB==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]);}}elsecurAEB = 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
#include
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; //清零，从头开始遍历 }elsei++; //如果不是最佳的传送距离，则继续往后找 }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;
} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！