面试中遇到的算法题

面试中遇到的算法题

七月 05, 2021

这里存放一些面试中遇到的有意思的面试题。因为最近两个多月没刷题,解题能力基本上又回去了。所以得记录一下,需要的时候快速找到感觉。

最长回文字符串

题目传送门

答案来源传送门

中心扩散法

第一个想到中心扩散法,具体分析见文章。

首先肯定得遍历一遍,逐一选择“中间点”,然后往左右扩散,重点是得想到扩散的两种情况

  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
/**
* @param {string} s
* @return {string}
*/
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
};

动态规划

这是自己写的递归版动态规划,应该是中间态的动态规划。实测,耗时和耗内存都比中间扩散法大不少。

思路是:

  1. 用一个二维数组dp存储状态,dp[i][j]存储s[i…j]是否是回文。

  2. s[i…j]是否是回文取决于s[i+1…j-1]是否是回文。则可以得到递推公式

    f(i, j) = f(i+1, j-1) && s[i] === s[j]

  3. 边界情况是,如果字符串长度是1时,则肯定是回文。字符串长度为2时,如果两个字符相同,则是回文

  4. 然后考虑好边界情况,整理出一个递归公式就行。

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
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function (s) {
const len = s.length;
let result = ''
let pre = 0;
let after = 0;

// 创建二维数组,用于存储。
let dp = new Array(len)
// 这里注意,不能 new Array(len).fill(new Array(len).fill(null))
// fill里加new Array, 那么填充的数组是一个数组,填充的是引用。会导致改了一个,每个都会改变
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);
};

// [i, j]
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;
}
// 大于3的情况,如果两头是回文,则递归查找
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;

}

总结

  1. 回文字符串天生就是一个可以拆分成子问题的问题,动态规划是个不二之选。寻找好递推关系还是重中之重。
  2. 中心扩散法貌似是最长回文问题的特殊方法。但其实应该也就是动态规划,的终极形态。

缺失的第一个正数

传送门

好理解的最佳解-原地哈希

这题目有两种答案:

哈希表法

时间和空间复杂度都是O(n)

把数组变成哈希表,然后从1开始递增。如果哈希表没有,就是答案。哈希表可以用对象,更佳的数据结构是Set,代码更简单(但是leetcode运行结果来看,Set更占内存、更耗时)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* @param {number[]} nums
* @return {number}
*/
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),则说明不需要占用额外空间,首先考虑的应该是,要在当前数组操作

具体看传送门。这个思路大约是:

  1. 先把负数清除,都统一转换为null排除干扰。如果此遍历过程发现没有1。则答案肯定是1.
  2. 顺序遍历,把当前遍历到的数字,把其数值的数组下标设置为负数。
    如果数值大于数组长度,则不改,否则会修改当前数组的长度。
  3. 最后从1累加遍历数组,如果是负数,则对应下标的数是存在于原数组的。如果无负数,则就是当前的值。
  4. 如果都是负数,结果是数组长度+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
/**
* @param {number[]} nums
* @return {number}
*/
var firstMissingPositive = function (nums) {
const len = nums.length;

let tmpArr = nums.slice();
// 去除负数,统一改为0
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
}
}

// 如果没有1。则结果是1
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;
// 最后走一遍,如果是负数,则原来存在于数组、非0则不存在,则是要找的结果。如果都是负数,则结果是len
for (let i = 0; i < len; i++) {
const val = tmpArr[i];
// 没被标记
if (val > 0 || val === null) {
result = i + 1;
return result;
}
}
return result;
};

总结

  1. 如果正常情况下需要O(n)空间,但是要求O(1)空间,往往是需要在当前数组上操作。
  2. 哈希表除了对象以外,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对象赋值即可。这么一想就简单很多。

总结

  1. 写算法就不用要求写pure function。可以的话用全局变量可以简化一些逻辑。
  2. for(let [key, value] of Object.entries())是个更好的遍历对象的方法,可以替代Object.keys().forEach()
  3. 不用考虑得太复杂,一开始就封装了个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
1
2
catch
4

我写出来的是:

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;
sum += num;
} else {
// 如果sum小于0,则sum+num会使得num变小,所以直接sum=num即可
sum = num;
}
result = Math.max(result, sum);
}
return result;
};

从头往后累加(sum),如果总值sum小于0。则用当前指针指向的值,因为如果sum小于0,则只会使得总值变小。

而我只想到的是num为负值会影响总值的大小。。。当局者很迷啊。。

总结

总的来说还是,无法想到终极动态规划思维的转换。。。。多加练习。。。

  1. 如果有 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
/**
* 节流 throttle
* @param {*} fn 回调函数
* @param {*} timeout 延迟时间
* @param {*} immediately 第一次是否触发
* @returns
*/
function throttle(fn, timeout, immediately) {
let pedding = false; // 闭包一个状态,存储是否可以执行
let first = !immediately; // 存储是否第一次调用的状态

return function (...args) {
// 非pending时,执行原方法就好
if (!pedding) {
if (!first) {
// 记得改变this指向为这个新的function
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)是,防止抖动。一般就是搜索框,停止一段时间再触发的方法。

省的老是记不住