华为笔试题4月14日_最小中转次数

---

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

题目

给出一个字符串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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

---

第二题 自动驾驶计速

题目

建立云端数据库，汽车将自身的运行信息上报到云端，汽车自身每隔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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

---

第三题 无线设备传输

题目

无线设备传输过程中，数据经常需要通过各种中继设备进行中转。有某段传输路径，每隔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;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33