面试题小记

发表于 | 更新于 | 分类于 |

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

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]