FactorCombinations [source code]
public class FactorCombinations {
static
/******************************************************************************/
class Solution {
public List<List<Integer>> getFactors(int n) {
return dfs (n, 2);
}
public List<List<Integer>> dfs (int n, int prev) {
List<List<Integer>> lss = new ArrayList<> ();
for (int i = prev; i <= (int) Math.sqrt (n); i++) {
if (n % i == 0) {
List<Integer> curLs = new ArrayList<> ();
curLs.add (i);
curLs.add (n / i);
lss.add (curLs);
List<List<Integer>> downLss = dfs (n / i, i);
for (List<Integer> downLs : downLss) {
downLs.add (0, i);
lss.add (downLs);
}
}
}
return lss;
}
}
/******************************************************************************/
public static void main(String[] args) {
FactorCombinations.Solution tester = new FactorCombinations.Solution();
int[] inputs = {
1,
37,
12,
32,
};
for (int i = 0; i < inputs.length; i++) {
int n = inputs[i];
System.out.println (Printer.separator ());
List<List<Integer>> output = tester.getFactors (n);
System.out.printf ("%d -> %s\n",
n, output
);
}
}
}
题目本身是看起来比较熟悉的, 不过好像有一个去重的问题需要解决, 比如对于12的结果, 有2, 6, 但是就没有6, 2. 这个感觉只要控制循环的重点不超过平方根就行了? 尝试一下;
好像上面这个去重方案并不完整; 想到一个大概的方案, 不过不知道是否正确, 尝试一下; 另外可以看到, 这题的难点就在于怎么去重了;
第一个思路是:
class Solution {
Set<Integer> set = new HashSet<> ();
public List<List<Integer>> getFactors(int n) {
List<List<Integer>> lss = new ArrayList<> ();
for (int i = 2; i <= (int) Math.sqrt (n); i++) {
if (n % i == 0) {
List<Integer> curLs = new ArrayList<> ();
curLs.add (i);
curLs.add (n / i);
lss.add (curLs);
if (set.add (n / i)) {
List<List<Integer>> downLss = getFactors (n / i);
for (List<Integer> downLs : downLss) {
downLs.add (0, i);
lss.add (downLs);
}
}
}
}
return lss;
}
}
enforce order to remove duplicate
但是这个思路最后有问题, 对于12, 出现了重复; 我重新观察了一下给的这些例子, 最后看到了一点规律, 发现这里去重的重点, 是enforce order. 这个是很久没有用到的一个技巧, 也是忘记了; 适当的实现了这个改动之后, 直接AC了, 速度是2ms (71%).
另外这里因为最后需要用一个add at index 0的操作, 所以我以为是不是换成LinkedList可以提速, 不过最后看来好像并没有任何的改变; 之前好像看过StackOverflow上面一篇文章说过, ArrayList大部分时间的performance是足够优秀的, 这里也是看到了论据;
后来想到一个有意思的小改动:
class Solution {
int prev = 2;
public List<List<Integer>> getFactors (int n) {
List<List<Integer>> lss = new LinkedList<> ();
for (int i = prev; i <= (int) Math.sqrt (n); i++) {
if (n % i == 0) {
List<Integer> curLs = new LinkedList<> ();
curLs.add (i);
curLs.add (n / i);
lss.add (curLs);
int prevP = prev;
prev = i;
List<List<Integer>> downLss = getFactors (n / i);
prev = prevP;
for (List<Integer> downLs : downLss) {
downLs.add (0, i);
lss.add (downLs);
}
}
}
return lss;
}
}
这样就不需要helper了, 直接用一个global来记录这个prev的位置;
没有editorial;
discussion最优解:
public List<List<Integer>> getFactors(int n) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
helper(result, new ArrayList<Integer>(), n, 2);
return result;
}
public void helper(List<List<Integer>> result, List<Integer> item, int n, int start){
if (n <= 1) {
if (item.size() > 1) {
result.add(new ArrayList<Integer>(item));
}
return;
}
for (int i = start; i <= n; ++i) {
if (n % i == 0) {
item.add(i);
helper(result, item, n/i, i);
item.remove(item.size()-1);
}
}
}
这个是一个用mutation来完成的DFS, 一开始我也是想到用这样做, 毕竟这个才是最常见的DFS的写法; 不过我认为我的写法其实是更好的; 另外, 他这种写法, 你可以明显的看到, 比我的更像是backtracking, 有明显的do/undo操作;
但是他上面这个算法其实非常的慢, 下面是另外一个改进:
@060601199 said in My Recursive DFS Java Solution:
2 small changes make it much faster, please look my comments for the 2 changes in the code
public class Solution {
public List<List<Integer>> getFactors(int n) {
List<List<Integer>> results = new ArrayList<>();
if (n <=3) {
return results;
}
getFactors(n, 2, new ArrayList<Integer>(), results);
return results;
}
private void getFactors(int n, int start, List<Integer> current, List<List<Integer>> results) {
if (n == 1) {
if (current.size() > 1) {
results.add(new ArrayList<Integer>(current));
}
return;
}
for (int i = start; i <= (int) Math.sqrt(n); i++) { // ==> here, change 1
if (n % i != 0) {
continue;
}
current.add(i);
getFactors(n/i, i, current, results);
current.remove(current.size()-1);
}
int i = n; // ===> here, change 2
current.add(i);
getFactors(n/i, i, current, results);
current.remove(current.size()-1);
}
}
注意他这里这个change2其实就是我自己的那个, 比如你刚从12里面提取出来2, 要直接先把2, 6也加进去的操作; 当他change1把循环的重点缩短到平方跟之后, 那么必须要加一个change2来考虑这个整个add的操作; 他虽然调用了getFactors, 但是实际上因为第一个参数传进去的是1, 所以call进去之后, 直接就是一个add操作;
另外, 刚开始看的时候不理解为什么最后有一个current.remove(current.size()-1)操作, 这个是什么原理: 这个是因为其实这里remove的就是刚刚上面刚刚add的i: 因为所有下面的iteration也都会相应的undo自己的add, 所以这里最后等到这个getFactors返回的时候, 你手上的就是你call这个函数之前的current.
这个是一个类似的改动:
@RoyalPen said in My Recursive DFS Java Solution:
Hey friend, thanks for your inspiration. I benefit a lot from your method. I made a little change to your code and it runs so much faster(only 2 ms). Here it is.
public class Solution {
public List<List<Integer>> getFactors(int n) {
List<List<Integer>> list = new ArrayList<>();
List<Integer> element = new ArrayList<>();
helper(list,n,2,element,(int)Math.sqrt(n));
return list;
}
public void helper(List<List<Integer>> list, int n, int start, List<Integer> element,int upper)
{
if(n == 1 &&element.size() > 1)
{
list.add(new ArrayList<Integer>(element));
return;
}
for(int i = start; i <= n; i++)
{
if(i > upper)
{
i = n;
}
if(n %i == 0)
{
element.add(i);
helper(list,n/i,i,element,(int)Math.sqrt(n/i));
element.remove(element.size() - 1);
}
}
}
}
Actually, factors of an integer n (except for 1 and n) are always between 1 and sqrt(n), so you do not have to check those numbers between sqrt(n) and n. However, in your method, we need to check n, so I added a check, when i is greater than sqrt(n), i will jump directly to n. This little change improved a lot. Thank you!
这里就看出来这种mutation的做法实际上真的是有点low的;
这个是另外一个类似的解法:
public List<List<Integer>> getFactors(int n) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (n <= 3) return result;
helper(n, -1, result, new ArrayList<Integer>());
return result;
}
public void helper(int n, int lower, List<List<Integer>> result, List<Integer> cur) {
if (lower != -1) {
cur.add(n);
result.add(new ArrayList<Integer>(cur));
cur.remove(cur.size() - 1);
}
int upper = (int) Math.sqrt(n);
for (int i = Math.max(2, lower); i <= upper; ++i) {
if (n % i == 0) {
cur.add(i);
helper(n / i, i, result, cur);
cur.remove(cur.size() - 1);
}
}
}
只不过他把整个add这个操作放在了循环前面了, 所以更加好理解一些;
这个解法不错:
class Solution {
public:
void getResult(vector<vector<int>> &result,vector<int> &row,int n){
int i=row.empty()?2:row.back();
for(;i<=n/i;++i){
if(n%i==0){
row.push_back(i);
row.push_back(n/i);
result.push_back(row);
row.pop_back();
getResult(result,row,n/i);
row.pop_back();
}
}
}
vector<vector<int>> getFactors(int n) {
vector<vector<int>> result;
vector<int>row;
getResult(result,row,n);
return result;
}
};
注意看他这里没有专门去保存这个prev的值, 而是直接用accum的end来比较, 这个想法还是有点意思的;
submission基本是波动;
Problem Description
Numbers can be regarded as product of its factors. For example,
8 = 2 x 2 x 2;
= 2 x 4.
Write a function that takes an integer n and return all possible combinations of its factors.
Note:
- You may assume that n is always positive.
- Factors should be greater than 1 and less than n.
Examples:
input: 1
output:
[]
input: 37
output:
[]
input: 12
output:
[
[2, 6],
[2, 2, 3],
[3, 4]
]
input: 32
output:
[
[2, 16],
[2, 2, 8],
[2, 2, 2, 4],
[2, 2, 2, 2, 2],
[2, 4, 4],
[4, 8]
]
Difficulty:Medium
Total Accepted:34.3K
Total Submissions:78.4K
Contributor:LeetCode
Companies
uberlinkedin
Related Topics
backtracking
Similar Questions