93. Restore IP Addresses
题目
分析：多重循环，判断小数点合适的位置
代码如下（copy网上）
class Solution {
public:
vector<string> restoreIpAddresses(string s) {
vector<string> ret;
if(s.size() > )
return ret;
for(int i = ; i < s.size(); i ++)
{// [0, i]
for(int j = i+; j < s.size(); j ++)
{// [i+1, j]
for(int k = j+; k < s.size()-; k ++)
{// [j+1, k], [k+1, s.size()-1]
string ip1 = s.substr(, i+);
string ip2 = s.substr(i+, j-i);
string ip3 = s.substr(j+, k-j);
string ip4 = s.substr(k+);
if(check(ip1) && check(ip2) && check(ip3) && check(ip4))
{
string ip = ip1 + "." + ip2 + "." + ip3 + "." + ip4;
ret.push_back(ip);
}
}
}
}
return ret;
}
bool check(string ip)
{
int value = stoi(ip);
if(ip[] == '')
{
return (ip.size() == );
}
else
{
if(value <= )
return true;
else
return false;
}
}
};
----------------------------------------------------------------------分割线--------------------------------------------------------------------------
94. Binary Tree Inorder Traversal
题目
分析：二叉树的中序遍历，题目要求不能使用递归，因此为了实现中序遍历，需要使用一个stack，只是在存储节点的 时候，中间节点利用两个NULL包裹起来存放。详细请看代码中的注释，代码如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
if(root == NULL)
return res;
stack<TreeNode*> myStack;
TreeNode *temp;
myStack.push(root);
while(!myStack.empty())
{
temp = myStack.top();
myStack.pop(); if(NULL == temp)//表示访问到中间节点了，需要读取val
{
temp = myStack.top();
myStack.pop();
res.push_back(temp->val);
temp = myStack.top();
myStack.pop();
continue;
}
//右节点push
if(temp->right != NULL)
myStack.push(temp->right); //利用两个NULL把中间节点包裹起来
myStack.push(NULL);
myStack.push(temp);
myStack.push(NULL); //左节点push
if(temp->left != NULL)
{
myStack.push(temp->left);
}
}
return res; }
};
-------------------------------------------------------------------------------分割线-------------------------------------------------------------------
95. Unique Binary Search Trees II
题目
分析：递归求解，代码如下（copy网上代码）
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<TreeNode *> generateTrees(int n) {
vector<TreeNode *> res;
if(n==)
return res;
return Helper(, n);
}
vector<TreeNode *> Helper(int begin, int end)
{
vector<TreeNode *> ret;
if(begin > end)
ret.push_back(NULL);
else if(begin == end)
{
TreeNode* node = new TreeNode(begin);
ret.push_back(node);
}
else
{
for(int i = begin; i <= end; i ++)
{//root
vector<TreeNode *> left = Helper(begin, i-);
vector<TreeNode *> right = Helper(i+, end);
for(int l = ; l < left.size(); l ++)
{
for(int r = ; r < right.size(); r ++)
{
//new tree
TreeNode* root = new TreeNode(i);
root->left = left[l];
root->right = right[r];
ret.push_back(root);
}
}
}
}
return ret;
}
};
----------------------------------------------------------------------------分割线---------------------------------------------------------------------
96. Unique Binary Search Trees
题目
分析：这题和95题是一样的，代码如下（copy网上代码）：
class Solution {
public:
int numTrees(int n) {
int f[n+];
memset (f , , sizeof(int)*(n+));
f[]=;
for(int i=; i<=n; i++)
for(int j=; j<i; j++)
f[i] += f[j] * f[i-j-];
return f[n];
}
};