美团（23届春招）前端笔经

3.11 19:00 笔试

平台：赛码网；时间：120min；总分100分

题型：单选20*2分=40分；专项选择10*2分=20分；编程2*20分=40分

一、单选题（计算机基础相关）

1、进程有4页，页面使用顺序1.23,1.2 3 ,12 3 43.2,1，物理块数分为3，OPT算缺页次数？

2、广义表的深度和长度？

3、8个并发进程，4个资源，不会死锁的最少资源？

4、目标串T="aaabbbab"，模式串P="ab”。采用朴素匹配算法。判断匹配成功需要比较几趟？

5、平衡二叉对中含有54节点，则该树的最大深度为 8 ？

6、存储过程的特点

7、MR模型shuffle阶段的步骤

8、动态规划步骤？

9、了防盗链技术，系统管理员采集数据时需要指定http请求报文头的字段是(？

10、已知IP划分，判断合法ip

11、Dijkstra算法求解图的最短路径

12、单处理机系统中有99个进程，就绪进程最多最少

13、Mysql中使用视图的限制不包括？

14、的真前缀

15、数据库隔离级别

16、视频使用的传输层协议

二、专项选择

跟行测差不多，规律题、数学题……

三、编程题（acm模式）

题1（20分）：

题目描述：

小美有一个由数字字符组成的字等串，现在她想对这个字符串进行一些修改。具体地，她可以将这个字符串中任意位置字符修改为任意的数字字符。她想知道，至少进行多少次修改，可以使得修改后的字符串不包含两个连相同的字符?

例如，对于字符串”111222333”。她可以进行3次格故将其变为”121212313”

输入描述：

一行，一个字符串s，s只包含数字字符 (1≤s≤100000）

输出描述：

输出一个非负整数，代表所求的答案。

样例输入：

111222333

样例输出：

3

解题思路：从前往后遍历数组，碰到连续相同的字符就记录连续个数，直到第一个不连续的字符，加上前面的次数f=n/2向下取整（通过55%）

function test(str) {
  let arr = str.split("");
  let len = arr.length;
  let res = 0;

  let temp = arr[0];
  let l1 = 1;
  for (let i = 1; i <= len; i++) {
    if (i < len && arr[i] === temp) {
      l1++;
      continue;
    } else {
      if (l1 > 1) res += Math.floor(l1 / 2);
      temp = arr[i];
      l1 = 1;
    }
  }
  console.log("res:", res);
}
// test('111115222')

题1（20分）：

题目描述：

小美是一位天文爱好者，她收集了接下来一段时问中所有会划过她所在的观测地上空的流星信息。n个流星在地所在观测地上空的出现时刻和消失时刻。对于一个流星，若其的出现时刻为s，消失时刻对t，那么小关在时间段[s,t]都能够观测到它。对于一个时刻，观测地上空出现的流星数量越多越好。小关希望能够选择一个最佳的时处进行观测，观测到最多流星，现在小关想知道，在这个最佳时刻，她最多能观测别多少个流星以及一共有多少个最佳时刻可供她选择

输入描述：

一第一行是一个正整数n，表示流显的教量

第二行是n个用空格隔开的正整数，第i个数s_i表示第i个流显的出明时间。

第三行是n个用空格隔开的正整数，第i个数t_i表示第i个流早的消失时同

输出描述：

输出一行用空格隔开的两个数x和y，其中x表示能观测到的最多流星数，y表示可供她选择的最佳时刻数量

样例输入：

3

2 1 5

6 3 7

样例输出：

2 4

解题思路：区间两两对比求交集，并将当前交集的整数时间点作为key存入map 值为该时间点出现的数量，当时没写完

function test(n, str1, str2) {
  let arr1 = str1.split("");
  let arr2 = str2.split("");
  let res = new Map();
  for (let i = 0; i < arr1.length; i++) {
	let start1 = arr1[i];
    let end1 = arr2[i];
    for (let j = i + 1; j < arr1.length; j++) {
	  let start2 = arr1[j];
      let end2 = arr2[j];
      if (start2 >= start1 && start2 <= end1) {
        for (let k = start2; k <= end1; k++) {
          if (res.has(k)) {
            res[k] = res[k] + 1;
          } else {
            res.set(k, 2);
          }
        }
      }else if (end2 >= start1 && end2 <= end1) {
        for (let k = start1; k <= end2; k++) {
          if (res.has(k)) {
            res[k] = res[k] + 1;
          } else {
            res.set(k, 2);
          }
        }
      }
    }
  }
  let l1 = Array.from(res.values())
  l1.sort()
  let a = l1[0]
  let count = l1.lastIndexOf(a) + 1
  console.log(a，count )
  console.log("res:", l1);
}
test(3, "215", "637");