问题1:跳台阶问题。具体描述,一个台阶总共有n级,如果一次可以跳1级,也可以跳2级。求总共有多少总跳法,并分析算法的时间杂度。
//相当于从下往上跳,最后剩一个(仅一种跳法)或两个(有两种跳法)+++
//函数功能 : 跳台阶问题
//函数参数 : n为台阶个数
//返回值 : 总的跳法
unsigned JumpSteps_Solution1(unsigned n)
{
if(n <= 2)
return n;
else
return JumpSteps_Solution1(n - 1) + JumpSteps_Solution1(n - 2);
}
问题2:二元树的深度。输入一棵二元树的根结点,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。
树的深度 = 1 + max{ 根节点左子树深度,根结点右子树深度}
struct SBinaryTreeNode // a node of the binary tree
{
int m_nValue; // value of node
SBinaryTreeNode *m_pLeft; // left child of node
SBinaryTreeNode *m_pRight; // right child of node
};
//函数功能 : 二元树的深度
//函数参数 : pNode指向树的结点
//返回值 : 深度
int BinaryTreeDepth(BinaryTreeNode *pNode)
{
if(pNode == NULL)
return 0;
else
{
int leftDepth = BinaryTreeDepth(pNode->m_pLeft);
int rightDepth = BinaryTreeDepth(pNode->m_pRight);
return (leftDepth > rightDepth) ? leftDepth+1 : rightDepth+1;
}
}
问题3:设计包含min函数的栈。定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。
思路:利用双栈来做。一个栈用于正常的入栈退栈,称为Stack1,另外一个用于保存栈的最小元素,称为Stack2。Stack2入栈时,将入栈元素与Stack2的栈顶元素比较,如果小于栈顶元素,则两个栈同时执行入栈操作。Stack1退栈时,如果退栈元素与Stack2的栈顶元素相等,则两个栈同时执行出栈操作。
template<class T>
class MinStack
{
public:
MinStack();
~MinStack();
bool Empty() const; //判断栈是否为空
void Push(T value); //压栈
void Pop(); //退栈
T& Top();
const T& Top() const;
const T& Min() const;
private:
stack<T> m_comStack; //正常栈
stack<T> m_minStack; //最小栈
};
template<class T>
MinStack<T>::MinStack()
{
}
template<class T>
MinStack<T>::~MinStack()
{
}
template<class T>
bool MinStack<T>::Empty() const
{
return m_comStack.empty();
}
template<class T>
void MinStack<T>::Push(T value)
{
if(m_minStack.empty() || value <= m_minStack.top())
m_minStack.push(value);
m_comStack.push(value);
}
template<class T>
void MinStack<T>::Pop()
{
if(m_minStack.top() == m_comStack.top())
m_minStack.pop();
m_comStack.pop();
}
template<class T>
const T& MinStack<T>::Min() const
{
return m_minStack.top();
}
template<class T>
T& MinStack<T>::Top()
{
m_comStack.top();
}
template<class T>
const T& MinStack<T>::Top() const
{
m_comStack.top();
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)