腾讯校招笔试思路分享
分数： 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)时间内有空，现在想要让尽可能多的人开会，给出开会时第一时区的时刻
样例：
输入：32 5 61 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;
}
