面试题小记

遇到的算法题,不知道他们是什么心态。

JS面试算法!!!!!!!!!!!!!!!!!!!!!!!

题目

我妹妹放学回家做了这样一个课后作业:给一张方格纸,把它剪成一片一片的,然后组装它们, 使其形成的边为一个数字递增的序列。开始的时候很有趣,但是慢慢地,我已经厌倦了看到那堆被撕破的纸。所以我决定编写一个可以帮助解决问题同时也可以”保护树木节约资源”的程序。

任务

给定一个正整数n,返回一个严格递增的序列(取决于语言版本的列表/数组/字符串)数字,使得平方和等于n²。

如果有多个结果满足,返回数值最大的那个结果:

例子

1
2
3
4

`decompose(11)`必须返回[1,2,4,10]。请注意,实际上有两种分解的方法:
11² = 121 = 1 + 4 + 16 + 100 = 1² + 2² + 4² + 10²,但是不返回[2,6,9],因为9小于10。
[1,1,4,9,49]不符合依次递增的规则,因此decompose(50)不返回[1, 1,4,9,49],而是返回[1,3,5,8,49]这种递增的序列。

注意

[n]和[1,1,1,…,1]都不是有效的解决方案。如果没有解决方案,则返回nil,null,Nothing,None(取决于语言)。

函数decompose将取正整数n并返回N =n²的分解:

1
2
3
4
5
6

“x1 ... xk”

decompose 50返回“1,3,5,8,49”

decompose 4返回“Nothing”

提示

xk经常是n-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

function getContent(n) {
let con = n*n;
let oNum = [];
let arr = [];
for(let i = 1 ; i < n ; i++ ){
oNum[i] = i*i;
};

let result = [], i = 0, len = oNum.length;
for(; i< len; i++) {
let v = oNum[i], j = 0, rLen = result.length;
result.push({vl: v, ar: [v]});
if(rLen) {
for(; j< rLen; j++) {
result.push({vl: v+result[j].vl, ar: result[j].ar.concat(v)});
}
}
}
if(i === len) {
let arr = [];
let xyh= result.filter(x => x.vl == con);
let oXyh = xyh[0]?xyh[0].ar.map((x) => {
return Math.sqrt(x) //直接操作遍历并重新赋值。ES6写法。简洁多了。
}):null;
return oXyh;
}
}

getContent(9) //[2, 4, 5, 6]
坚持原创技术分享,您的支持将鼓励我继续创作!