前言
依旧是递归。
（马上开学了，新学期课好多，还得抽空刷题……TvT）
一、嵌套类问题
例如计算（3*（2+4*（1+1）））这种题就是嵌套类问题。观察其结构，不难发现递归会是很好的解决方法。
嵌套类问题的思路就是设置全局变量where，用来记录递归中处理过的嵌套结构，在回来时直接去嵌套的结束位置继续。
1.字符串解码
class Solution {
public:int where;string decodeString(string s) {where=0;return f(s,0);}string f(string s,int i){string cur;int cnt=0;while(i<s.length()&&s[i]!=']'){if( (s[i]>='a'&&s[i]<='z') || (s[i]>='A'&&s[i]<='Z') ){cur+=s[i++];}else if(s[i]>='0'&&s[i]<='9'){cnt=cnt*10+s[i++]-'0';}else//遇到'['{string next=f(s,i+1);for(int j=0;j<cnt;j++){cur+=next;}i=where;cnt=0;}}where=i+1;return cur;}
};在设置完全局变量where后，递归函数的主要思路就是碰到“】”就返回上一层，然后是字母就加上，是数字就计算，当遇到“【”时，就去调递归计算嵌套部分，回来后按照数字大小加字符串，最后利用where更新i，然后让cnt归零。注意，在即将返回时要更新where。
2.原子的数量
class Solution {
public:int where;string countOfAtoms(string formula) {where=0;map<string,int>mp=f(formula,0);string ans;for(map<string,int>::iterator iter=mp.begin();iter!=mp.end();iter++){ans+=iter->first;int cnt=iter->second;if(cnt>1){ans+=to_string(iter->second);}}return ans;}map<string,int> f(string s,int i){map<string,int>ans;//总表string name;//历史收集到的名字map<string,int>pre;//历史的表int cnt=0;while(i<s.length()&&s[i]!=')'){if( (s[i]>='A'&&s[i]<='Z') ||s[i]=='('){fill(ans,name,pre,cnt);//清空历史name.clear();pre.clear();cnt=0;//填新表if(s[i]>='A'&&s[i]<='Z'){name+=s[i++];}else{pre=f(s,i+1);i=where;}}else if(s[i]>='a'&&s[i]<='z'){name+=s[i++];}else{cnt=cnt*10+s[i++]-'0';}}fill(ans,name,pre,cnt);where=i+1;return ans;}void fill(map<string,int>&ans,string name,map<string,int>&pre,int cnt){if(name.length()>0||!pre.empty()){cnt=cnt==0?1:cnt;if(name.length()>0){ans[name]+=cnt;}else{for(map<string,int>::iterator iter=pre.begin();iter!=pre.end();iter++){ans[iter->first]+=iter->second*cnt;}}}}
};这个题的要求按字典序排列，所以要准备一张map记字符串对应的出现次数，所以递归函数的返回值要变成map，就是这一点比较反常识。
还是遇到“）”就返回，否则是大写字母或“（”，说明到了新的该收集的地方，需要先结算，往总表里填入之前收集到的表或字符串，都清空后，若是大写字母，就填字符串，否则，说明是“（”，则需要调递归收集一个pre表，最后更新i。若是小写字母，只需要填在name后即可。若是数字，计算出来即可。最后在退出时需要再汇总一次并更新where。
再就是汇总填表函数，若name有东西或者pre表里有东西才去汇总。因为若只有一个字符或表，cnt会为0，所以要设成1。之后若name有就填name，否则说明pre有东西，那就填pre。
这个题虽然看起来跟上个题差不多，但具体写起来时的情况讨论和代码结构还是挺费劲的。
二、N 皇后 II 问题
重点是位运算版本，太妙了~
1.普通解
class Solution {
public://对角线判断：|当前行-之前行|=|当前列-之前列|int totalNQueens(int n) {vector<int>path(n,0);//下标->行 数值->列 =>表示有无皇后return f(0,path,n);}int f(int i,vector<int>&path,int n){if(i==n)//能来到说明找到一种{return 1;}int ans=0;for(int j=0;j<n;j++)//遍历当前行的每一列{if(check(path,i,j))//可以放就放{path[i]=j;ans+=f(i+1,path,n);//不需要清除，之后遍历会覆盖}}return ans;}bool check(vector<int>&path,int i,int j){for(int k=0;k<i;k++)//遍历之前每一行{if(j==path[k]||abs(i-k)==abs(j-path[k])){ //判断列 //判断对角线return false;}}return true;}
};首先一个结论，对角线上的判断是：|当前行-之前行|=|当前列-之前列|
用path数组记录列信息，然后从上到下遍历每行。若来到第n行，说明找到了一种。否则遍历当前行的每一列，每次check一下能不能放，能放就放，然后去下一行调递归即可。
接着是check函数，就是遍历之前行，若列上有了或者对角线有了就返回false，否则返回true。
2.位运算解
class Solution {
public:int totalNQueens(int n) {int col=0;int left=0;int right=0;int limit=(1<<n)-1;return f(limit,col,left,right);}int f(int limit,int col,int left,int right){if(col==limit){return 1;}int ban=col|left|right;//不能放的位置int candidate=limit&(~ban);//改成1位置可放，并消去高位的1int place=0;int ans=0;while(candidate!=0){place=candidate&(-candidate);//取最右侧1candidate^=place;//消最右侧1ans+=f(limit,col|place,(left|place)>>1,(right|place)<<1);}return ans;}
};位运算的主要思路就是用位信息来记录当前位置是否可放。
首先用col来记录列信息，之后观察对角线的特点，可以发现，每次去到下一行，左对角线就是每次放置的位置右移，右对角线就是左移。注意这里最右侧数位对应的是最左边的格子。之后再设置limit表示全填满的情况，即（1<<n）-1。
递归函数若col等于limit，即每一列都填满，就说明找到一种。之后col，left和right全或起来就是不能填的位置，再取反与上limit就是能放的位置。然后遍历每个能放的位置，每次取出candidate最右侧1，去下一行调递归即可。
总结
要赶紧努力把递归练好啊！