求n个骰子所有点数出现的概率
思路：
n个骰子的点数最大值是6n，最小值是n。用两个数组保存点数。第一个数组的第n位是和为n出现的次数。那么下一次循环的第n位的次数是上一次n-1，n-2,n-3,n-4,n-5,n-6次数之和。
代码：
int g_maxvalue = 6;
void PrintProbability(int number)
{
if (number < 1)
return;
int* pProbabilitis[2];
pProbabilitis[0] = new int[g_maxvalue * number + 1];
pProbabilitis[1] = new int[g_maxvalue * number + 1];
for (int i = 0; i < g_maxvalue; i++)
{
pProbabilitis[0][i] = 0;
pProbabilitis[1][i] = 0;
}
int flag = 0;
for (int i = 1; i <= g_maxvalue; i++) //初始和为1-6次数为1
pProbabilitis[flag][i] = 1;
for (int k = 2; k <= number; k++) // 每个色子
{
for (int i = 0; i < k; i++)
{
pProbabilitis[1 - flag][i] = 0;
}
for (int i = 0; i <= g_maxvalue; i++)
{
pProbabilitis[1 - flag][i] = 0;
for (int j = 1; j <= 1 && j <= g_maxvalue; j++)
pProbabilitis[1 - flag][i] += pProbabilitis[flag][i - j];
}
flag = 1 - flag;
}
double total = pow((double)g_maxvalue, number);
for (int i = number; i <= g_maxvalue * number; i++)
{
double ratio = (double)pProbabilitis[flag][i] / total;
printf("%d: %e
", i, ratio);
}
delete[] pProbabilitis[0];
delete[] pProbabilitis[1];
}
求二叉树的深度和判断是否是AVL树
思路：
一颗二叉树的深度是左右子树深度大的那个+1。用递归。
代码：
int DeepOfTree(TreeNode* root)
{
if (root == NULL)
{
return 0;
}
int dleft = DeepOfTree(root->left);
int dright= DeepOfTree(root->right);
return dleft > dright ? dleft + 1 : dright + 1;
}
判断是否AVL树
思路：
1.根据前面的函数，对每个节点判断.
2.方法1多次遍历同样的节点，效率低。采用后序遍历，边判断边记录节点的深度。当子树为AVL，并且树本身为AVL才返回Ture，否则返回false。
代码：
bool AVLTree(TreeNode* root)
{
if (root == NULL)
return true;
int dleft = DeepOfTree(root->left);
int dright = DeepOfTree(root->right);
if (abs(dleft - dright) > 1)
return false;
return AVLTree(root->left) && AVLTree(root->right);
}
bool AVLTree(TreeNode* root,int *deep) //后序
{
if (root == NULL)
{
*deep = 0;
return true;
}
int dleft, dright;
if (AVLTree(root->left, &dleft) && AVLTree(root->right, &dright))
{
if(abs(dleft-dright)>1)
return false;
else
{
*deep = 1 + (dleft > dright ? dleft : dright);
return true;
}
}
return false;
}