腾讯校招笔试思路分享

分数： 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(n²/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;
}

#腾讯##笔试题目##前端工程师##校招#