[NCH 1, 3]

Preview:

O(m*n):

 1 class Solution
 2 {
 3 public:
 4     int strStr(string haystack,string needle)
 5     {
 6         for(int i=0;i<=int(haystack.size()-needle.size());i++)
 7         {
 8             int j;
 9             for(j=0;j<needle.size();j++)
10             {
11                 if(haystack[i+j]!=needle[j])
12                     break;
13             }
14             if(j==needle.size())
15                 return i;
16         }
17         return -1;
18     }
19 };

View Code

注意：size()函数返回值是size_t类型，是unsigned的，所以假如有可能为负数的话就会出问题。haystack.size()是有可能小于needle.size()的，有可能为负，因此要加个int强制转换。

或者，如果不想强制转换的话，可以把外层for循环的判断改为 i + needle.size() <= haystack.size(); 这样就不会涉及到负数了。

O(m+n):

ref: soul

2. Subsets

 1 class Solution
 2 {
 3 public:
 4     vector<vector<int>> subsets(vector<int> &nums)
 5     {
 6         sort(nums.begin(),nums.end());
 7         dfs(nums,0);
 8         return result;
 9     }
10     vector<vector<int>> result;    
11     vector<int> path;
12     void dfs(vector<int> &nums,int start)
13     {
14         result.push_back(path);    
15         for(int i=start;i<nums.size();i++)
16         {
17             path.push_back(nums[i]);
18             dfs(nums,i+1);
19             path.pop_back();
20         }
21     }
22 };

View Code

对于排序后为{0,1,4}的序列，result输出是这样的：

1: 
2: 0 , 
3: 0 , 1 , 
4: 0 , 1 , 4 , 
5: 0 , 4 , 
6: 1 , 
7: 1 , 4 , 
8: 4 ,

View Code

仔细思考一下顺序为什么是这样的。

3. Subsets II

 1 class Solution
 2 {
 3 public:
 4     vector<vector<int>> subsetsWithDup(vector<int> &nums)
 5     {
 6         sort(nums.begin(),nums.end());
 7         dfs(nums,0);
 8         return result;
 9     }
10     vector<vector<int>> result;
11     vector<int> path;
12     void dfs(vector<int> &nums, int start)
13     {
14         result.push_back(path);
15         for(int i=start;i<nums.size();i++)
16         {
17             if(i>start && nums[i]==nums[i-1]) continue;
18             path.push_back(nums[i]);
19             dfs(nums,i+1);
20             path.pop_back();
21         }
22     }
23 };

View Code

参考自己当时的分析。对于一个特定的for循环，它所循环到的每个元素都是针对当前同一个位置的不同元素的替换（它们之前的前缀都是一样的）。

注意判重是基于i>start的基础上，start之前那是前缀的事，不用管，只要保证从start之后在同一个位置不会出现重复元素就行。

比如nums是[1,2,2,2,2,2,2,3],前缀是[1,2,2],那么只要保证之后不会出现重复的[1,2,2,2]之类的就行了。

4. Permutations

 1 class Solution
 2 {
 3 public:
 4     vector<vector<int>> permute(vector<int> &nums)    
 5     {
 6         dfs(nums);
 7         return result;
 8     }
 9     vector<vector<int>> result;
10     vector<int> path;
11     void dfs(vector<int> &nums)
12     {    
13         if(path.size()==nums.size())
14         {
15             result.push_back(path);    
16             return;
17         }
18         for(int i=0;i<nums.size();i++)
19         {
20             if(find(path.begin(),path.end(),nums[i])==path.end())
21             {
22                 path.push_back(nums[i]);
23                 dfs(nums);
24                 path.pop_back();
25             }
26         }
27     }
28 };

View Code

5. Permutations II

 1 class Solution
 2 {
 3 public:
 4     vector<vector<int>> permuteUnique(vector<int> &nums)
 5     {
 6         for(auto x:nums)
 7             umap[x]++;
 8         dfs(nums);
 9         return result;
10     }
11     vector<vector<int>> result;
12     vector<int> path;
13     unordered_map<int,int> umap;
14     void dfs(vector<int> &nums)
15     {
16         if(path.size()==nums.size())
17         {
18             result.push_back(path);
19             return;
20         }
21         for(auto p=umap.begin();p!=umap.end();p++)
22         {    
23             if(p->second>0)
24             {
25                 path.push_back(p->first);
26                 umap[p->first]--;
27                 dfs(nums);
28                 umap[p->first]++;
29                 path.pop_back();
30             }
31         }
32     }
33 };

View Code

如果nums里之前是已经排好序的元素，那么如果把result输出来其实可以看到，所有的permutation是按照从小到大的顺序。

其实把元素放进unordered_map中就隐含着把元素按照相同元素在一起的顺序放了，隐含着排了个序。对排序的元素来处理可以避免重复取值。ref

[NCH03]

递归如何求复杂度?

全排列如何求时间复杂度？首先看总共有多少种情况，是n！个。然后在递归的时候递归内部的处理的复杂度是O（n）。所以全排列的时间复杂度是n * n!

二叉树如何求时间复杂度？大部分是O(n)，n为点的个数。

二叉树的空间复杂度？空间复杂度主要耗费栈空间。栈空间主要和h相关。