1.把二元查找树转变成排序的双向链表
题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
10
/ \
6 14
/ \ / \
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16。
#include <stdio.h>
#include <iostream.h>
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
typedef BSTreeNode DoubleList;
DoubleList * pHead;
DoubleList * pListIndex;
void convertToDoubleList(BSTreeNode * pCurrent);
// 创建二元查找树
void addBSTreeNode(BSTreeNode * & pCurrent, int value)
{
if (NULL == pCurrent)
{
BSTreeNode * pBSTree = new BSTreeNode();
pBSTree->m_pLeft = NULL;
pBSTree->m_pRight = NULL;
pBSTree->m_nValue = value;
pCurrent = pBSTree;
}
else
{
if ((pCurrent->m_nValue) > value)
{
addBSTreeNode(pCurrent->m_pLeft, value);
}
else if ((pCurrent->m_nValue) < value)
{
addBSTreeNode(pCurrent->m_pRight, value);
}
else
{
//cout<<"重复加入节点"<<endl;
}
}
}
// 遍历二元查找树 中序
void ergodicBSTree(BSTreeNode * pCurrent)
{
if (NULL == pCurrent)
{
return;
}
if (NULL != pCurrent->m_pLeft)
{
ergodicBSTree(pCurrent->m_pLeft);
}
// 节点接到链表尾部
convertToDoubleList(pCurrent);
// 右子树为空
if (NULL != pCurrent->m_pRight)
{
ergodicBSTree(pCurrent->m_pRight);
}
}
// 二叉树转换成list
void convertToDoubleList(BSTreeNode * pCurrent)
{
pCurrent->m_pLeft = pListIndex;
if (NULL != pListIndex)
{
pListIndex->m_pRight = pCurrent;
}
else
{
pHead = pCurrent;
}
pListIndex = pCurrent;
cout<<pCurrent->m_nValue<<endl;
}
int main()
{
BSTreeNode * pRoot = NULL;
pListIndex = NULL;
pHead = NULL;
addBSTreeNode(pRoot, 10);
addBSTreeNode(pRoot, 4);
addBSTreeNode(pRoot, 6);
addBSTreeNode(pRoot, 8);
addBSTreeNode(pRoot, 12);
addBSTreeNode(pRoot, 14);
addBSTreeNode(pRoot, 15);
addBSTreeNode(pRoot, 16);
ergodicBSTree(pRoot);
return 0;
}
2.设计包含min函数的栈。
定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。
#include <deque>
#include <assert.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:
deque<T> m_data; // the elements of stack
deque<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();
}
// insert 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);
// set the index of minimum elment in m_data at the end of m_minIndex
if(m_minIndex.size() == 0)
m_minIndex.push_back(0);
else
{
if(value < m_data[m_minIndex.back()])
m_minIndex.push_back(m_data.size() - 1);
else
m_minIndex.push_back(m_minIndex.back());
}
}
// erease 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();
}
// get the minimum element of stack
template <typename T> const T& CStackWithMin<T>::min() const
{
assert(m_data.size() > 0);
assert(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。*/
//July 2010/10/18
#include <iostream.h>
int maxSum(int* a, int n)
{
int sum=0;
int b=0;
for(int i=0; i<n; i++)
{
if(b<0)
b=a[i];
else
b+=a[i];
if(sum<b)
sum=b;
}
return sum;
}
int main()
{
int a[10]={1,-8,6,3,-1,5,7,-2,0,1};
cout<<maxSum(a,10)<<endl;
return 0;
}
/*
4.在二元树中找出和为某一值的所有路径
题目：输入一个整数和一棵二元树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
例如 输入整数22和如下二元树
10
/ \
5 12
/ \
4 7
则打印出两条路径：10, 12和10, 5, 7。
二元树节点的数据结构定义为：
struct BinaryTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BinaryTreeNode *m_pLeft; // left child of node
BinaryTreeNode *m_pRight; // right child of node
};
*/
//2010/10/18 July
//引用自283 楼 firstfhy 的回复。
//二元树节点
class BinaryTreeNode
{
int m_nValue; // value of node
BinaryTreeNode m_pLeft; // left child of node
BinaryTreeNode m_pRight; // right child of node
public BinaryTreeNode(int m_nValue)
{
this.m_nValue = m_nValue;
}
public boolean left()
{
return m_pLeft == null ? false : true;
}
public boolean right()
{
return m_pRight == null ? false : true;
}
public boolean isLeaf()
{
return !(left() || right());
}
public BinaryTreeNode getChild(int lr)
{
return lr == 0 ? m_pLeft : m_pRight;
}
}
//记录结果路径的链表节点
class Result
{
String path;
Result next;
Result pre;
public Result(String path)
{
this.path = path;
}
}
public class MicroSoftEx004
{
/**二元树根节点*/
private BinaryTreeNode root;
/**目标数*/
int target;
/**累计变量*/
private int count;
/**记录路径*/
private String path = "";
/**记录结果路径的链表*/
private Result result = new Result(null);
/**构建二元树*/
public void bulitTree()
{
root = new BinaryTreeNode(10);
root.m_pLeft = new BinaryTreeNode(5);
root.m_pRight = new BinaryTreeNode(12);
root.m_pLeft.m_pLeft = new BinaryTreeNode(4);
root.m_pLeft.m_pRight = new BinaryTreeNode(7);
}
/*
* 在二元树中找出和为某一值的所有路径
* 先搜索左子树，后搜索右子树，
当遇到非叶子节点累计大于等于目标值时或叶子节点累计不等于目标值时该路径搜索失败
* 二元树节点,左子树为0，右子树为1
*/
public void solve(BinaryTreeNode root, int lr)
{
int len = path.length() + 1;//记录当前是第几层节点
count += root.m_nValue;//累加
int temp = count;//记录当前值
if(count < target && !root.isLeaf())
{
//非叶子节点且累计小于目标值时继续搜索
path += lr + "";//记录当前搜索的子树的左右[0|1]
if(root.left())
solve(root.m_pLeft, 0);//搜索左子树
path = path.substring(0, len);//去除左子树的路径信息
count = temp;//还原当前值
if(root.right())
solve(root.m_pRight, 1);//搜索右子树
count = temp;//还原当前值
}
else if(count == target && root.isLeaf())
{
//找到所需路径
path += lr + "";//记录当前搜索的子树的左右[0|1]
result.next = new Result(path);//添加新的结果
result.next.pre = result;//新结果前驱为之前结果节点
result = result.next;//指向新结果节点
}
}
public static void main(String[] args)
{ // TODO Auto-generated method stub
MicroSoftEx004 ex = new MicroSoftEx004();
ex.bulitTree();
ex.target = 22;
ex.solve(ex.root, 0);
BinaryTreeNode root;
while(ex.result.path != null)
{
root = ex.root;
System.out.print(root.m_nValue + " ");
for(int i = 1;i < ex.result.path.length();i++)
{
root = root.getChild(Integer.parseInt(ex.result.path.substring(i, i + 1)));
System.out.print(root.m_nValue + " ");
}
System.out.println();
ex.result = ex.result.pre;
}
}
}
/*5.查找最小的k个元素
题目：输入n个整数，输出其中最小的k个。
例如输入1，2，3，4，5，6，7和8这8个数字，
则最小的4个数字为1，2，3和4。
*/
//1.快排思想 O(n*logk) 2.建最大堆，大小为k，O(n*logk) 3.选择排序 O(n*k)
//July 2010/10/18
//引用自116 楼 wocaoqwer 的回复。
#include<iostream>
using namespace std;
class MinK{
public:
MinK(int *arr,int si):array(arr),size(si){}
bool kmin(int k,int*& ret){
if(k>size)
{
ret=NULL;
return false;
}
else
{
ret=new int[k--];
int i;
for(i=0;i<=k;++i)
ret[i]=array[i];
for(int j=(k-1)/2;j>=0;--j)
shiftDown(ret,j,k);
for(;i<size;++i)
if(array[i]<ret[0])
{
ret[0]=array[i];
shiftDown(ret,0,k);
}
return true;
}
}
void remove(int*& ret){
delete[] ret;
ret=NULL;
}
private:
void shiftDown(int *ret,int pos,int length){
int t=ret[pos];
for(int s=2*pos+1;s<=length;s=2*s+1){
if(s<length&&ret[s]<ret[s+1])
++s;
if(t<ret[s])
{
ret[pos]=ret[s];
pos=s;
}
else break;
}
ret[pos]=t;
}
int *array;
int size;
};
int main()
{
int array[]={1,2,3,4,5,6,7,8};
MinK mink(array,sizeof(array)/sizeof(array[0]));
int *ret;
int k=4;
if(mink.kmin(k,ret))
{
for(int i=0;i<k;++i)
cout<<ret[i]<<endl;
mink.remove(ret);
}
return 0;
}