4.14 华为笔试题解
题目比较简单，一共三道题，leetcode medium难度。前两道题都全A了。第三道题是lc45，我A了95%，有一个用例没有通过，但是把code贴到lc是能过的。可能题目和原题还是不太一样吧。有懂的大佬可以说说这个用例是咋回事。
反转字符串
题目
将()中的字符串翻转，并在输出中删除括号。括号可迭代，如输入为 (uoy(love)i)，输出为(iloveyou)。先翻转内层括号，再翻转外层括号。输出要删除掉所有括号。我感觉这题是今天最难的一题。。
code
思路为栈。用栈维护 '(' 的下标，遇到 ')' 出栈，并翻转之间的子串。
#include<bits/stdc++.h>
using namespace std;
void swap(char& a, char& b){
char t = a;
a = b;
b = t;
}
void reverse(string& s, int l, int r){
while(l<r)
{
swap(s[l], s[r]);
l++;
r--;
}
}
string stringCore(string& s){
int len = s.length();
stack<int> leftP;
string ret = "";
for(int i=0;i<len;i++)
{
if(s[i]=='(')
leftP.push(ret.size());
else if(s[i]==')')
{
int l = leftP.top();
leftP.pop();
reverse(ret, l, ret.size()-1);
}
else{
ret += s[i];
}
}
return ret;
}
int main(){
//string s;
//cin>>s;
string s = "(((asdfg)asdfg)asdfg(asdfg)asdfg)asdfg(asdfghjkl)";
cout<<stringCore(s)<<endl;
} 自动驾驶计速
题目
题目比较复杂，我这里就不写了。
大概是一个考验代码能力的设计类题目，需要注意的是AEB结束后的2s内是需要判断下一次AEB的。要点见注释。
code
#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;
}
跳跃游戏II
题目
见LC45。题目大概是一样的，可能有一个小小的区别，导致有1个样例我没有通过。但是我没有发现这个区别。
code
贪心算法。每次循环遍历当前位置到可达的最大位置，并更新下一次遍历的最大位置。#include<bits/stdc++.h>
using namespace std;
int minTrans(vector<int>& dev){
int ret = 0;
int maxGet = 0;
int pre = 0;
while(maxGet<dev.size()-1)
{
int curGet = maxGet;
for(int i=pre;i<=curGet;i++)
{
maxGet = max(maxGet, dev[i]+i);
}
ret++;
pre = curGet+1;
}
return ret;
}
int main(){
while(true){
int n;
cin>>n;
vector<int> dev(n);
for(int i=0;i<n;i++)
{
cin>>dev[i];
}
cout<<minTrans(dev)<<endl;
}
} 
