面试题21包括min函数的栈
面试题22栈的压入、弹出序列
面试题23从上往下打印二叉树
面试题24二叉搜索树的后序遍历序列
面试题25二叉树中和为某一值的路径
面试题26复杂链表的复制
面试题27二叉搜索树与双向链表
面试题28字符串的排列
面试题29数组中出现次数超过一半的数字
面试题30最小的K个数
/****************************************************/
面试题21 包括min函数的栈 ：定义栈的数据结构，请在该类型中实现一个可以得到栈的最小元素的min函数。在该栈中。调用min、push及pop的时间复杂度都是O（1）
思 路：申请一个与原来栈stack大小同样的栈tmpStack。用来保存当前栈中最小元素。stack压入一个元素，tmpStack也压入一个元素，该元素与tmpStack.top比較，大则压入top 否则压入该元素。
出栈同一时候出栈。
实现例如以下：
template <typename> T;
class Stack
{
public:
Stack();
~Stack();
void pop();
void push(T &value);
T min();
private:
stack<T> m_stack;
stack<T> m_min;
};
void pop()
{
if (m_min.size() <= 0 || m_stack.size() <= 0)
{
return;
}
m_stack.pop();
m_min.pop();
}
void push(T &value)
{ if ( m_min.size() == 0 || value < m_min.top())
{
m_min.push(value); }
else
{
m_min.push(m_min.top());
} m_stack.push(value); }
T min()
{
if (m_min.size() > 0)
{
return m_min.top();
}
}
面试题22 栈的压入、弹出序列 ：输入两个序列。第一个是栈的压入顺序，请推断第二个1、2、3、4、5、6则4、5、3、2、1是出栈顺序。而4、3、5、1、2就不可能是该压栈序列。
思路：
实现例如以下：
bool IsPopOrder(const int *pPush, const int *pPop, int length)
{
const int *pPushNext = pPush;
const int *pPopNext = pPop;
bool result = false; if (pPush == NULL || pPop == NULL || length <= 0)
{
return false;
} stack<const int> iStack; while(pPopNext - pPop < length)/* 弹出序列还没有到头*/
{
while(iStack.top() != *pPopNext)
{
if (pPushNext - pPush == length)
{
break;
} iStack.push(*pPushNext);
pPushNext++;
} if (iStack.top() != *pPopNext)
{
break;
} iStack.pop();
pPopNext++;
} if (iStack.empty() && pPopNext - pPop == length)
{
return true;
} return false;
}
面试题23 从上往下打印二叉树 。二叉树的层序遍历
实现例如以下：
struct BinaryTreeNode
{
int data;
BinaryTreeNode *lchild;
BinaryTreeNode *rchild;
};
void LevelOrder(BinaryTreeNode *root)
{
BinaryTreeNode *pNode;
if (root == NULL)
{
return;
}
queue<BinaryTreeNode> iQueue;
iQueue.push(root);
while(!iQueue.empty())
{
pNode = iQueue.front();
if (pNode->lchild != NULL)
{
iQueue.push(pNode->lchild);
}
if (pNode->rchild != NULL)
{
iQueue.push(pNode->rchild);
} printf("%d",pNode->data);
iQueue.pop();
}
}
面试题24 二叉搜索树的后序遍历序列 ，给出一个数组，推断是否是二叉搜索树的后序遍历序列
思路：最后一个结点的值大于左子树的随意值。小于右子树的随意值
实现例如以下：
int IsSerchTree(int *squeue, int length)
{
int i,j; if (squeue == NULL || length <= NULL)
{
return false;
} for (i = 0; i < length; i++)
{
if (squeue[i] > squeue[length-1])
{
break;
}
} for (j = i, j <length; j++)
{
if (squeue[j] < squeue[length -1])
{
return false;
}
} if ((true == IsSerchTree(squeue, i)
&& (true == IsSerchTree(squeue + i,length - i - 1))) {
return true;
} }
面试题25 二叉树中和为某一值的路径
注意：vector 与 stack和queue的差别
vector能够从头部删除节点，也能够从尾部遍历整个结构
实现例如以下：
struct BinaryTreeNode
{
int data;
BinaryTreeNode *lchild;
BinaryTreeNode *rchild;
};
void SumPathTree(BinaryTreeNode *root, int expectSum, vector<int> &iPath, int currentSum)
{
if (root == NULL)
{
return;
} /* 採用前序遍历的方式，先处理根节点 */
currentSum += root->data;
iPatch.push_back(root->data); if ((currentSum == expectSum)
&& (root->lchild == NULL && root->rchild == NULL)
{
for (iterator iter = iPath.begin(); iter < iPath.end(); iter++)
{
printf("%d", *iter);
}
printf("\n");
} if (root->lchild != NULL)
{
SumPathTree(root->lchild,expectSum,iPath,currentSum);
} if (root->rchild != NULL)
{
SumPathTree(root->rchild,expectSum,iPath,currentSum);
} /* 假设以上路径都没有期望的值。则回溯到调用之前的结点 递归结束之后，一定回到根结点 */
iPath.pop_back();
currentSum-=root->data; }
面试题26 复杂链表的复制
struct ComplexListNode
{
int data;
ComplexListNode *next;
ComplexListNode *sibling;/* 指向不论什么一个结点 */
};
第一步：每一个节点后面赋值一个同样的结点
第二步：遍历偶数结点。将新结点中sibling指针指向该指的结点
第三步：将链表按奇数偶数。拆分成两个链表。
面试题27 二叉搜索树与双向链表 ，输入一个二叉搜索树，将一个二叉搜索树变成一个排序的双向链表
思路：採用中序遍历二叉树的方式，每次递归记录下来上次遍历到的结点，作为指针传入下次递归
实现例如以下：
struct BinaryTreeNode
{
int data;
BinaryTreeNode *lchild;
BinaryTreeNode *rchild;
};
void ConvertTree(BinaryTreeNode *root, BinaryTreeNode **lastNode)
{
if (root == NULL)
{
return;
} ConvertTree(root->lchild,lastNode); root->lchild = lastNode;
if (*lastNode != NULL)
{
(*lastNode)->rchild = root;
}
(*lastNode) = root; ConvertTree(root->rchild,lastNode);
} BinaryTreeNode *GetHeadNode(BinaryTreeNode *root)
{
BinaryTreeNode *head;
if (root == NULL)
{
return NULL;
} head = root;
while (head->lchild)
{
head = head->lchild;
}
return head;
}
面试题28 字符串的排列
比如：比如输入abc 输出abc的六种排列组合 abc bac ……
实现例如以下：
#include <iostream> void printOrderStr(char *str, int length, int index)
{ char temp; if (str == NULL || length == 0)
{
return;
} if (index == length)
{
for (int i = 0; i<length; i++)
printf("%c",str[i]);
printf("\n");
} for (int i = index; i < length; i++)
{
temp = str[index];
str[index] = str[i];
str[i] = temp; printOrderStr(str, length, index+1); temp = str[index];
str[index] = str[i];
str[i] = temp; }
}
int main()
{
char str[] = {'a', 'b', 'c'}; printOrderStr(str, 3, 0); }
扩展题，输入一个字符串输出字符串的各种组合，比如：输入abc 输出a、b、c、ab……abc
实现例如以下：
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
#include<assert.h> void Combination_m(char *string ,int number , vector<char> &result)
{
assert(string != NULL);
if(number == 0)
{
static int num = 1;
printf("第%d个组合\t",num++); vector<char>::iterator iter = result.begin();
for( ; iter != result.end() ; ++iter)
printf("%c",*iter);
printf("\n");
return ;
}
if(*string == '\0')
return ; result.push_back(*string);
Combination_m(string + 1 , number - 1 , result);
result.pop_back();
Combination_m(string + 1 , number , result);
} void Combination(char *string)
{
assert(string != NULL); int i , length = strlen(string);
for(i = 1 ; i <= 3 ; ++i)
{
vector<char> result;
Combination_m(string , i ,result);
}
} int main(void)
{
char str[] = "abc";
Combination(str);
getchar();
return 0;
}
面试题29 数组中出现次数超过一半的数字 。给定一个数组，当中有一个数组其个数超过一半。求该数
思路：
最简单的就是排序，求中位数。
採用一个数记录反复个数，一个数记录结果，详细实现例如以下：
int FindMoreThanHalf(int num[], int length)
{
int times = 0;
int result;
if (num == NULL || length <=0 )
{
return 0;/* 非法输入*/
} result = num[0];
times++;
for (int i = 1; i < length; i++)
{ if (num[i] == result)
{
times++;
} if (times == 0)
{
result = num[i];
} if (num[i] != result && times > 0 )
{
times--;
}
} return times;
}
面试题30 最小的K个数
#include <stdlib.h>
#include <stdio.h>
/* 求最小的K个数 */ int partition(int *psArray, int num, int startIndex, int endIndex)
{
int iTemp;
int i = startIndex;
int j = endIndex; if (psArray == NULL || num <= 0 || startIndex > endIndex || startIndex < 0 || endIndex < 0)
{
return 0;
} iTemp = psArray[0]; while (i < j)
{
while ((i < j) && (psArray[i] <= psArray[j]))
j--; if (i < j)
{
iTemp = psArray[i];
psArray[i] = psArray[j];
psArray[j] = iTemp;
} while((i < j) && (psArray[i] <= psArray[j]))
i++; if (i < j)
{
iTemp = psArray[i];
psArray[i] = psArray[j];
psArray[j] = iTemp;
}
}
return i;
}
void FindMinKNum(int *psArray, int num, int k)
{
int i;
int j;
if (k > num)
{
return;
} i = partition(psArray,num,0,num-1);
while (i != k-1)
{
if (i < k-1)
{
i = partition(psArray,num,i+1,num-1);
}
else
{
i = partition(psArray,num,0,i-1);
}
}
for (j = 0; j <= i; j++)
{
printf(" %d", psArray[j]);
}
printf("\n"); }
int main()
{
int a[]={3,4,5,1,2};
FindMinKNum(a, 5, 2); }
能够用O（n*logk）的时间复杂度加上O(k)的空间复杂度来实现。
void GetLeastNumbers(int *psArray, int length, int k)
{
if (psArray == NULL || length < 0 || k < 0 || length < k)
{
return;
} multiset<int, greater<int> > iMultiset;
multiset<int, greater<int> >::iterator iSetIterator; for (int i = 0; i < length; i++)
{
if (i < k)
{
iMultiset.insert(psArray[i]);
}
else
{
if (psArray[i] < *(iMultiset.begin()))
{
iMultiset.erase(iMultiset.begin());
iMultiset.insert(psArray[i]);
}
}
}
for (iSetIterator = iMultiset.begin(); iSetIterator != iMultiset.end(); iSetIterator++ )
{
printf(" %d", *iSetIterator);
}
printf("\n");
}