前端面试题+算法题（二）

一、LeeCode 算法题

1、643. 子数组最大平均数 I

题目：给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。请你找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。任何误差小于 10-5 的答案都将被视为正确答案。

场景1：输入 nums = [1,12,-5,-6,50,3], k = 4 输出 12.75

场景2：输入 nums = [5], k = 1 输出 5.0000

小编思路：

var findMaxAverage = function (nums, k) {
  let sum = null
  let asn = -Infinity
  for (let i = 0; i < nums.length; i++) {
    if (i < k) {
      sum += nums[i]
    } else {
      sum += nums[i] - nums[i - k]
    }
    if (i >= k - 1) {
      asn = Math.max(asn, sum / k)
    }
  }
  return asn;
};

官方题解：

var findMaxAverage = function(nums, k) {
    let sum = 0;
    const n = nums.length;
    for (let i = 0; i < k; i++) {
        sum += nums[i];
    }
    let maxSum = sum;
    for (let i = k; i < n; i++) {
        sum = sum - nums[i - k] + nums[i];
        maxSum = Math.max(maxSum, sum);
    }
    return maxSum / k;
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/maximum-average-subarray-i/solutions/590322/zi-shu-zu-zui-da-ping-jun-shu-i-by-leetc-us1k/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2、645. 错误的集合

题目：集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。给定一个数组 nums 代表了集合 S 发生错误后的结果。请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

场景1：输入 nums = [1,2,2,4] 输出 [2,3]

场景2：输入 nums = [1,1] 输出 [1,2]

小编思路：

sort()方法：对nums进行从小到大的排序
第一个for()循环：找出重复的数
splice()方法：去除一个重复数
第二个for()循环：找出不连续的数，即是丢失的数字
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findErrorNums = function (nums) {
  nums.sort((a, b) => a - b);
  let repeat = null;// 重复
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === nums[i + 1]) {
      repeat = nums[i]
      nums.splice(i,1)
    }
  }
  for (let j = 0; j < nums.length; j++) {
    if(nums[j] !== j+1){
      return [repeat, j+1]
    }
  }
  return [repeat, nums.length+1]
};
官方题解1：排序

将 nums 数组排序，n 为 nums 数组长度

重复的数：相邻两个元素相等
丢失的数：
丢失的数大于等于 1 且小于 n，则相邻两个元素的差等于2，两个数间的值即为丢失的数字
丢失的数是 n ，则 nums 的最后一个数不等于 n
var findErrorNums = function(nums) {
    const errorNums = new Array(2).fill(0);
    const n = nums.length;
    nums.sort((a, b) => a - b);
    let prev = 0;
    for (let i = 0; i < n; i++) {
        const curr = nums[i];
        if (curr === prev) {
            errorNums[0] = prev;
        } else if (curr - prev > 1) {
            errorNums[1] = prev + 1;
        }
        prev = curr;
    }
    if (nums[n - 1] !== n) {
        errorNums[1] = n;
    }
    return errorNums;
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/set-mismatch/solutions/857255/cuo-wu-de-ji-he-by-leetcode-solution-1ea4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
官方题解2：哈希表

第一个for()循环：记录每个数字出现的次数
第二个for()循环：
重复的数字，会在数组中出现 2 次
丢失的数字，会在数组中出现 0 次
var findErrorNums = function(nums) {
    const errorNums = new Array(2).fill(0);
    const n = nums.length;
    const map = new Map();
    for (const num of nums) {
        map.set(num, (map.get(num) || 0) + 1);
    }
    for (let i = 1; i <= n; i++) {
        const count = map.get(i) || 0;
        if (count === 2) {
            errorNums[0] = i;
        } else if (count === 0) {
            errorNums[1] = i;
        }
    }
    return errorNums;
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/set-mismatch/solutions/857255/cuo-wu-de-ji-he-by-leetcode-solution-1ea4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

3、674. 最长连续递增序列

题目：给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

场景1：输入 nums = [1,3,5,4,7] 输出 3

场景2：输入 nums = [2,2,2,2,2] 输出 1

小编思路：

reduce()方法：遍历nums，并返回
对于 reduce() 方法不理解的小伙伴，可以看下小编的这篇文章：ES6新特性详解-CSDN博客

当前一项比后一项小，则说明还在递增当前递增长度+1，同时如果超出已记录的最大长度，则赋值给最大长度
否则重新开始记录递增长度
/**
 * @param {number[]} nums
 * @return {number}
 */
var findLengthOfLCIS = function(nums) {
  let maxLength = 1;
  let curLength = 1;
  nums.reduce((pre,cur)=>{
    if(pre < cur){
      curLength++;
      if(maxLength < curLength){
        maxLength = curLength;
      }
    } else {
      curLength = 1;
    }
    return cur
  })
  return maxLength;
};
官方题解：贪心

for() 循环：当不是递增时，则更新 start 起始下标
Math.max()方法：每次循环判断当前记录的最大长度与更新下标后哪个长度更大，则取哪个长度
var findLengthOfLCIS = function(nums) {
    let ans = 0;
    const n = nums.length;
    let start = 0;
    for (let i = 0; i < n; i++) {
        if (i > 0 && nums[i] <= nums[i - 1]) {
            start = i;
        }
        ans = Math.max(ans, i - start + 1);
    }
    return ans;
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/longest-continuous-increasing-subsequence/solutions/573383/zui-chang-lian-xu-di-zeng-xu-lie-by-leet-dmb8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

4、682. 棒球比赛

题目：你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表 ops，其中 ops[i] 是你需要记录的第 i 项操作，ops 遵循下述规则：

整数 x - 表示本回合新获得分数 x
"+" - 表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。
"D" - 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。
"C" - 表示前一次得分无效，将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。

请你返回记录中所有得分的总和。

场景1：输入 ops = ["5","2","C","D","+"] 输出 30

场景2：输入 ops = ["5","-2","4","C","D","9","+","+"] 输出 27

场景3：输入 ops = ["1"] 输出 1

小编思路：

arr 记录每次有效分数，num1 前两次的有效得分，num2 前一次的有效得分
forEatch() 方法：分别判断 nums 为 4 种情况的计分处理，同时更新num1，num2值
/**
 * @param {number[]} nums
 * @return {number}
 */
var findLengthOfLCIS = function(nums) {
  let maxLength = 1;
  let curLength = 1;
  nums.reduce((pre,cur)=>{
    if(pre < cur){
      curLength++;
      if(maxLength < curLength){
        maxLength = curLength;
      }
    } else {
      curLength = 1;
    }
    return cur
  })
  return maxLength;
};
官方题解：

主要是将 if() 换成 switch()
var calPoints = function(ops) {
    let ret = 0;
    const points = [];
    for (const op of ops) {
        const n = points.length;
        switch (op[0]) {
            case '+':
                ret += points[n - 1] + points[n - 2];
                points.push(points[n - 1] + points[n - 2]);
                break;
            case 'D':
                ret += 2 * points[n - 1];
                points.push(2 * points[n - 1]);
                break;
            case 'C':
                ret -= points[n - 1];
                points.pop();
                break;
            default:
                ret += parseInt(op);
                points.push(parseInt(op));
                break;
        }
    }
    return ret;
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/baseball-game/solutions/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

5、697. 数组的度

题目：给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

场景1：输入 nums = [1,2,2,3,1] 输出 2

场景2：输入 nums = [1,2,2,3,1,4,2] 输出 6

其他思路：

定义map：记录每个数值的开始下标，结束下标，个数（分别对应 degree 的0，1，2）
第一个forEatch() ：
如果map存在当前数值，则更新结束下标，计数+1
如果map不存在当前数值，则初始化该数值开始、结束下标为当前循环下标，初始计数为1

定义minLen、maxCount：最小长度、数组的度
第二个forEatch()：
如果当前循环计数大于当前记录的最大计数（度），则更新最大计数（度），最小长度
如果当前循环计数等于当前记录的最大计数（度），则更新最小长度
var findShortestSubArray = function (nums) {
  const map = new Map();
  nums.forEach((item, index) => {
    if (map.has(item)) {
      const degree = map.get(item);
      degree[1] = index; //right
      degree[2]++; //计数
      map.set(item, degree);
    } else {
      const degree = [index, index, 1];
      map.set(item, degree);
    }
  });

  let minLen = nums.length + 1;
  let maxCount = 0;
  map.forEach((item) => {
    if (item[2] > maxCount) {
      maxCount = item[2];
      minLen = item[1] - item[0] + 1;
    } else if (item[2] === maxCount) {
      minLen = Math.min(minLen, item[1] - item[0] + 1);
    }
  });
  return minLen;
};
官方题解：

思路和上面相似，只是实现方式不同
var findShortestSubArray = function(nums) {
    const mp = {};

    for (const [i, num] of nums.entries()) {
        if (num in mp) {
            mp[num][0]++;
            mp[num][2] = i;
        } else {
            mp[num] = [1, i, i];
        }
    }
    
    let maxNum = 0, minLen = 0;
    for (const [count, left, right] of Object.values(mp)) {
        if (maxNum < count) {
            maxNum = count;
            minLen = right - left + 1;
        } else if (maxNum === count) {
            if (minLen > (right - left + 1)) {
                minLen = right - left + 1;
            }
        }
    }
    return minLen;
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/degree-of-an-array/solutions/610337/shu-zu-de-du-by-leetcode-solution-ig97/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

二、面试题

1、Less 和 Scss 的区别

Less 和 SCSS 都是 CSS 的预处理器，它们允许开发者使用更强大和灵活的语法来编写样式表，从而提高开发效率和代码的可维护性

（1）语法差异

①Less

语法与标准 CSS 有所不同，更接近 js 的语法
用 . 定义类选择器，# 定义 ID 选择器，> 定义子选择器
使用较少的特殊字符，eg：变量定义以 @ 开头，Mixin 以 . 开头，选择器嵌套使用 &

@primary-color: #333;
.header {
  background-color: @primary-color;
}

②SCSS

语法更接近标准的 CSS ，会保留标准 CSS 的所有特性
用缩进或大括号 {} 定义选择器，用分号 ; 定义分隔属性
支持嵌套规则、变量、运算符等

$primary-color: #333;
.header {
  background-color: $primary-color;
}

（2）编译方式

①Less

通常以 .less 为扩展名

②SCSS

通常以 .scss 为扩展名

二者编译后均生成纯 CSS 文件，文件扩展名为 .css

（3）兼容性

①Less

在早期版本中对 CSS 语法更宽松，较容易与现有的 CSS 文件集成。最新版本的 Less 也支持更严格的 CSS 语法

②SCSS

采用更接近标准 CSS 的语法，更易上手

（4）社区和生态系统

①Less

在生态系统方面较早出现，会有一些基于 Less 的工具和库，相较于 SCSS 使用率较低
插件和工具支持不够丰富，尤其是与现代前端开发工具链的集成可能不如 SCSS 无缝

②SCSS

与生态系统整合紧密
有大量的插件和工具支持，与现代前端开发工具链的集成非常好

（5）性能

①Less

Less 的性能通常优于 SCSS，尤其在处理大量代码时，Less 的编译速度更快

②SCSS

SCSS 在处理大量嵌套和变量时，会比 Less 稍微慢一些

2、link 标签和 import 标签的区别？

（1）用法

① <link>

<link> 标签是 HTML 标记，用于在 HTML 文档的 <head> 部分中引入外部 CSS 文件
其属性有： rel（关系）、href（资源链接）、type （MIME类型）等

<head>
  <link rel="stylesheet" href="style.css">
</head>

② @import

CSS 规则，用于在 CSS 样式表中引入外部 CSS 文件
必须位于 CSS 样式表中，通常放在样式表的顶部

@import url("style.css");

（2）加载时机

① <link>

引入的资源通常在页面加载时，同步加载 CSS 文件
这样并行执行不会阻止页面的渲染（阻塞页面渲染，但不会阻塞解析）

② @import

通常用于异步加载，当控制台开始执行遇到 import 语句时，对应的文件才会被加载
这样会阻止页面的渲染，导致页面渲染延迟

（3）兼容性

① <link>

可用于所有 HTML 版本

② @import

其规则是 CSS2 引入的特性，旧版浏览器可能不支持

（4）可维护性

① <link>

与 HTML 文档分开，更容易维护和管理，且可以在文档的 <head> 部分轻松找到

② @import

引入的 CSS 文件与 CSS 代码混在一起，会导致维护复杂度增加

3、Js 中的隐藏类是什么？以下哪段代码运行效率更高？

答案：左边例1的效率更高，因为重用了隐藏类（Hidden Class）

（1）隐藏类

隐藏类是指V8引擎（Google Chorme 和 Node.js 使用的 JS 引擎）中的一种优化机制
JS是一门动态语言，V8引擎会为每个JS对象分配一个隐藏类，以便更快找到属性所在的内存位置

（2）测试案例

// 测试代码
console.time("a");//例1
for (let i = 0; i < 1000000; i++) {
  const obj = {};
  obj["a"] = i;
}
console.timeEnd("a");

console.time("b");//例2
for (let i = 0; i < 1000000; i++) {
  const obj = {};
  obj[`${i}`] = i;
}
console.timeEnd("b");

（3）分析案例

①方案一：User1

第 1 次循环，i=0，执行 new User1(`User_0`, 0); 时
- 执行第一行：V8会生成一个叫 Hidden Class 0{} 的类
- 执行第二行：添加一个叫 name 的属性。V8会生成一个新的 Hidden Class 1 带上 name 属性，并在 Class 0 上标记内存偏移量指向 Class 1。当前 Class 1 则用于表示当前所执行的代码
- 执行第三行：添加 age 属性。V8会生成一个新的 Hidden Class 2 带上 age 属性，并在 Class 1 上标记内存偏移量指向 Class 2。当前 Class 2 则用于表示实例化出来的真实对象
第 2 次循环时，V8会寻找能够代表当前代码的隐藏类
- 执行第一行：如果有寻找到，则直接使用。因此会找到 Class 0，并分配给当前代码
- 执行第二行：会找到 Class 1
- 执行第三行：会找到 Class 2

综上，即使这段代码在执行1,000万次，哪怕更多的循环，V8始终在利用这三个隐藏类来表示这段代码，不用新建新的隐藏类来进行表示

②方案二：User2

第 1 次循环，i=0，执行 new User2(`User_0`, 0); 时
- 执行第一行：同方案一是一样，都生成一个隐藏类 Hidden Class 0
- 执行第二行：用 name 的值 User_0 来作为属性名，因此V8会建一个新的 Hidden Class 1，带上 User_0 参数，并在 Class 0 上标记 User_0 的内存偏移指针，指向 Class 1，当前 Class 1 标记所执行的代码
- 执行第三行：同上，新建 Hidden Class 2 类

与方案一相同都是只生成了3个隐藏类【到目前为止V8所消耗的性能和方案一是一致的】

第 2 次循环时，i=1，执行 new User2(`User_1`, 1); 时
- 执行第一行：同理还是可以找到 Class 0
- 执行第二行：由于 name 的参数变为 User_1，原来并没有一个隐藏类可以与之对应。因此V8需要新建新的隐藏类 Hidden Class 3，并在 Class 0 上标记 User_1 的指针偏移，指向 Class 3
- 执行第三行：需要再新建一个隐藏类 Hidden Class 4，在原来的 Class 3 上新建 age 的指针偏移量，指向 Class 4（指当前正在执行的这段实例化出来的代码）

综上，当执行1,000万次循环时，V8则要针对这段代码实例化2,000万个隐藏类

③总结

方案二比方案一耗时多出许多的原因是：建隐藏类的过程，造成了极大的性能损耗

function User1(name, age) {
  this.name = name; // age 为固定属性
  this.age = age; // age 为固定属性
}
console.time("例1耗时");
for (let i = 0; i < 10000000; i++) {
  new User1(`User_${i}`, i);
}
console.timeEnd("例1耗时");

function User2(name, age) {
  this[name] = name; // name 为动态属性
  this.age = age; // age 为固定属性
}
console.time("例2耗时");
for (let i = 0; i < 10000000; i++) {
  new User2(`User_${i}`, i);
}
console.timeEnd("例2耗时");

（4）优化建议

①在构造函数中初始化所有属性，尽量避免“添加动态属性”的场景

②始终按照同样属性顺序构建对象，使得隐藏类可以得到重用

③不要加载未初始化或已经删除的属性

4、数组的快速模式、字典模式是什么？以下哪段代码效率更高？

答案：左边效率更高，因为利用了数组的快速模式

（1）数组模式

V8会以不同的形式去存储 JS 的数组

①快速模式

对应 C 语言的数组来对 JS 的数组进行存储，具备速度快，紧凑的特点

触发机制：索引从 0 到 length-1 且无空洞或预分配数组小于100000，无论有无空洞

②字典模式

对应 C 语言的哈希表，具备速度慢，松散的特点

触发机制：预分配数组大于等于100000，且数组有空洞

（2）测试案例

// 测试代码
console.time('a');
const arr1 = [];
for (let i = 0; i < 10000000; i++) {
  arr1[i] = 1;
}
console.timeEnd('a');

console.time('b');
const arr2 = [];
arr2[10000000 - 1] = 1;
for (let i = 0; i < 10000000; i++) {
  arr2[i] = i;
}
console.timeEnd('b');

（3）优化策略

①从 0 开始连续的初始化数组，以避免数组进入字典模式

②不要预分配一个超大数组（如长度大于等于 100000）

③删除数组元素时让数组保持紧凑，尽可能避免使用 delete

④不要访问未初始化或已删除的数组元素

5、以下代码什么时候成立？

if (a == 1 && a == 2 && a == 3) {
  console.log("结果成立");
}

结果如下：

const a = {
  i: 1,

  valueOf: function() {
    return this.i++;
  }
}

if (a == 1 && a == 2 && a == 3) {
  console.log("结果成立");
}