首页 > 笔经面经 > 腾讯校招笔试思路分享

腾讯校招笔试思路分享

头像
杨珏成
编辑于 2019-08-18 10:09:41 app内打开
赞 13 | 收藏 89 | 回复32 | 浏览4367
分数: 87.5 / 100 / 100 / 100 / 0(来不及)
方向:前端
2,3题好像是不同方向专有的,差异化比较大,我拿到的题比较简单
方向不一样的可以看看第1和第4题!
收藏的时候可以简单回一下贴,让更多人看到

1. 字符串解码

小明和小红用字符串压缩通信。
字符串压缩规则是:如果有连续重复的字符串比如ABCABCABC就缩写成[3|ABC]。
现有压缩后的字符串,设计一个解压程序还原字符串。
样例:
输入:
HG[3|B[2|CA]]F
输出:
HGBCACABCACABCACAF
坑点:
需要优化内存,我之所以87.5就是因为内存溢出MLE了,正在考虑用栈结构重写一次。
思路(87.5/100分):
string decode(string s) {
    string res = "", ans = "";
    int len, start , end;
    int time, counting;
    time = 0, counting = 1;
    len = s.size();
    for (int i = 0; i < len; i++)
    {
        if (s[i] == '[')
        {
            start = i;
            for (i = len; s[i] != ']'; i--);
            end = i;
            res += decode(s.substr(start + 1, end - start - 1));
            i++;
        }
        if (counting && s[i] >= '0' && s[i] <= '9')
        {
            time = time * 10 + (s[i] - '0');
        }
        else if (s[i] == '|')
        {
            counting = 0;
        }
        else
        {
            res += s[i];
        }
    }
    char tmp = res[res.size() - 1];
    if (tmp == '\0')
    {
        res = res.substr(0, res.size() - 1);
    }
    if (time > 0)
    {
        for (int i = 0; i < time; i++)
        {
            ans.append(res);
        }
    }
    else
    {
        ans = res;
    }
    return ans;
}

int main()
{
    string s;
    cin >> s;
    cout << decode(s) << endl;
    return 0;
} 

2.识别IP

判断一个ip地址是不是私有的
已知私有IP范围是:
10.0.0.0 - 10.255.255.255
172.16.0.0-172.16.255.255
192.168.0.0-192.168.255.255
127.0.0.0/8 # 注意!这里是一个巨坑,0/8的意思代表0-8,是一种简写方法,但是腾讯并没有说明其含义
样例:
输入:
0.0.0.0
输出:
false
思路(100/100分):
function isPrivate(ip){
    // TODO
    let ipVal = ip.split('.');
    ipVal[0] = Number(ipVal[0]);
    ipVal[1] = Number(ipVal[1]);
    ipVal[2] = Number(ipVal[2]);
    ipVal[3] = Number(ipVal[3]);
    if (ipVal[0] == 10) {
        if (ipVal[1] >= 0 && ipVal[1] <= 255) {
            if (ipVal[2] >= 0 && ipVal[2] <= 255) {
                if (ipVal[3] >= 0 && ipVal[3] <= 255) {
                    return true;
                }
            }
        }
    }
    if (ipVal[0] == 172) {
        if (ipVal[1] >= 16 && ipVal[1] <= 31) {
            if (ipVal[2] >= 0 && ipVal[2] <= 255) {
                if (ipVal[3] >= 0 && ipVal[3] <= 255) {
                    return true;
                }
            }
        }
    }
    if (ipVal[0] == 192) {
        if (ipVal[1] == 168) {
            if (ipVal[2] >= 0 && ipVal[2] <= 255) {
                if (ipVal[3] >= 0 && ipVal[3] <= 255) {
                    return true;
                }
            }
        }
    }
    if (ipVal[0] == 127) {
        if (ipVal[1] == 0) {
            if (ipVal[2] == 0) {
                if (ipVal[3] >= 0 && ipVal[3] <= 8) {
                    return true;
                }
            }
        }
    }
    return false;
}

3. 驼峰转换

把一个由 - 或 _ 或 @ 连接的变量词组转换成驼峰写法
样例:
输入:
content-type
输出:
contentType
思路(100/100分):
function camel(str) {
    // TODO
    let ans = "";
    let upper = false;
    for (let index = 0; index < str.length; index++) {
        const element = str[index];
        if (element == '_' || element == '-' || element == '@') {
            upper = true;
        } else {
            if (upper) {
                ans += element.toUpperCase();
            } else {
                ans += element;
            }
            upper = false;
        }
    }
    return ans;
};

4.星球开会

企鹅星球上一天有N(<200000)个小时(时间不包含0点),对应N个时区,当第1时区一点的时候第2时区已经两点了,以此类推
每个时区有Ai个人,每个时区上的人只有在[u,v)时间内有空,现在想要让尽可能多的人开会,给出开会时第一时区的时刻
样例:
输入:
3
2 5 6
1 3
输出:
3
坑点:
时区的对应有一点绕,我一开始理解成后一个时区比前一个时区落后,实际上是超前的,每后一个时区比前一个时区快1个小时,解决掉这个问题就没有大问题了。
另外要考虑一下时间复杂度的问题,我的优化比较差,最坏复杂度是O(n2/2)
思路(80/100分):
int main() {
    int n, u, v, len, pos;
    long long ans, tmp;
    cin >> n;
    vector<int> a(n, 0);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    cin >> u >> v;
    u--;
    v--;
    len = v - u;
    pos = 0;
    if (len < n / 2)
    {
        ans = 0;
        for (int i = 0; i < n; i++)
        {
            tmp = 0;
            for (int j = 0; j < len; j++)
            {
                tmp += a[(i + j) % n];
            }
            if (tmp > ans || (tmp == ans && ((n + u - pos) % n < (n + u - pos) % n)))
            {
                ans = tmp;
                pos = i;
            }
        }
    }
    else
    {
        ans = INF;
        for (int i = 0; i < n; i++)
        {
            tmp = 0;
            for (int j = 0; j < n - len; j++)
            {
                tmp += a[(i + j) % n];
            }
            if (tmp < ans || (tmp == ans && ((n + u - pos) % n < (n + u - pos) % n)))
            {
                ans = tmp;
                pos = i;
            }
        }
    }
    cout << (n + u - pos) % n + 1 << endl;
    return 0;
}



32条回帖

回帖
加载中...

本文相关内容

相关热帖

近期热帖

热门推荐