TP-LINK杭州秋招提前批-前端二面面经
这一面答得有点烂,看别人面经考智力题,结果临时抱佛脚扑了个空,我这主要就是做了一道题
同样聊聊你自己的学习经历,为什么投前端?
讲一讲JS的垃圾回收机制:引用计数和标记清除
刷过题吗,考你一道:
,把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; };#TP-LINK##校招##前端工程师##面经#