🔥大厂常考的算法题和手写题 II

前沿

金三银四又是一波跳槽季，总结一下前端面试中遇到的算法题和手写题。

实现 testPurcase 函数

描述：
函数 purcase 是已实现的下单函数, 参数分别为 onOrder onPay onBuy, 且必须要保证三个函数执行顺序是 onOrder => onPay => onBuy 且存在异步执行的可能, 实现一个测试函数 testPurcase ， 入参是 purcase 函数， 即是 testPurcase(purcase)。onOrder onPay onBuy 三个函数的类型为: (err, data) => void, testPurcase 返回的是 Promise， 只有当 onOrder onPay onBuy 三个函数按照顺序执行且执行结果 err 均为 null 时 Promise状态才 resolve 其它均是 reject。

示例： 
输入：purcase((err, data) => {console.log('onOrder')}, onPay: (err, data) => {setTimeout(() => {console.log('onPay')}, 1000)}, (err, data) => {console.log('onBuy')}); 其中 onOrder 函数执行 err 非空  
输出：false 

约束： 
1. onOrder onPay onBuy 三个函数的类型为: (err, data) => void
2. testPurcase 返回 Promise

解题:
function testPurcase(purcase) {
    const result = [];
    return new Promise((resolve, reject) => {
        const onOrder = (err, data) => {
            if (err) {
                reject(err);
            } else {
                result.push(data);
            }
        };
        const onPay = (err, data) => {
            if (err) {
                reject(err);
            } else {
                const len = result.length;
                if (len !== 1) {
                    reject('function that is not executed');
                } else {
                    result.push(data);
                }
            }
        };
        const onBuy = (err, data) => {
            if (err) {
                reject(err);
            } else {
                const len = result.length;
                if (len !== 2) {
                    reject('function that is not executed');
                } else {
                    result.push(data);
                    resolve(result);
                }
            }
        };
        
        purcase(onOrder, onPay, onBuy);
    });
}

实现 flatten(obj) 函数

描述：
实现一个 flatten(obj) 函数将对象进行拉平

示例：
输入：{a: 1, b: [3], c: {d: 4}}
输出：{a: 1, 'b[0]': 3, 'c.d': 4}

约束： 
1. 仅针对对象和数组进行拉平

解题：

function flatten(obj, prefix = '', result = {}) {
    // 遍历对象的每一个属性
    for (let key in obj) {
        if (obj.hasOwnProperty(key)) {
            let pref = prefix.length ? prefix + '.' : '';
            // 如果属性值类型是对象且非数组，则递归调用flatten
            if (typeof obj[key] === 'object' && !Array.isArray(obj[key])) {
                flatten(obj[key], pref + key, result);
            } else if (Array.isArray(obj[key])) { // 处理数组，将其转换为对象键
                obj[key].forEach((item, index) => {
                    flatten(item, `${pref}${key}[${index}]`, result);
                });
            } else { // 如果不是对象或数组，直接添加到结果对象
                result[pref + key] = obj[key];
            }
        }
    }
    return result;
}

无重复字符的最长子串

描述：
给定一个字符串 `s` ，请你找出其中不含有重复字符的最长子串的长度。

示例：
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

约束：
1. `0 <= s.length <= 5 * 104`
2. `s` 由英文字母、数字、符号和空格组成

解题：
function lengthOfLongestSubstring(s: string): number {
    const str: string[] = [];
    let ans = 0;
    for (let i = 0; i < s.length; i++) {
        const val = s[i];
        if (str.includes(val)) {
            const index = str.indexOf(val);
            str.splice(0, index + 1);
        }
        str.push(val);
        ans = Math.max(ans, str.length);
    }
    return ans;
};

最大子数组和

描述：
给你一个整数数组 `nums` ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。

示例：
输入： nums = [-2,1,-3,4,-1,2,1,-5,4]
输出： 6
解释： 连续子数组 [4,-1,2,1] 的和最大，为 6 。

约束：
1. `1 <= nums.length <= 105`
2. `-104 <= nums[i] <= 104`

解题：
function maxSubArray(nums: number[]): number {
   let ans = Number.MIN_SAFE_INTEGER;
   let sum = 0;
   for(let i = 0; i < nums.length; ++i) {
       sum = nums[i] + Math.max(sum, 0);
       ans = Math.max(ans, sum);
    }
    return ans;
};

缺失的第一个正数

描述：
给你一个未排序的整数数组 `nums` ，请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 `O(n)` 并且只使用常数级别额外空间的解决方案。

示例：
输入： nums = [1,2,0]
输出： 3
解释： 范围 [1,2] 中的数字都在数组中。

约束：
1. `1 <= nums.length <= 105`
2. `-231 <= nums[i] <= 231 - 1`

解题：
function firstMissingPositive(nums: number[]): number {
    const numbers = Array.from({length: nums.length}, (_, index) => index + 1);
    for (const val of nums) {
        const index = val - 1;
        if (numbers[index] === val) {
            numbers[index] = nums.length + 2;
        }
    }
    const formatNumbers = numbers.filter((item) => item !== numbers.length + 2);
    return formatNumbers.length ? formatNumbers[0] : nums.length + 1;
};

react 中 $$typeof 的作用

在 React 中，$$typeof 是一个内部属性，用于标记 React 元素、组件和其他对象的类型。这个属性主要用于安全和内部操作的目的，特别是为了防止 XSS（跨站脚本攻击）。

XSS 防护

React 使用 $$typeof 属性来确保在渲染过程中处理的对象确实是 React 元素。当 React 元素通过 JSX 或者 React.createElement 方法创建时，React 会给这个对象添加一个 $$typeof 属性。这样，当对象被传递到渲染流程中时，React 可以检查 $$typeof 属性，以确保它是一个合法的 React 元素。这样做可以防止攻击者注入原始的 HTML 或者 JavaScript，这对于防止 XSS 攻击来说非常重要。

值和类型

对于 React 元素，$$typeof 的值通常是 Symbol.for('react.element')。React 还可能为不同的类型使用不同的 Symbol.for() 值，比如对于 React ForwardRef 元素，其值为 Symbol.for('react.forward_ref')。使用 Symbol 有助于确保这些值的唯一性，减少了与用户代码发生冲突的可能性。

总之，$$typeof 是 React 内部用于鉴别和安全检查的一种机制，它确保渲染流程中处理的对象是安全和预期的 React 对象，帮助防止 XSS 攻击。

BFC 的理解

BFC，全称为 块格式化上下文（Block Formatting Context） ，是 Web 页面的一种 CSS 渲染模式。理解 BFC 对于编写高效、布局合理的 CSS 代码非常重要，它决定了元素如何对其内容进行布局，以及与其他元素之间的关系和相互作用。

BFC的工作原理和特性

1. 垂直布局：在 BFC 中，盒子（box）是按照垂直方向依次排列的。
2. 盒子垂直方向的距离由 margin 决定：在 BFC 中相邻的盒子的垂直间距由它们的 margin 决定。值得注意的是，属于同一个 BFC 的相邻 Box 的上下 margin 会发生重叠。
3. BFC 的区域不会与浮动元素的 box 重叠：布局上，BFC 可以看做是隔离了浮动元素和非浮动元素，使内部元素与外部元素相互独立。
4. 计算 BFC 的高度时，浮动元素也参与计算：即便内部子元素浮动，也不会影响到外部元素的高度计算。

创建 BFC 的条件

BFC 不是总是存在的，只有符合一定条件的元素才会生成 BFC，这些条件包括：

1. 根元素（<html>）
2. 浮动元素（元素的 float 不是 none）
3. 绝对定位元素（position 为 absolute 或 fixed）
4. display 值为 inline-block、table-cell、table-caption、flex、inline-flex、grid 或 inline-grid 的元素
5. overflow 值不为 visible 的元素

BFC 的应用场景

1. 防止 margin 重叠：在同一个 BFC 中的两个相邻 Box 可能会发生 margin 重叠的现象。通过创建新的 BFC，可以防止相邻元素的 margin 发生重叠。
2. 清除内部浮动（清除浮动的影响） ：在父元素上创建 BFC 可以包含其内部浮动元素，避免父元素高度坍塌。
3. 制作侧边栏布局：侧边栏和主内容区域需要分开布局时，可通过 BFC 实现两栏不重叠的效果。

总之，BFC 创建了一个独立的渲染区域，其中的元素布局不受外界影响，同时也不会影响到这个环境之外的元素。合理利用 BFC，可以在不引入额外标记的情况下，高效解决 CSS 布局中遇到的许多难题，提升页面布局的灵活性和可维护性。

EventLoop

// js 进程宏任务
setTimeout(function () {
    console.log(1); // 宏任务
}); 
new Promise(function (resolve,reject) {
    console.log(2);
    resolve(3);
}).then(function (val){
    console.log(val); // 微任务
});
console.log(4);

// 2 4 3 1

this

const obj = {
    name: 'obj',
    sayName: () => {
        console.log(this.name);
    },
};
const sayName = obj.sayName;
sayName(); // undefined
obj.sayName(); // undefined