从1到n的二叉搜索树及回溯类之全排列、电话号码

总结

从1到n的二叉搜索树其实考的是数学，推导出卡特兰数从而解决；全排列和电话号码则是典型的回溯类题目，解法套路就是决策、再决策、撤销恢复状态

题目I（DP动态规划）

题解

	int numTrees(int n) {vector<int> G(n+1,0);G[0]=1;// 第一重循环用来给G赋值，表示i个节点组成的二叉搜索树个数// 因为是从1到n，所以在计算G[n]时是肯定知道G[n-1]及之前的// 从而可以不使用递归来实现for(int i=1;i<=n;i++){//第二重循环表示以j为根节点组成的二叉搜索树个数for(int j=1;j<=i;j++){G[i]+=G[j-1]*G[i-j];}}return G[n];}

感悟

题目II（回溯）

题解

	vector<vector<int>> permute(vector<int>& nums) {map<int,bool> m;for(int i=0;i<nums.size();i++){m[nums[i]]=false;}vector<vector<int>> result;vector<int> t;backtrack(nums,result,m,t);return result;}void backtrack(vector<int>& nums,vector<vector<int>>& result,map<int,bool>& m,vector<int>& t){if(t.size()==nums.size()){vector<int> tem;for(int i=0;i<nums.size();i++){tem.push_back(t[i]);}result.push_back(tem);return ;}for(int i=0;i<nums.size();i++){if(m[nums[i]]==true){continue;}t.push_back(nums[i]);m[nums[i]]=true;backtrack(nums,result,m,t);t.pop_back();m[nums[i]]=false;}}

感悟

就是回溯法，因为传递的参数用的都是引用，所以需要考虑恢复状态！！！

题目III

题解

	vector<string> letterCombinations(string digits) {vector<string> result;string t="";int n=0;backtrack(digits,t,result,n);return result;}void backtrack(string& digits,string& t,vector<string>& result,int& n){if(digits.length()==t.length()){string x=t;if(digits!=""){result.push_back(x);}else{}return ;}vector<char> vc;if(digits[n]=='2'){vc.push_back('a');vc.push_back('b');vc.push_back('c');}else if(digits[n]=='3'){vc.push_back('d');vc.push_back('e');vc.push_back('f');}else if(digits[n]=='4'){vc.push_back('g');vc.push_back('h');vc.push_back('i');}else if(digits[n]=='5'){vc.push_back('j');vc.push_back('k');vc.push_back('l');}else if(digits[n]=='6'){vc.push_back('m');vc.push_back('n');vc.push_back('o');}else if(digits[n]=='7'){vc.push_back('p');vc.push_back('q');vc.push_back('r');vc.push_back('s');}else if(digits[n]=='8'){vc.push_back('t');vc.push_back('u');vc.push_back('v');}else{vc.push_back('w');vc.push_back('x');vc.push_back('y');vc.push_back('z');}for(int i=0;i<vc.size();i++){t+=vc[i];n++;backtrack(digits,t,result,n);n--;t=t.substr(0,t.length()-1);}}

感悟

这个题目也是回溯类题目，似乎回溯类都是三步：决策、再决策、撤销；不过这个和上一道题目还是有一些不一样的，上一道题目就是在给定的nums数组里面选数字，且不能重复，所以在遍历选择列表的时候得判断选择项是否已经选过了；而这道题不一样，“23”的顺序是固定的，一定是先选2再选3，只是每一个数字里的字符每次可以任意选择，所以选择列表就是每个数字代表的字符，并且不用判断是否已经选过，然后通过传递参数n来进入下一步决策