华为笔试题4月14日

朱雀 2023-01-15 08:06 124阅读 0赞

### 文章目录 ###

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

--------------------

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

### 题目 ###

**给出一个字符串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生成一次速度数据。

数据上报方式：

1.  周期上报：每30s上报一次，启动后的第一个速度开始计算，第一帧需要上报。
2.  AEB（自动紧急制动）上报：当汽车速度比上一次生成的速度减少了9及以上时，认为触发AEB流程，如果连续2s均保持AEB状态，触发AEB上报，上报内容有：（1）本次AEB过程中的所有速度数据，触发AEB前2s的数据和AEB结束后2s的数据。（2）该范围内的数据中如果包含了已经周期上报的数据，重复上报。（3）如果两次AEB上报的数据有重叠，重叠数据上报一次。
3.  在满足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;
    }