学步园

1.     int value[] = {1000,900,500,400,100,90,50,40,10,9,5,4,1};  
2.     char *roman[] = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};  
3.     char store[20] = {0};  
4.   
5.     int len = sizeof(value)/sizeof(int);  
6.     for(int i = 0;i < len;++i){  
7.         while(n >= value[i]){  
8.             n -= value[i];  
9.             strcat(store,roman[i]);  
10.         }  
11.     }  

1.     arr['I'-'A'] = 1;  
2.     arr['V'-'A'] = 5;  
3.     arr['X'-'A'] = 10;  
4.     arr['L'-'A'] = 50;  
5.     arr['C'-'A'] = 100;  
6.     arr['D'-'A'] = 500;  
7.     arr['M'-'A'] = 1000;  
8.   
9.     result = arr[str[n-1]-'A'];  
10.     for(int i = n-2;i >= 0;--i){  
11.         if(arr[str[i]-'A'] >= arr[str[i+1]-'A'])  
12.             result = result + arr[str[i]-'A'];  
13.         else  
14.             result = result - arr[str[i]-'A'];  
15.     }  

1. void DFS(int *visited,char *buf,int n)  
2. {  
3.     int i;  
4.     for(i = 0;i < n;i++){  
5.         if(visited[i] == 0)  
6.             break;  
7.     }  
8.     if(i == n){  
9.         puts(buf);  
10.         return;  
11.     }  
12.     visited[i] = 1;  
13.     buf[i] = '(';  
14.     for(int j = i+1;j < n;j+=2){  
15.         visited[j] = 1;  
16.         buf[j] = ')';  
17.         DFS(visited,buf,n);  
18.         visited[j] = 0; //清除标志  
19.         if(visited[j+1] == 1)   //已经到达边界  
20.             break;  
21.     }  
22.     visited[i] = 0;<span style="white-space:pre"> </span>//清楚标志  
23. }

1. void generate(int leftNum,int rightNum,string s,vector<string> &result)  
2.     {  
3.         if(leftNum==0&&rightNum==0)  
4.         {  
5.             result.push_back(s);  
6.         }  
7.         if(leftNum>0)  
8.         {  
9.             generate(leftNum-1,rightNum,s+'(',result);  
10.         }  
11.         if(rightNum>0&&leftNum<rightNum)  
12.         {  
13.             generate(leftNum,rightNum-1,s+')',result);  
14.         }  
15. }  

1.         stack<int> S;  
2.         S.push(-1);  
3.         for(int i = 0;i < n;i++){  
4.             if(str[i] == '('){  //为左括号，入栈  
5.                 S.push(i);  
6.             }  
7.             else{               //为右括号  
8.                 if(S.size()>1){ //当栈的元素多于一个的时候才能出栈  
9.                     S.pop();  
10.                     int temp = S.top();  
11.                     if(i-temp > result)  
12.                         result = i-temp;  
13.                 }else{          //栈元素为1个，代表有效字符出栈完毕，且更新的为')'右括号的位置！  
14.                     S.pop();  
15.                     S.push(i);  
16.                 }  
17.             }  
18.         }  

1.         int highbit = 0;  
2.         while(n--)  
3.         {  
4.             highbit = res.size();  
5.             for(int i= res.size()-1; i >= 0; i--)  
6.                 res.push_back(highbit|res[i]);  
7.         }  

1. vector<int> grayCode(int n) {  
2.         // Start typing your C/C++ solution below  
3.         // DO NOT write int main() function  
4.         vector<int> res;  
5.         int num = 1<<n;  
6.         int i = 0;  
7.         while(i<num)  
8.             res.push_back((i>>1)^(i++));  
9.         return res;  
10. } 

1. TreeNode *toBST(ListNode *&h, int low, int up)  
2. {  
3.     if (low > up) return nullptr;  
4.     int m = low + ((up-low)>>1);  
5.   
6.     TreeNode *lt = toBST(h, low, m-1);  
7.     TreeNode *r = new TreeNode(h->val);  
8.     h = h->next;  
9.     r->left = lt;  
10.     r->right = toBST(h, m+1, up);  
11.     return r;         
12. }

1. if(j == 0 || j == i) cur.push_back(1);  
2.                     else cur.push_back(ans[i - 1][j] + ans[i - 1][j - 1]);
    

1. int min = triangle[i-1][j] > triangle[i-1][j-1] ? triangle[i-1][j-1] : triangle[i-1][j];  
2.                     triangle[i][j] += min; 

1.     int findBound(int n,bool asc){  
2.         int count = 0;  
3.         while(map.find(n) != map.end()){  
4.             count++;  
5.             map.erase(n);  
6.             if(asc)  
7.                 n--;  
8.             else  
9.                 n++;  
10.         }  
11.         return count;  
12.     } 

1.         map<string,int> word_count; //记录L字符串中每一个元素出现的个数  
2.         int word_size = L[0].size();  
3.         for(int i = 0;i < l_size;i++)  
4.             ++word_count[L[i]];  
5.         map<string,int> counting;   //记录查找过程中的个数  
6.         for(int i = 0;i <= (int)S.size()-l_size*word_size;i++){  
7.             counting.clear();  
8.             int j;  
9.             for(j = 0;j < l_size;j++){  
10.                 string word = S.substr(i+j*word_size,word_size);  
11.                 if(word_count.find(word) != word_count.end()){  
12.                     ++counting[word];  
13.                     if(counting[word] > word_count[word])  
14.                         break;  
15.                 }else  
16.                     break;  
17.             }  
18.             if(j == l_size)  
19.                 res.push_back(i);  
20.         }  

先不考虑边界，就考虑一般情况：

1.S[i+1] == '0'，如果S[i]为'1'或者'2'，F[i+1] = F[i]，否则无解；

2.如果S[i]为'1'，F[i+1] = F[i] + F[i-1]（例如"xxxxxx118"，可以是"xxxxxx11" + "8"，也可以是"xxxxxx1" + "18"）；

3.如果S[i]为'2'，当S[i+1] <= '6'时，F[i+1] = F[i] + F[i-1] （最大的Z为"26"，"27""28""29"不存在），当S[i+1] > '6'时，F[i+1] = F[i] （例如"xxxxxx28"，只能是"xxxxxx2" + "8"）。

   great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]