工商银行科技菁英笔试：完全平方数问题和共线点问题

第二题：完全平方数

最近刷leetcode,做到了279，然后就想到了笔试题，然后就想分享一下思路，因为没有学过算法，所以可能解法是不对的，希望有同学可以帮忙给出更好的解法。

这道题目要求给出可以组成自然数n的完全平方数序列，且序列长度最小，如果不存在这样的序列，那么就输出NA。

考虑到会有输出NA的情况，所以我认为这道题中要求完全平方数序列是不重复的，比如输入8，输出的不应该是4，4，而应该是NA。

首先要注意，这个不能用贪心做，因为这题的局部最优是导不出全局最优的，比如n=41,如果用贪心，会得到1,4,36的分解，但真正的答案应该是16，25。

如果是允许重复的，那么这道题目比较直观，可以用动态规划求解，如果设F(n)是表出n的最短完全平方数序列的话（认为没有办法表出的n的F(n)的长度为无穷），那么F(n)=concat(F(n-j*j),(argmin_{j=1,...,sqrt(n)}#concat(j*j,F(n-j*j)))^2),从F(0）=[]一直开始递推到F(n)，时间复杂度是O(n^{3/2})。

但这边不允许重复，如果仍然用原来的F(n)的定义的话，就不能用动态规划了，因为F(n)会受到后面的状态的影响（如果后面的决策中选用了j*j的话,F(n)中就不能再包含j*j了），不符合动态规划无后效性的要求。

所以考虑采用回溯法，用一个数组used来标注各元素是否已经被使用，一旦被使用，在求解子问题的时候就不能再用这个元素了，代码如下：

但是这个方***有重复子问题，虽然通过bound的设定尽量减少了重复子问题，但还是不能完全避免。这种方法对于超过2000的数就特别慢了。所以参考背包问题的解法，可以重新定义问题F(n)，通过引入一个新变量I,我们定义F(n,i)为用基<=i的不重复的完全平方数组成n的长度最短的序列，所以F(n,i)=min(concat(F(n-i*i,i-1),i*i),F(n,i-1))，因为i最大为sqrt(n),因此这种算法的时间复杂度也是O(n^{3/2})。实现代码晚上再写，现在先去笔个试先，妈的，垂死挣扎，明知没hc，还要去，我是不是傻。

补充动态规划的代码，实现的时候只保存F(0,1,...,n,i-1)(存在prevcol向量中），并在此基础上计算F(0,1，...,n,i)（curcol)，以减少空间复杂度。同时，注意到如果n<I*I,那么F(n,i)=F(n,i-1),如果n>I(i+1)(2i+^)(根据完全平方和公式），那么不存在一串小于等于I*I的完全平方数，加起来的和是n,此时F(n,i)=F(n,i-1)仍然成立（因为两个都是序列不存在），所以在计算F（0,1,...,n,i)时，只要计算在i*i到i*(i+1)*(2i+1)的F即可，其余的直接复制F（0,1,...,n,i-1)。

用了动态规划之后，的确时间复杂度大大下降了，动态规划真厉害！

10月26日更新BFS解法。

===========================================================================================================

经过牛友提醒，去学习了BFS方法，发现这种方法更加直观，而且更快。

思想就是建一个队列remainAndsteps存各步后可能的中间状态（1步以后的中间状态，2步以后的中间状态，。。。），如果把所有可能的中间状态都遍历完了，还是没有一个中间状态正好是完全平方数，那就说明无法拆分。

同时，为了让各完全平方数不重复，仍然采用了bound的设定，即在对中间状态进行进一步拆分时，只准使用比之前用过的数都小的数。

代码如下：

第三题：

工行的第三题是求最多的共线点数，好像在leetcode上也是有原题的。

今天看到另一个牛友po的第三题求共线点的代码，发现原来不可以直接用double形式的斜率是否相等来判断共线（因为可能会因为浮点数精度问题（相对误差eps)，对斜率是否相等产生误判),所以一时冲动，又写了这一题。

思路很简单，就是遍历每个点，然后再遍历其他点，看其他点中和这个点以不同斜率共线的点分别有几个，如果发现共线的点大于历史最大共线点数了，就更新历史最大共线点数。因为对于共线的点，以线上任何一个点作为起点来计算这条线上的点数，都可以得到正确的共线点数，因此在第二个遍历中，不需要从头遍历点，只要遍历比当前点index更大的点就可以了，虽然这样会导致得到的与当前点以不同斜率共线的点的个数不对，但却不会影响最终结果的正确性（因为正确的线上点的个数已经在前面遍历到线上index最小的点的时候计算过了）。

对于斜率，应该将斜率记成字符串a/b的形式，a,b互素，因此可以先用辗转相除法求出分子分母的最大公约数，然后分子分母除以最大公约数得到a,b。

另外，考虑到会有垂直的点，这个时候无法计算斜率，因此用verticalnum来储存和当前点垂直的点的个数。

同时，考虑到会有重合的点，这些点可以被记作以任意斜率与当前点共线的点，因此在一开始记录以各斜率共线的点数（以及与当前点垂直的点数）时，将这部分点排除在外，单独设立变量redundantpoint记录重复点的数目，最后只要在最大共线点数的基础上加上这部分点的个数，就是真正的与当前点共线的最多点数了。

另外，还用了JAVA正则表达式的包regex来解析字符串。

最后，代码如下：