Leetcode 78. Subsets的followup

subsets的followup
https://leetcode.com/problems/subsets/
memory不够怎么办？

请个位大佬给个思路，谢谢。

大概写了一下，代码长这样：

1. 
   
2. 
   
3. #include <iostream>
   
4. #include <vector>
   
5. #include <fstream>
   
6. #include <string>
   
7. using namespace std;
   
8. void add(string in, string out, int n)
   
9. {
   
10.     fstream infile(in, ios::in);
    
11.     fstream outfile(out, ios::out);
    
12.     string line;
    
13.     while(getline(infile, line))
    
14.         outfile<<line<<" "<<to_string(n)<<endl;
    
15.     infile.close();
    
16.     outfile.close();
    
17. }
    
18. void append(string in, string out)
    
19. {
    
20.     fstream infile(in, ios::in);
    
21.     fstream outfile(out, ios::out|ios::app);
    
22.     string line;
    
23.     while(getline(infile, line))
    
24.         outfile << line << endl;
    
25.     infile.close();
    
26.     outfile.close();
    
27. }
    
28. void subset(vector<int> nums, string filename)
    
29. {
    
30.     string tmp = "tmp.txt";
    
31.     fstream file;
    
32.     file.open(filename,ios::out);
    
33.     file<<endl;
    
34.     file.close();
    
35. 
    
36.     for(int n : nums)
    
37.     {
    
38.         add(filename, tmp, n);
    
39.         append(tmp, filename);
    
40.     }
    
41. }
    
42. int main()
    
43. {
    
44.     string filename = "subset.txt";
    
45.     subset({1,2,3,4}, filename);
    
46.     fstream res(filename, ios::in);
    
47.     string line;
    
48.     while(getline(res, line)) cout << line << endl;
    
49.     return 0;
    
50. }
    
51. 
    
52. 
    
53. 
    
54. 
    
55. 
    

复制代码

对应的输出是：
                                                                                                                                         
1                                                                                                                                       
2                                                                                                                                       
1 2                                                                                                                                    
3                                                                                                                                       
1 3                                                                                                                                    
2 3                                                                                                                                    
1 2 3                                                                                                                                   
4                                                                                                                                       
1 4                                                                                                                                    
2 4                                                                                                                                    
1 2 4                                                                                                                                   
3 4                                                                                                                                    
1 3 4                                                                                                                                   
2 3 4                                                                                                                                   
1 2 3 4                                                                                                                                 
                                                                                                                                         
                                                                                                                                         
...Program finished with exit code 0                                                                                                     
Press ENTER to exit console.

内存不够的话，就用磁盘
这是齐士巴的代码，可以把res想象成一个文件，vector<int> tmp = res[i]可以认为是从文件中读取一行数据，res.push_back(tmp)可以认为是向文件追加一行数据。

1. 
   
2. class Solution {
   
3. public:
   
4.     vector<vector<int>> subsets(vector<int>& nums) {
   
5.         vector<vector<int>> res{{}};
   
6.         for(int n : nums)
   
7.         {
   
8.             int size = res.size();
   
9.             for(int i=0; i<size; ++i)
   
10.             {
    
11.                 vector<int> tmp = res[i];
    
12.                 tmp.push_back(n);
    
13.                 res.push_back(tmp);
    
14.             }
    
15.         }
    
16.         return res;
    
17.     }
    
18. };
    

复制代码

用iteration写就行：

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null || nums.length == 0){
            return res;
        }
        
        List<Integer> sub = new ArrayList<>();
        res.add(sub);
        
        for(int i = 0; i < nums.length; i++){
            final int size = res.size();
            for(int j = 0; j < size; j++){
                List<Integer> temp = new ArrayList<>(res.get(j));
                temp.add(nums);
                res.add(temp);
            }
        }
        return res;
    }
}

andysli6590 发表于 2021-3-25 03:51
用iteration写就行：

class Solution {

这就不太懂内存不够的意思了，如果输入是1M个数字，输出是2的1M次方大小吧,也就是1EB？
不知道内存不够是不是指这个最终保存结果的内存不够？

不用临时文件的版本

1. 
   
2. 
   
3. #include <iostream>
   
4. #include <vector>
   
5. #include <fstream>
   
6. #include <string>
   
7. using namespace std;
   
8. void subset(vector<int> nums, string filename)
   
9. {
   
10.     fstream file(filename, ios::out);
    
11.     file<<endl;
    
12.     file.close();
    
13.     int count = 1;
    
14.     for(int n : nums)
    
15.     {
    
16.         fstream in(filename, ios::in);
    
17.         fstream out(filename, ios::out|ios::app);
    
18.         string line;
    
19.         for(int i=0;i<count&&getline(in, line);++i)
    
20.         {
    
21.             out<<line<<" "<<to_string(n)<<endl;
    
22.         }
    
23.         count = count << 1;
    
24.         in.close();
    
25.         out.close();
    
26.     }
    
27. }
    
28. int main()
    
29. {
    
30.     string filename = "subset.txt";
    
31.     subset({1,2,3,4}, filename);
    
32.     fstream file(filename, ios::in);
    
33.     string line;
    
34.     while(getline(file, line)) cout << line << endl;
    
35. 
    
36.     return 0;
    
37. }
    

复制代码