- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我要解决的问题:
给定一个 int n
,将此 int
的最小“因式分解”返回为所有正方形的数字。
我们在这里定义因式分解不是通常的方式:k
到 m
数字(m1, m2, m3...
)的因式分解将是这样:m1 + m2 + m3 + ... = k
。
例如:令n = 12
。最佳解决方案是:[4,4,4]
因为 4 是 2 的平方并且 4 + 4 + 4 = 12
。还有 [9,1,1,1]
虽然它不是最小的,因为它是 4 个数字而不是前者的 3 个。
我试图解决这个问题:
我的想法是给定数字n
,我们将执行以下算法:
首先,我们将找到最接近 n
的平方数(例如,如果 n = 82
,我们将找到 81。
然后我们将递归地计算我们得到的数字减去最接近它的平方。
这是一个流程示例:假设 n = 12
并且我们的函数是 f
,我们计算 f(3)
UNION {9}
然后 f(12-4)
UNION {4}
然后 f(12-2)
UNION { 2}
。从每一个中我们得到一个方形组合列表,我们从中获取最小列表。我们将它们保存在 HashMap 中以避免重复(动态编程风格)。
Java 中的代码尝试(不完整):
public List<Integer> getShortestSquareList(int n){
HashMap<Integer,List<Integer>> map = new HashMap<Integer,List<Integer>();
map.put(1, 1);
List<Integer> squareList = getSquareList(n);
return internalGetShortestSquareList(n, map, squareList);
}
List<Integer> getSquareList(int n){
List<Integer> result=new ArrayList<Integer>();
int i = 1;
while(i*i <= n){
result.add(i*i);
i++;
}
return result;
}
public int getClosestSquare(int n,List<Integer> squareList){
// getting the closestSquareIndex
}
public List<Integer> internalGetShortestSquareList(int n, HashMap<Integer m, HashMap<Integer,List<Integer>> map, List<Integer> squareList){
if (map.contains(n)) {return map.get(n);}
int closestSqureIndex=getClosestSquare(m,squareList);
List<Integer> minSquareList;
int minSize=Integer.MAX_INT;
for(int i=closestSqureIndex; i>-1; i--) {
int square = squareList.get(closestSqureIndex);
List<Integer> tempSquares= new ArrayList<Integer>(square);
tempSquares.addAll(f(n-square, map, squareList));
if (tempSquares.size() < minSize) {
minSize = tempSize;
minSquareList = tempSquares;
}
}
map.put(n, minSquareList);
return map.get(n);
}
我的问题:
看来我的解决方案不是最优的(imo)。我认为我的解决方案的时间复杂度是 O(n)*O(Sqrt(n))
因为最大递归深度是 n
并且子节点的最大数量是平方(n)
。我的解决方案可能充满了错误——目前这对我来说无关紧要。我将不胜感激任何指导以找到更优化的解决方案(伪代码或其他)。
最佳答案
基于@trincot 的 link , 我会建议一个简单的 O(n sqrt n)
算法。这个想法是:
n
的方 block 进行穷举搜索找出是否n
是一个正方形本身,或者是任何两个或三个小于 n
的正方形之和.这可以在 sqrt(n)^3
中完成时间,即 O(n sqrt n)
.n
的“因式分解”在四个方 block 中。递归查找数字的四次分解 m
,现在分为三种情况:
m
是素数,m mod 4 = 1
.根据math ,我们知道 n
是两个正方形的乘积。简单的详尽搜索或更“数学”的方法都应该给出一个简单的答案。m
是素数,m mod 4 = 3
.这种情况仍然需要计算出细节,但可以使用 link 中描述的数学来实现。 .m
是合数。这是递归的情况。首先分解 m
在两个因素中,即整数 u
和 v
这样u*v=m
.出于性能原因,它们应该尽可能接近,但这是次要细节。然后,递归地找到 u
的 4 次因式分解和 v
.
然后,使用 the formula :
(a^2+b^2+c^2+d^2) (A^2+B^2+C^2+D^2) = (aA+bB+cC+dD)^2 + (aB-bA+cD-dC)^2 + (aC-bD-cA+dB)^2 + (aD-dA+bC-cB)^2
找到 m
的四次分解.我在这里表示 u = (a^2+b^2+c^2+d^2)
和 v = (A^2+B^2+C^2+D^2)
,因为此时已知它们的 4 分解。
关于java - 查找整数的最小 "factorization"到平方数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34634757/
我是一名优秀的程序员,十分优秀!