这里存放一些面试中遇到的有意思的面试题。因为最近两个多月没刷题,解题能力基本上又回去了。所以得记录一下,需要的时候快速找到感觉。
最长回文字符串 题目传送门
答案来源传送门
中心扩散法 第一个想到中心扩散法,具体分析见文章。
首先肯定得遍历一遍,逐一选择“中间点”,然后往左右扩散,重点是得想到扩散的两种情况
,
由同一个字符构造成的回文。
两端相同的回文。
自己盲解答时,没有考虑到第一个情况,导致解答失败。
代码如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 var longestPalindrome = function (s ) { const len = s.length; let result = '' for (let i = 0 ; i < len; i++) { let l = i - 1 ; let r = i + 1 ; while (l >= 0 && s[l] === s[i]) { l--; } while (r < len && s[r] === s[i]) { r++; } while (l >= 0 && r < len && s[l] === s[r]) { r++; l--; } if (result.length < r - l) { result = s.slice(l + 1 , r) } } return result };
动态规划 这是自己写的递归版动态规划,应该是中间态的动态规划。实测,耗时和耗内存都比中间扩散法大不少。
思路是:
用一个二维数组dp存储状态,dp[i][j]存储s[i…j]是否是回文。
s[i…j]是否是回文取决于s[i+1…j-1]是否是回文。则可以得到递推公式
f(i, j) = f(i+1, j-1) && s[i] === s[j]
边界情况是,如果字符串长度是1时,则肯定是回文。字符串长度为2时,如果两个字符相同,则是回文
然后考虑好边界情况,整理出一个递归公式就行。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 var longestPalindrome = function (s ) { const len = s.length; let result = '' let pre = 0 ; let after = 0 ; let dp = new Array (len) for (let i = 0 ; i < len; i++) { const newArr = new Array (len).fill(null ); dp[i] = newArr; } for (let r = 0 ; r < len; r++) { for (let l = 0 ; l <= r; l++) { const res = handlePalidrom(s, l, r, dp); if (res && r - l > after - pre) { after = r; pre = l; } } } return s.slice(pre, after + 1 ); }; function handlePalidrom (s, l, r, dp ) { const len = r - l + 1 ; if (dp[l][r] !== null ) return dp[l][r]; if (len === 1 ) { dp[l][r] = true ; return true ; } if (len === 2 && s[l] === s[r]) { dp[l][r] = true ; return true ; } if (s[l] === s[r]) { const res = handlePalidrom(s, l + 1 , r - 1 , dp); if (res) { dp[l][r] = true ; } return res; } dp[l][r] = false ; return false ; }
总结
回文字符串天生就是一个可以拆分成子问题的问题,动态规划是个不二之选。寻找好递推关系还是重中之重。
中心扩散法貌似是最长回文问题的特殊方法。但其实应该也就是动态规划,的终极形态。
缺失的第一个正数 传送门
好理解的最佳解-原地哈希
这题目有两种答案:
哈希表法 时间和空间复杂度都是O(n)
把数组变成哈希表,然后从1开始递增。如果哈希表没有,就是答案。哈希表
可以用对象,更佳的数据结构是Set,代码更简单(但是leetcode运行结果来看,Set更占内存、更耗时)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 var firstMissingPositive = function (nums ) { let set = new Set (nums); let result = nums.length + 1 ; for (let i = 1 ; i <= nums.length; i++) { if (!set.has(i)) { result = i; return result; } } return result; };
原地哈希法 时间复杂度O(n),空间O(1)
如果要求空间复杂度O(1),则说明不需要占用额外空间,首先考虑的应该是,要在当前数组操作
。
具体看传送门。这个思路大约是:
先把负数清除,都统一转换为null
,排除干扰
。如果此遍历过程发现没有1。则答案肯定是1.
顺序遍历,把当前遍历到的数字,把其数值的数组下标设置为负数。 如果数值大于数组长度,则不改,否则会修改当前数组的长度。
最后从1累加遍历数组,如果是负数,则对应下标的数是存在于原数组的。如果无负数,则就是当前的值。
如果都是负数,结果是数组长度+1;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 var firstMissingPositive = function (nums ) { const len = nums.length; let tmpArr = nums.slice(); let hasOne = false ; for (let i = 0 ; i < len; i++) { const val = tmpArr[i]; if (val === 1 ) { hasOne = true ; } if (val < 1 ) { tmpArr[i] = null } else { tmpArr[i] = val } } if (!hasOne) return 1 ; for (let i = 0 ; i < len; i++) { let val = Math .abs(tmpArr[i]); if (val <= len && val > 0 ) { tmpArr[val - 1 ] = -Math .abs(tmpArr[val - 1 ]) } } let result = len + 1 ; for (let i = 0 ; i < len; i++) { const val = tmpArr[i]; if (val > 0 || val === null ) { result = i + 1 ; return result; } } return result; };
总结
如果正常情况下需要O(n)空间,但是要求O(1)空间,往往是需要在当前数组
上操作。
哈希表除了对象
以外,Set数据结构
也许是一个更好的选择
对象扁平化 面试遇到的题目。leetcode暂时未找到。网上搜,有个词叫,对象扁平化。这个比对象扁平化多了个对象、数组扁平化
如下,把input转换未output的形式
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 var input = { a: { a: 'a' , b: [ 0 , { a: true , b: 5 } ] }, b: [ { a: 'a' }, true ] } var output = { 'a.a' : 'a' , 'a.b[0]' : 0 , 'a.b[1].a' : true , 'a.b[1].b' : 5 , 'b[0].a' : 'a' , 'b[1]' : true }
遇到这个问题,尝试了很多次,都不知道如何做。后来朋友实现后,发现是自己根本没有放开思维。
看代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 function faltObject (input ) { const result = {}; handleObject(input, result, '' ); return result; } function handleValue (input, res, preKey ) { if (Array .isArray(input)) { handleArray(input, res, preKey) } else if (typeof input === 'object' ) { handleObject(input, res, preKey) } else { res[preKey] = input; } } function handleObject (input, res, preKey ) { const entries = Object .entries(input); for (let [key, val] of entries) { const newKey = preKey ? `${preKey} .${key} ` : key; handleValue(val, res, newKey); } } function handleArray (input, res, preKey ) { for (let i = 0 ; i < input.length; i++) { const val = input[i]; const newKey = preKey ? `${preKey} [${i} ]` : `[${i} ]` handleValue(val, res, newKey) } } console .log(faltObject(input));
自己实现时,脑子想的总是,一个方法实现,一个方法,统一输入、统一输出。最终方法里到处做判断。最终逻辑过于复杂,没有实现成功。
而正确答案,从头到尾操作的只是一个全局的对象result,只是递归的堆叠key,直到递归到非对象和数组时,给全局result对象赋值即可。这么一想就简单很多。
总结
写算法就不用要求写pure function。可以的话用全局变量可以简化一些逻辑。
for(let [key, value] of Object.entries())
是个更好的遍历对象的方法,可以替代Object.keys().forEach()
不用考虑得太复杂,一开始就封装了个isObject。而实际情况,直接typeof xx === 'object'
就差不多了。
寻找两个字符串中重复的部分 手写koa 这是面头条遇到的问题。当场解答出来了,面试官没说什么问题。但是也不确定是不是没毛病。
难度适中
题目:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 const app = new App();app.use(async (next) => { try { console .log(1 ); await next(); } catch (error) { console .log('catch' ) } console .log(4 ); }); app.use(async (next) => { console .log(2 ); await next(); console .log(3 ); }); app.use(async (next) => { throw new Error ('abc' ) });
期望输出是
我写出来的是:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class App { constructor ( ) { this .middleWare = []; this .index = 0 ; } next = () => { const cur = this .middleWare[this .index]; if (cur) { this .index++; return cur(); } } use (cb ) { if (typeof cb === 'function' ) { const bindCb = cb.bind(null , this .next); this .middleWare.push(bindCb); } } async trigger ( ) { this .index = 0 ; await this .next(); } }
总结 写的有点乱。但不是不能用。。。
最大子序和 leetcode上看到的题目。最大子序和
官方标签是动态规划
1 给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
1 2 输入: [-2,1,-3,4,-1,2,1,-5,4] 输出:6
从头开始,往后遍历。
已经遍历过的
结果
[-2 ]
-2
[-2, 1 ]
1
[-2, 1 , -3]
1
[-2, 1, -3, 4 ]
4
[-2, 1, -3, 4 , -1]
4
[-2, 1, -3, 4, -1, 2 ]
5
[-2, 1, -3, 4, -1, 2, 1 ]
6
[-2, 1, -3, 4, -1, 2, 1 , -5]
6
[-2, 1, -3, 4, -1, 2, 1 , -5, 4]
6
这题真的是想半天都不知道解不了。想了半天,写的递归动态规划,结果超时,一直想不通终极的动态规划。然而评论中给的终极解决方案超级的简单:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 var maxSubArray = function (nums ) { let sum = nums[0 ]; let result = 0 ; for (let i = 0 ; i < nums.length; i++) { const num = nums[i]; if (sum > 0 ) { sum += num; } else { sum = num; } result = Math .max(result, sum); } return result; };
从头往后累加(sum),如果总值sum小于0。则用当前指针指向的值,因为如果sum小于0,则只会使得总值变小。
而我只想到的是num为负值会影响总值的大小。。。当局者很迷啊。。
总结 总的来说还是,无法想到终极动态规划思维的转换。。。。多加练习。。。
如果有 if (result > sum) result = sum;
类似的写法是,可以用更精简的 result = Math.max(result, sum)代替
手写节流,防抖 遇到好两三次,状态不好时,也写不出来。。
其实很简单,本质上,是闭包了一个计时器
!!!!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 function throttle (fn, timeout, immediately ) { let pedding = false ; let first = !immediately; return function (...args ) { if (!pedding) { if (!first) { fn.call(this , ...args); } first = false ; pedding = true ; setTimeout (() => { pedding = false ; }, timeout); } }; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 /** * 防抖 debounce * @param {*} fn 回调函数 * @param {*} timeout 延迟时间 * @param {*} immediately 第一次是否触发 * @returns */ function debounce(fn, timeout, immediately) { let timer = null; let first = immediately; return function (...args) { clearTimeout(timer); if (first) { fn(this, ...args); first = false; } timer = setTimeout(() => { fn(this, ...args); first = true; }, timeout); }; }
by the way:
节流(throttle)是,节省,触发的意思(自己猜的)。所以一般用在滚动事件这种频繁触发,仅让其一段时间内触发的方法
防抖(debouce)是,防止抖动。一般就是搜索框,停止一段时间再触发的方法。
省的老是记不住