TP-LINK杭州秋招提前批-前端二面面经

这一面答得有点烂，看别人面经考智力题，结果临时抱佛脚扑了个空，我这主要就是做了一道题

同样聊聊你自己的学习经历，为什么投前端？

讲一讲JS的垃圾回收机制：引用计数和标记清除

刷过题吗，考你一道：

参考1004. 最大连续1的个数 III

，把0和1换成A和B。

头铁第一次用动态规划写了一遍，总算写了出来，时间空间复杂度为，可以优化空间至，面试官说有没有别的方法，提示滑动窗口，总算写了出来，

为了我加强版，参考424. 替换后的最长重复字符

，只说思路，使用空间换时间，我抄了一遍别的大佬的：

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 * 滑动窗口
 */
var characterReplacement = function(s, k) {
    // 1. 设置最高次数
    let maxTime = 0;

    // 2. 遍历字符串
    for (let i = 0; i < s.length; i++) {
        // 2.1 设置窗口起点值
        const value = s[i];

        // 2.2 设置参数
        let replaceTime = k, // 可滑动次数
        slide = i, // 滑动的下标
        time = 1; // 本次出现数

        // 2.3 向右开始滑动
        while (
            (replaceTime || s[slide + 1] === value) // 还有滑动次数或者下一个字符串相同
            && slide < s.length - 1 // 限制滑动边界 [i, s.length - 1]
        ) {
            // 每滑动一次向右移一位
            slide++;
            // 每滑动一次本次出现数 + 1
            time++;
            // 如果本次是不相同的，减少滑动次数
            if (s[slide] !== value) {
                replaceTime--;
            }
        }

        // 2.4 如果向右到顶，但是还有 replaceTime，
        // 表明向左还可以滑，那就继续向左滑动
        // 滑动前重置一下开始位置
        slide = i;

        // 2.5 向左开始滑动
        while (
            (replaceTime || s[slide - 1] === value) // 类似向右的判断
            && slide > 0 // 边界为 [0, i]
        ) {
            // 每滑动一次向左移一位
            slide--;
            // 每滑动一次本次出现数 + 1
            time++;
            // 如果本次是不相同的，减少滑动次数
            if (s[slide] !== value) {
                replaceTime--;
            }
        }

        // 2.6 将本次滑动次数汇总到最高次数中
        maxTime = Math.max(maxTime, time);
    }

    // 3. 返回结果
    return maxTime;
};

实在是太烦了，其实思路可以很简单，使用双指针

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 * 双指针
 */
var characterReplacement = function(s, k) {
    // 长度
    const n = s.length;
    // 数组
    const num = Array(26).fill(0);
    let maxn = 0;
    // 左右指针
    let left = 0, right = 0; 

    while (right < n) {
        // 统计右指针对应的字母的个数
        num[s[right].charCodeAt() - 'A'.charCodeAt()]++;
        // 比较当前最长长度和现在的最长长度
        maxn = Math.max(maxn, num[s[right].charCodeAt() - 'A'.charCodeAt()]);
        // c窗口内除了出现次数最多的那一类字符之外，剩余的字符数量不超过 k个
        if (right - left + 1 - maxn > k) {
            num[s[left].charCodeAt() - 'A'.charCodeAt()]--;
            // 左指针移动
            left++;
        }
        right++;
    }
    return right - left;
};