華為筆試題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;
}

第二題 自動駕駛計速

題目

建立云端資料庫，汽車將自身的運行資訊上報到云端，汽車自身每隔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;
}