首页 > 4.14 华为笔试题解
头像
伏尔塔瓦尔河的纤夫
编辑于 2021-04-19 19:30
+ 关注

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;
        }
}




全部评论

(3) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐