1.把二元查找树转变成排序的双向链表
题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
10
/ \
6 14
/ \ / \
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16。
首先我们定义的二元查找树节点的数据结构如下：
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
思路：可以中序遍历整棵树。按照这个方式遍历树，比较小的结点先访问。如果我们每访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整当前结点的指针将其链接到链表的末尾。当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。
///////////////////////////////////////////////////////////////////////
// Covert a sub binary-arch-tree into a sorted double-linked list
// Input: pNode - the head of the sub tree
// pLastNodeInList - the tail of the double-linked list
///////////////////////////////////////////////////////////////////////
void ConvertNode(BSTreeNode* pNode, BSTreeNode*& pLastNodeInList)
{
if(pNode == NULL)
return;
BSTreeNode *pCurrent = pNode;
// Convert the left sub-tree
if (pCurrent->m_pLeft != NULL)
ConvertNode(pCurrent->m_pLeft, pLastNodeInList);
/
/ P ut the current node into the double-linked list
pCurrent->m_pLeft = pLastNodeInList;
if(pLastNodeInList != NULL)
骨头的英文pLastNodeInList->m_pRight = pCurrent;
pLastNodeInList = pCurrent;
// Convert the right sub-tree
if (pCurrent->m_pRight != NULL)
ConvertNode(pCurrent->m_pRight, pLastNodeInList);
}
///////////////////////////////////////////////////////////////////////
// Covert a binary arch tree into a sorted double-linked list
/
/ Input: pHeadOfTree - the head of tree
// Output: the head of sorted double-linked list
///////////////////////////////////////////////////////////////////////
BSTreeNode* Convert_Solution1(BSTreeNode* pHeadOfTree)
{
BSTreeNode *pLastNodeInList = NULL;
ConvertNode(pHeadOfTree, pLastNodeInList);
// Get the head of the double-linked list
BSTreeNode *pHeadOfList = pLastNodeInList;
while(pHeadOfList && pHeadOfList->m_pLeft)
pHeadOfList = pHeadOfLi s t->m_pLeft;
return pHeadO fList;
}
2.设计包含min函数的栈。
定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。
思路：因此仅仅只添加一个成员变量存放最小元素（或最小元素的位置）是不够的。我们需要一个辅助栈。每次push一个新元素的时候，同时将最小元素（或最小元素的位置。考虑到栈元素的类型可能是复杂的数据结构，用最小元素的位置将能减少空间消耗）push到辅助栈中；每次pop一个元素出栈的时候，同时pop辅助栈。
参考代码：
#include <deque>
#include <asrt.h>
template<typename T> class CStackWithMin
{
public:
CStackWithMin(void) {}
virtual ~CStackWithMin(void) {}
T&top(void);
const T& top(void) const;
void push(const T& value);
void pop(void);
const T& min(void) const;
private:
python是什么意思deque<T> m_data; // the elements of stack
eleventhdeque<size_t> m_minIndex; // the indices of minimum elements
大学英语六级词汇};
// get the last element of mutable stack
template <typename T> T& CStackWithMin<T>::top()
{
return m_data.back();
}
// get the last element of non-mutable stack
template<typename T> const T& CStackWithMin<T>::top() const
{
return m_data.back();
}
// inrt an elment at the end of stack
template<typename T> void CStackWithMin<T>::push(const T& value) {
厉兵秣马什么意思
// append the data into the end of m_data
m_data.push_back(value);
// t the index of minimum elment in m_data at the end of m_minIndex if(m_minIndex.size() == 0)
m_minIndex.push_back(0);
el
不离不弃的英文{
if(value < m_data[m_minIndex.back()])
m_minIndex.push_back(m_data.si z e() - 1);
el
脆生生的什么m_minIndex.push_back(m_minIndex.back());
}
}
// erea the element at the end of stack
template <typename T> void CStackWithMin<T>::pop()
{
// pop m_data
m_data.pop_back();
// pop m_minIndex
m_minIndex.pop_back();
}
lfishness
// get the minimum element of stack
malfoy
template <typename T> const T& CStackWithMin<T>::min() const
{
asrt(m_data.si z e() > 0);
asrt(m_minIndex.size() > 0);
return m_data[m_minIndex.back()];
}
3.求子数组的最大和
题目：
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。
因为时间复杂度为O(n), 以为着我们只能有for循环，不能有嵌套for循环；===》我们只能从语义上去分析这个题目的破绽。可以把一个规模为N的问题转化为规模为N-1的问题。所以这个从A[0]到A[n-1]的最大和子数组问题分解成：
1. 所求子数组中包含A[0]。如果不包含A[1]，则A[0]自己满足条件，此时Max（A[0]……A[n-1]）=A[0]。如果包含A[1]，则Max（A[0]……A[n-1]）=A[0]+Max（A[1]……A[n-1]）。
2. 所求子数组中不包含A[0]。Max（A[0]……A[n-1]）=Max（A[1]……A[n-1]）。
最终结果取以上三者的最大值即可，即Max（A[0]……A[n-1]）=max（ A[0], A[0]+Max（A[1]……A[n-1]）, Max
（A[1]……A[n-1]））。
所以这就好像踢皮球，最终把球踢给了A[n-2]和A[n-1]
如果只有这两个数： max(A[n-2],A[n-1])=max(A[n-2] , A[n-2]+A[n-1])
如果只有三个数：max(A[n-3],A[n-2],A[n-1]) = max(A[n-3],A[n-3]+max(A[n-2],A[n-1]),max(A[n-2],A[n-1]));
.....
Max（A[0]……A[n-1]）=max（ A[0], A[0]+Max（A[1]……A[n-1]）, Max（A[1]……A[n-1]））。
public void getMax(int[] arr){
int max=0;
int temp =0;
for(int i=arr.length;i-2>=0;i--){
if(i=arr.length-1){
max = arr[i-2]>arr[i-2]+arr[i-1]?arr[i-2]:arr[i-2]+arr[i-1];
}el {
temp = arr[i-2]>arr[i-2]+max?arr[i-2]:arr[i-2]+max;
max = temp>max?temp:max;
}
}
}
//方法2
设置两个整数变量：cur和sum，从给定数组中依次取出所有元素，加到cur 上去，当cur<0 时候重置cur。sum记录cur 出现过的最大值：
var cur = array[0];
var sum = cur;
for (int i = 1; i < array.Length; i++)
{
indivicur = cur < 0 ?array[ i ] : cur + array[ i ];
if (sum < cur) sum = cur;
