2021腾讯校招前端第二次笔试题总结

发表于 更新于 分类于

2021腾讯校招前端第二次笔试题总结

两个有序的数组合并成一个

这题就是我上面说的能 ac100%，但是因为粗心只 ac 了 60%…。

原因就是腾讯的笔试题都是采用的标准输入输出。

所有的输入数据都要手动的处理成我们想要的样子。

V8 的输入输出就是readline（读取一行）和print（打印一行）。

这题给的样例输入输出如下（没记错应该是这个样例）。

1
2
3
4
5
6
输入：
1,2,4
1,3,4

输出：
1,1,2,3,4,4

也就是读取两行，转成数组再操作。

可是我傻逼了，用了split(',')之后忘记转成数字了…

这就导致了算法没错，但是比较的结果出错了。

1
2
"3" > "122"; // true
3 > 122; // false

整体的算法如下（这个就是归并排序中每一次合并的一个算法）。

这题应该考察双指针的知识点吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
function merge(arr1, arr2) {
  let i = 0;
  let j = 0;
  let k = 0;
  const result = [];
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      result.push(arr1[i]);
      i++;
    } else {
      result.push(arr2[j]);
      j++;
    }
    k++;
  }

  // 这里防止两个数组有一个没遍历完成，要直接把剩下的元素push的结果集的末尾
  if (i < arr1.length) {
    for (k = i; k < arr1.length; k++) {
      result.push(arr1[k]);
    }
  } else {
    for (k = j; k < arr2.length; k++) {
      result.push(arr2[k]);
    }
  }

  return result;
}

const arr1 = readline()
  .split(",")
  .map((s) => Number.parseInt(s));
const arr2 = readline()
  .split(",")
  .map((s) => Number.parseInt(s));

const result = merge(arr1, arr2);

print(result.join(","));

写到中间想起来没转成数字这件事，写着写着又给忘了…

JSON的扁平化

题意大致就是有一个对象，每秒会记录当时的点击量。

要求给你一个这个对象的json格式，转成数组形式。

1
2
3
4
5
输入：
{ "1": 123, "2": 234, "8": 7 }

输出：
[123, 234, 0, 0, 0, 0, 0, 7]

这题很快就ac了还是相当开心的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function fn(str) {
  const obj = JSON.parse(str);

  const result = [];

  // 得到所有的key，也就是所有的秒数
  Object.keys(obj).forEach((item) => {
    const i = Number.parseInt(item);
    if (i > 0 && i <= Number.MAX_SAFE_INTEGER) {
      // 索引为秒数 - 1
      result[i - 1] = obj[i];
    }
  });

  for (let i = 0; i < result.length; i++) {
    // 找空位，以0代替
    if (result[i] === undefined) {
      result[i] = 0;
    }
  }

  return result;
}

const str = readline();
const result = fn(str);
// json形式输出
print("[" + result.join(",") + "]");

计算中位数

给定一个长度为n（n 为偶数）的数组，问如果删除每一位之后，剩下的n - 1位的数组中位数是多少。

1
2
3
4
5
6
7
8
9
10
11
输入：
6
1 2 3 4 5 6

输出
4       // 删除1之后，剩下的数组中位数为4
4       // 删除2之后，剩下的数组中位数为4
4       // 删除3之后，剩下的数组中位数为4
3       // 删除4之后，剩下的数组中位数为3
3       // 删除5之后，剩下的数组中位数为3
3       // 删除6之后，剩下的数组中位数为3

这题我觉得我思路应该是没错的。

思路就是我们要先保存原来的索引，然后对这个数组进行排序。

由于数组的长度是偶数，我们可以知道。

如果删除了前 n / 2 个数中的某一个，那么中位数一定是第 n / 2 + 1 个。

如果删除了后 n / 2 个数中的某一个，那么中位数一定是第 n / 2 个。

可以以他的样例1 2 3 4 5 6。

如果删除了3前面的任意一个数，包括3，那么中位数就会落到4这个数字上。

  • 2 3 4 5 6
  • 1 3 4 5 6
  • 1 2 4 5 6

如果删除了4后面的任意一个数，包括4，那么中位数就会落到3这个数字上。

  • 1 2 3 5 6
  • 1 2 3 4 6
  • 1 2 3 4 5

理解上面之后就可以写代码了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
function fn(n, arr) {
  // 保存每个数字原来位置的索引
  // 这里要注意原题目并没有说数组不重复，所以存一个索引数组
  const map = {};
  for (let i = 0; i < arr.length; i++) {
    if (map[arr[i]] === undefined) {
      map[arr[i]] = [i];
    } else {
      map[arr[i]].push(i);
    }
  }

  // 排序，开始求中位数
  arr.sort();
  // 右中位数的索引
  const rightMid = n / 2;
  // 左中位数的索引
  const leftMid = rightMid - 1;
  // 两者对应的值
  const rightMidVal = arr[rightMid];
  const leftMidVal = arr[leftMid];

  const result = [];
  // 删除[0, leftMid]索引中的其中一个值，剩下的中位数一定是rightMidVal
  for (let j = 0; j <= leftMid; j++) {
    // 得到这个数原来对应的索引位置
    const indexArr = map[arr[j]];
    // 写入结果集
    for (let i = 0; i < indexArr.length; i++) {
      result[indexArr[i]] = rightMidVal;
    }
  }
  // 删除[rightMid, arr.length)索引中的其中一个值，剩下的中位数一定是leftMidVal
  for (let j = rightMid; j < arr.length; j++) {
    // 跟上面同理
    const indexArr = map[arr[j]];
    for (let i = 0; i < indexArr.length; i++) {
      result[indexArr[i]] = leftMidVal;
    }
  }

  return result;
}

// 输入
const n = Number.parseInt(readline());
const arr = readline()
  .split(" ")
  .map((s) => Number.parseInt(s));

const result = fn(n, arr);
// 输出
result.forEach((val) => print(val));

写的时候紧张了，这题也应该拿下的。

Dom题：实现一个日期的组件

这个确实做不出来… 因为对日期的API不是特别的熟悉。

html代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
<div id="js-container">
  <div class="calendar">
    <table>
      <thead>
        <tr>
          <th class="pre">←</th>
          <th colspan="5" class="date">2020.01</th>
          <th class="next">→</th>
        </tr>
        <tr>
          <th>一</th>
          <th>二</th>
          <th>三</th>
          <th>四</th>
          <th>五</th>
          <th>六</th>
          <th>日</th>
        </tr>
      </thead>
      <tbody>
        <tr>
          <td></td>
          <td>1</td>
          <td>2</td>
          <td>3</td>
          <td>4</td>
          <td>5</td>
          <td>6</td>
        </tr>
        <tr>
          <td>7</td>
          <td>8</td>
          <td>9</td>
          <td>10</td>
          <td>11</td>
          <td>12</td>
          <td>13</td>
        </tr>
        <tr>
          <td>14</td>
          <td>15</td>
          <td>16</td>
          <td>17</td>
          <td>18</td>
          <td>19</td>
          <td>20</td>
        </tr>
        <tr>
          <td>21</td>
          <td>22</td>
          <td>23</td>
          <td>24</td>
          <td>25</td>
          <td>26</td>
          <td>27</td>
        </tr>
        <tr>
          <td>28</td>
          <td>29</td>
          <td>30</td>
          <td></td>
          <td></td>
          <td></td>
          <td></td>
        </tr>
      </tbody>
    </table>
  </div>
</div>

css样式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
.current {
  background-color: #4b8cff;
  color: white;
}

#js-container {
  display: flex;
  justify-content: center;
  margin-top: 30px;
}

table {
  border-spacing: 0;
  border-collapse: collapse;
}

table td,
table th {
  width: 100px;
  height: 40px;
  border-left: 1px solid #c1c1c1;
  text-align: center;
}

table tr td:last-child,
table tr th:last-child {
  border-right: 1px solid #c1c1c1;
}

table tr {
  border-top: 1px solid #c1c1c1;
}

table tr:last-child {
  border-bottom: 1px solid #c1c1c1;
}

js如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function Calendar(year, month) {
  this.month = month;
  this.year = year;
  this.el = null; // TODO 挂载元素
  if (!this.el) {
    return;
  }
  this.el.addEventListener("click", (event) => {
    const target = event.target;
    const isPre = target.classList.contains("pre");
    const isNext = target.classList.contains("next");
    if (!isPre && !isNext) {
      return;
    }
    // TODO 更新month和year
    this.el.innerHTML = this.innerHTML();
  });

  this.innerHTML = function () {
    const year = +this.year || 0;
    const month = (+this.month || 0) - 1;
    const date = new Date();
    // TODO 生成html字符串
    return "";
  };
}

这题就要我们填充三个TODO。

前两个TODO还好， 比较简单，难度在第三个TODO。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
function Calendar(year, month) {
  this.month = month;
  this.year = year;
  this.el = document
    .getElementById("js-container")
    .getElementsByClassName("calendar")[0]
    .getElementsByTagName("table")[0];
  if (!this.el) {
    return;
  }
  this.el.addEventListener("click", (event) => {
    const target = event.target;
    const isPre = target.classList.contains("pre");
    const isNext = target.classList.contains("next");
    if (!isPre && !isNext) {
      return;
    }
    if (isPre) {
      // 点击了上一个月
      if (this.month === 1) {
        this.year--;
        this.month = 12;
      } else {
        this.month--;
      }
    } else if (isNext) {
      // 点击了下一个月
      if (this.month === 12) {
        this.year++;
        this.month = 1;
      } else {
        this.month++;
      }
    }
    this.el.innerHTML = this.innerHTML();
  });

  this.innerHTML = function () {
    const year = +this.year || 0;
    const month = (+this.month || 0) - 1;
    const cur = new Date(); // 当前时间

    let xq = new Date(year, month, 1).getDay();
    // 因为getDay中星期天返回的是0，我们需要把他设置为索引第6位，同时星期1到6设置成对应0-5的索引
    // 我们只会获取第一天，因为完成整个日期数组并不会需要用到这个getDay()的API
    // 我们只需要第一天正确的在数组里面的位置即可
    xq = xq === 0 ? 6 : xq - 1;
    // 获取这个月有多少天，这里设置为天数设置为0的意思是，获取上一个月的最后一天是这个月中的第几天
    // 所以我们其实是获取了下一个月(month + 1)的上一个月(month)的最后一天处于那个月的第几天
    // 而第几天也就意味着这个月有多少天（范围 1 - 31）
    const day = new Date(year, month + 1, 0).getDate();
    const r = [];

    for (let i = 0; i < day; i++) {
      const j = i + xq;
      const row = Math.floor(j / 7);
      const col = j % 7;
      if (r[row] === undefined) {
        r[row] = [];
      }
      // 如果正好是这个月的当天，就把对应的天数设置成负数
      if (
        cur.getDate() === i + 1 &&
        cur.getMonth() === month &&
        cur.getFullYear() === year
      ) {
        r[row][col] = -(i + 1);
      } else {
        r[row][col] = i + 1;
      }
    }

    let trs = "";
    for (let i = 0; i < r.length; i++) {
      let tds = "";
      for (let j = 0; j < 7; j++) {
        if (r[i][j] !== undefined) {
          // 负数设置当天的样式
          if (r[i][j] < 0) {
            tds += `<td class="current">${-r[i][j]}</td>`;
          } else {
            tds += `<td>${r[i][j]}</td>`;
          }
        } else {
          tds += `<td></td>`;
        }
      }
      trs += `<tr>${tds}</tr>`;
    }

    return `<thead>
              <tr>
                <th class="pre"><</th>
                <th colspan="5" class="date">
                  ${this.year}
                  .
                  ${this.month < 10 ? "0" + this.month : this.month}
                </th>
                <th class="next">></th></tr>
              <tr>
                <th>一</th><th>二</th><th>三</th><th>四</th><th>五</th><th>六</th><th>日</th>
              </tr>
          </thead>
          <tbody>
            ${trs}
          </tbody>`;
  };
  // new的时候第一次初始化
  this.el.innerHTML = this.innerHTML();
}

new Calendar(2020, 9);

写半个多小时，写出来的，期间看了MDN上的API。

昨晚考完就断断续续的想了，今天再写就不会特别的慢。

感觉非常棒的一道题。

放个运行的图：

消消乐（栈题）

写这题剩 10 分钟，还没写完系统就交卷了…

给定n个字符串，如果有两个相同的字符挨在一起，就把它们消去，消去之后的字符串如果符合规则也要继续消去，输出需要消去的次数

1
2
3
4
5
6
7
8
输入：
2
abcddcba
101

输出：
4       // 消去了dd，cc相碰消去，bb相碰消去，aa相碰消去，共消去4此
0       // 无法消去

这题我刚看到就觉得是考察栈的知识点的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
function fn(n, arr) {
  const result = [];
  for (let i = 0; i < n; i++) {
    if (arr[i].length === 0 || arr[i].length === 1) {
      result.push(0);
      continue;
    }
    const strArr = arr[i].split("");
    const stack = [];
    stack[0] = strArr[0];
    let j = 1;
    let count = 0;
    while (j < strArr.length) {
      const peek = stack[stack.length - 1];
      if (peek === strArr[j]) {
        // 消去
        count++;
        stack.length--;
      } else {
        // push进数组
        stack[stack.length] = strArr[j];
      }
      j++;
    }
    result.push(count);
  }
  return result;
}

const n = Number.parseInt(readline());
const arr = [];
for (let i = 0; i < n; i++) {
  arr.push(readline());
}

const result = fn(n, arr);
result.forEach((val) => print(val));