美文网首页
254. Factor Combinations (M)

254. Factor Combinations (M)

作者: Ysgc | 来源:发表于2021-01-29 10:00 被阅读0次

    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.
    Example 1:

    Input: 1
    Output: []
    Example 2:

    Input: 37
    Output:[]
    Example 3:

    Input: 12
    Output:
    [
    [2, 6],
    [2, 2, 3],
    [3, 4]
    ]
    Example 4:

    Input: 32
    Output:
    [
    [2, 16],
    [2, 2, 8],
    [2, 2, 2, 4],
    [2, 2, 2, 2, 2],
    [2, 4, 4],
    [4, 8]
    ]


    我的答案:
    本以为很简单的一道题,没想到竟然有这么两个巨坑,不亏是M

    • 坑1:for循环里面的结尾判断是<还是<=
      • 我一开始想当然觉得是<,因为从2开始,那么不可能搜索到n/2了,结果就被4打脸了,所以必须是<=,但这样就造成后面很多问题了
    • 坑2:如何去重?
      • 无脑筛选是会重复的,所以必须有个start的数字,for循环里面每个i,都不可能再新加一个<i的元素
      • 所以要screen out掉2,但是2<=2<=2,所以得在for里面的if也判断一次,必须让n/i这个可能新加入的元素也要>=i
    class Solution {
    public:
        vector<vector<int>> getFactors(int n, int start=2) {
            vector<vector<int>> ans;
            
            for (int i=start; i<=n/start; ++i) {
                // cout << n << " " << i << " " << n%i << endl;
                if (n%i == 0 and n/i>=i) {
                    ans.push_back({n/i, i});
                    for (auto& sub_factor:getFactors(n/i, i)) {
                        sub_factor.push_back(i);
                        ans.push_back(sub_factor);
                    }
                }
            }
            
            return ans;
        }
    };
    

    Runtime: 92 ms, faster than 39.83% of C++ online submissions for Factor Combinations.
    Memory Usage: 7.4 MB, less than 17.80% of C++ online submissions for Factor Combinations.

    稍微优化了一下代码,用一个reference叫temp的vector<int>表示已经搜索过的

    class Solution {
    private:
        vector<vector<int>> ans;
        
    public:
        vector<vector<int>> getFactors(int n) {
            vector<int> temp;
            helper(n, temp, 2);
            
            return ans;
        }
        
        void helper(int n, vector<int>& temp, int start) {
            for (int i=start; i<=n/start; ++i) {
                if (n%i == 0 and n/i >= i) {
                    temp.insert(temp.end(), {i,n/i});
                    ans.push_back(temp);
                    temp.pop_back();
                    
                    helper(n/i, temp, i);
                    temp.pop_back();
                }
            }
        }
    };
    

    Runtime: 60 ms, faster than 44.49% of C++ online submissions for Factor Combinations.
    Memory Usage: 7 MB, less than 76.27% of C++ online submissions for Factor Combinations.


    如何成为0ms?

    • 把i<=n/i放到for循环的结束判断里
    class Solution {
    private:
        vector<vector<int>> ans;
        
    public:
        vector<vector<int>> getFactors(int n) {
            vector<int> temp;
            helper(n, temp, 2);
            
            return ans;
        }
        
        void helper(int n, vector<int>& temp, int start) {
            for (int i=start; i<=min(n/start,n/i); ++i) {
                if (n%i == 0) {
                    temp.insert(temp.end(), {i,n/i});
                    ans.push_back(temp);
                    temp.pop_back();
                    
                    helper(n/i, temp, i);
                    temp.pop_back();
                }
            }
        }
    };
    

    相关文章

      网友评论

          本文标题:254. Factor Combinations (M)

          本文链接:https://www.haomeiwen.com/subject/ppxkwktx.html