要去看埃菲尔铁塔的顶
欢迎关注本人微博：t.cn/RGSLVUk
面试用的算法[持续更新...]
/*
#在一个二维数组中，每一行都按照从左到右递增的顺序排序，
#每一列都按照从上到下递增的顺序排序。请完成一个函数，
#输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
*/
int row,col,count = 0;
int** array = NULL;
int item = 14;
array = (int**)new int[10];
for( int i = 0 ; i<10 ; i++)
{
array[i] = (int*) new int [7];
for(int j =0 ;j < 7; j++)
{
array[i][j] = i+j ;
printf( " %d ",array[i][j]) ;
}
printf("\n");
}
row = 9;
col = 0;
while(row >= 0 && col <10 )
{
if( array [row][col] == item )
{
printf("find ! \n"); break;
}
else if( array [row][col] > item) //当前列
{
row -- ;
}
else //( array [row][col] < item )
{
col ++ ;
}
}
for( int i = 0 ; i<10 ; i++)
delete[] array[i];
delete[] array;
return 0;
---------------------------------------------------------------------------------
// 输入一个链表，从尾到头打印链表每个节点的值。
typedef struct _NODE
{
int data ;
_NODE * next;
}NODE , *PNODE;
void InitList(PNODE pNode)
{
PNODE temp = NULL ;
int data ;
while(1)
{
cin >> data;
if( data == -1)
break;
temp = new NODE ;
temp ->data = data ;
temp ->next = pNode->next;
pNode->next = temp ;
}
}
void showList(PNODE pNode)
{
PNODE temp = pNode->next ;
while(NULL != temp)
{
printf( "%d ," , temp->data);
temp = temp->next;
}
}
void DelList(PNODE pNode)
{
if( pNode == NULL )
return;
PNODE temp = pNode ;
while(NULL != temp)
{
PNODE q = temp->next ;
delete temp ;
temp = q;
}
}
// 逆序输出链表
void RevList(PNODE pNode)
{
if(NULL == pNode)
return ;
else
RevList(pNode->next);
printf("%d ," , pNode->data);
}
int _tmain(int argc, _TCHAR* argv[])
{
PNODE pNode = new NODE ;
pNode->next = NULL;
InitList(pNode);
showList(pNode);
RevList(pNode->next);
DelList(pNode);
return 0;
}
----------------------------------------------------------
// 已知前序 中序 重建二叉树
typedef struct _TreeNode {
char val;
_TreeNode *left;
_TreeNode *right;
}TreeNode ,*PTreeNode;
PTreeNode CreateTree()
{
PTreeNode ptr ;
char data;
cin>>data ;
if( data == '#')
ptr = NULL ;
else
{
ptr = new TreeNode;
ptr->val = data;
ptr->left = CreateTree();
ptr->right = CreateTree();
}
return ptr;
}
//前序 + 中序 构造树
int IniTtreeByFM(PTreeNode root , char* front ,char* middle ,int num)
{
int i = 0;
root->val = front[0];
root->left = root->right =NULL ;
if( num==0 ) return 0;
//找到根结点
for( i=0; i<num ; i++)
{
if(middle[i] == root->val)
break;
}
//如果存在 左孩子
if( i != 0 )
{
root->left = new TreeNode ;
IniTtreeByFM(root->left , front+1 ,middle ,i);
}
//如果存在 右孩子
if( i != (num - 1))
{
root->right = new TreeNode ;
IniTtreeByFM(root->right ,front + i +1 ,middle+i+1 ,i);
}
return 1;
}
void PreOrder(PTreeNode pNode)
{
if( pNode )
{
printf("%c ,",pNode->val);
PreOrder(pNode->left);
PreOrder(pNode->right);
}
}
void MidOrder(PTreeNode pNode)
{
if( pNode )
{
MidOrder(pNode->left);
printf("%c ,",pNode->val);
MidOrder(pNode->right);
}
}
void LastOrder(PTreeNode pNode)
{
if( pNode )
{
LastOrder(pNode->left);
LastOrder(pNode->right);
printf("%c ,",pNode->val);
}
}
void DestoryTree(PTreeNode pNode)
{
if( pNode )
{
DestoryTree(pNode->left);
DestoryTree(pNode->right);
delete pNode;
pNode = NULL;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
char front[] = {"ABDECF"};
char middle[] = {"DBEAFC"};
PTreeNode root = new TreeNode;
IniTtreeByFM( root ,front ,middle,6);
PreOrder(root);
printf("\n");
MidOrder(root);
printf("\n");
LastOrder(root);
DestoryTree(root);
return 0;
}
--------------------------------------------------
两个栈 实现 队列操作
// 入队
stack <int> stack1;
stack <int> stack2;
//入队 stack2倒入stack1
void EnQue(int data)
{
while( !stack2.empty())
{
stack1.push(stack2.top());
stack2.pop();
}
stack1.push(data);
}
//入队 stcack1倒入stak2
int DeQue()
{
int temp;
while(!stack1.empty())
{
stack2.push(stack1.top());
stack1.pop();
}
temp = stack2.top();
stack2.pop();
return temp;
}
main()
{
int i ;
for(i = 0; i< 100; i++)
EnQue(i);
for(i = 0; i< 100; i++)
printf("%d,",DeQue());
}
------------------------------------------------------
////////////////////
//旋转数组的最小数
//
// 现比较首尾元素 若 首>尾 则是 旋转数组
// 否则是 顺序数组 直接二分法
//
// 对于旋转数组 比较 mid位 与 start end 位
// 456123 456是前段 123 是后段
// 若 mid > start 则 在 start 后段
// 若 mid < end 则在end 前段
// 二分查找最小数
// 顺序查找 最小值
int InOrder(int table[] , int start , int end )
{
int i = start ;
int Min = table[start];
while(i<=end)
{
if( Min > table[i])
{
Min = i;
}
}
return Min;
}
int Min(int table[] ,int length)
{
int mid , start , end , minIndex = 0;
start = 0;
end = length - 1;
while( table[start] >= table[end])
{
mid = start + (end - start )/2;
if( end - start == 1) //结束条件 45[61]23
{
minIndex = end;
break;
}
if( table[start] == table[mid] && table[mid] == table[end])
{
minIndex = InOrder(table , start , end );
break;
}
if( table[mid] >= table[start] ) //在start 后面
{
start = mid ;
}
else if( table[mid] <= table[end]) //在end 前面
{
end = mid;
}
}
return minIndex ;
}
int main(int argc, char** argv) {
int table[] = { 3,4,4,5,6,2,2};
int table1[] = { 1,1,1,0,0,0}; //22
int table2[] = {1,2,3,4,5,6};
int table3[] = {3,4,5,6,1,2};
printf("%d" ,table1[ Min(table1,6)] );
printf("%d" ,table2[ Min(table2,6)] );
printf("%d" ,table3[ Min(table3,6)] );
printf("%d" ,table[ Min(table,7)] );
return 0;
}
///////////////////
2 进制 1 的个数
int num = 8;
int count = 0;
while( num )
{
++ count;
num = ( num - 1) & num;
}
printf("%d ", count);
-------------------------------------------------------
double 的 int 次方
#define INVALID_INPUT_BASE 0
bool status = true;
double DoubleExp( double base , int exp)
{
if( ( base < 0.000001 && base > -0.000001 ))
{
status = INVALID_INPUT_BASE;
return 0.0;
}
else if(exp == 0)
{
return 1;
}
else if (exp == 1)
{
return base;
}
else if( exp < 0)
{
return 1.0 / DoubleExp( base , -1.0 * exp);
}
else
{
return DoubleExp(base , exp -1) * base;
}
}
int main(int argc, char** argv) {
double t = 0;
t = DoubleExp(t , 1);
if( status )
{
cout << t << endl;
}
else
{
cout << " INVALID_INPUT_BASE"<<endl;
}
return 0;
}
-------------------------
// 倒数 第k 个结点
typedef struct _NODE
{
int data ;
struct _NODE* next ;
}NODE , *PNODE;
//
// 倒数 第 N 个结点
PNODE LastN( PNODE pList , int k)
{
int count = 0 ;
PNODE q = pList->next ;
while(q && count < k)
{
q = q->next;
++count;
}
if( count < k) return NULL ; // 不够k 个
PNODE t = pList->next;
while(q)
{
t = t->next;
q = q->next ;
}
return t;
}
-----------------------------------------------------------
链表反转
void RevserList(PNODE pNode)
{
PNODE p , q;
if( pNode == NULL) return ;
p = pNode->next;
pNode->next = NULL;
while(p)
{
q = p->next;
p->next = pNode->next;
pNode->next = p;
p = q;
}
}
//////////////////////
-------------------------------------------------------------------
比较 两棵 二叉树 是否相同
bool CmpTree ( PTreeNode pA ,PTreeNode pB)
{
if( pA == NULL && pB == NULL)
return true;
else if( pA == NULL || pB == NULL)
return false;
bool ResultLeft = CmpTree ( pA->left ,pB->left);
bool ResultRight = CmpTree(pA->right , pB->right);
return ResultLeft && ResultRight;
}
----------------------------------------------------------------
二叉树 镜像：
PTreeNode Mirror( PTreeNode pRoot)
{
if ( pRoot == NULL)
return NULL ;
PTreeNode pLeft = Mirror( pRoot->left ); // 先交换 左边
PTreeNode pRight = Mirror( pRoot->right);
pRoot->left = pRight ;
pRoot->right = pLeft ;
return pRoot ; //交换完毕 回去
}
------------------------------------------------------------
二叉树 结点个数
int GetTreeNum(PTreeNode pRoot)
{
if( NULL == pRoot)
return NULL;
return GetTreeNum( pRoot->left ) + GetTreeNum( pRoot->right ) + 1;
}
二叉树 深度
int GetTreeDeep(PTreeNode pRoot )
{
if( pRoot == NULL)
return 0;
int DeepLeft = GetTreeDeep( pRoot->left );
int DeepRight = GetTreeDeep(pRoot->right);
return DeepLeft > DeepRight ? (DeepLeft + 1) : (DeepRight + 1);
}
-------------------------------------------------------------------------------------
最低公共 父结点
bool FindTreeNode(PTreeNode pRoot , PTreeNode pNode)
{
if( pRoot == NULL || pNode == NULL)
return false;
else if( pRoot == pNode )
return true;
bool Findbool = FindTreeNode( pRoot->left , pNode);
if( ! Findbool )
{
Findbool = FindTreeNode(pRoot->right , pNode);
}
return Findbool;
}
pPTreeNode GetLastParentNode( PTreeNode pRoot , PTreeNode pNode1 , PTreeNode pNode2)
{
if( FindTreeNode(pRoot->left , pNode1 )) //从这个结点 左边找
{
if( FindTreeNode(pRoot->right , pNode2 ) ) //同时在右边找到
return pRoot ; //返回这个结点
else
return GetLastParentNode(pRoot->left , pNode1 , pNode2); //那都在左边找
}
else
{
if( FindTreeNode(pRoot->left , pNode2 ) )
return pRoot ;
else
return GetLastParentNode(pRoot->right , pNode1 , pNode2);
}
}
------------------------------------------------------------------------------------------------------
//判断是否是 子树
bool CmpTreeNode ( PTreeNode pRoot , PTreeNode pNode )
{
if( pRoot == NULL && pNode == NULL)
return true;
else if( pRoot == NULL || pNode== NULL)
return false;
bool CmpLeft = CmpTreeNode(pRoot->left , pNode->left );
bool CmpRight = CmpTreeNode(pRoot->right , pNode->right);
return CmpLeft && CmpRight;
}
bool IsSubTree( PTreeNode pRoot , PTreeNode pNode )
{
if( pRoot == NULL || pNode == NULL)
return false;
if( pRoot == pNode ) //这里判断是否 结点相同
return CmpTreeNode( pRoot , pNode );
bool findleft = IsSubTree (pRoot->left , pNode) ;
if( ! findleft )
{
findleft = IsSubTree(pRoot->right , pNode );
}
return findleft;
}
---------------------------------------------------------------------------
任意两个结点之间的距离
void print_path(char* path ,int index )
{
int i = 0;
for(;i<index;i++)
{
cout<<path[i] << "|" ;
}
cout<<endl;
}
void PrintPath( PTreeNode pRoot , char val ,char* path , int* index)
{
PTreeNode pCur = pRoot,pVisit = NULL ; //标记是否访问
stack<PTreeNode> s;
(*index) = 0 ;
//char path[100] = {0};
while( pCur || ! s.empty() )
{
while( pCur ) //移动到左下角
{
s.push(pCur);
path[(*index)++] = pCur->val; //保存访问结点
pCur = pCur->left;
}
pCur = s.top(); //出栈
s.pop();
if( pCur->right == NULL || pCur->right == pVisit) //访问过右边结点
{
// cout << pCur->val << ", ";
//访问 过 删除
if( pCur->val == val ) //如果查到 打印出路径
{
// print_path(path , index);
break;
}
(*index) -- ;
pVisit = pCur ; //标记访问过
pCur = NULL; //重置 也即 从栈中获取其 父结点
}
else
{
s.push(pCur);
pCur = pCur->right ;
}
}
}
int GetLength(char* pathA, char* pathB , int lenA , int lenB)
{
int count = 0;
while( (pathA[count] == pathB[count] ) && count < ( lenA>lenB? lenB:lenA ))
{
count ++ ;
}
cout<< "lenA : " <<lenA <<endl;
cout<< "lenB : " <<lenB <<endl;
cout<< "count : " <<count <<endl;
return lenA + lenB - 2*count;
}
// AB#CD###E#FG##H##
int main(int argc, char* argv[])
{
int a = 0;
int* p = &a;
int lenA , lenB;
char pathA[20] = {0};
char pathB[20] = {0};
PTreeNode ptr = CreateTree();
PrintPath(ptr , 'D' , pathA,&lenA);
PrintPath(ptr , 'F' , pathB,&lenB);
print_path(pathA,lenA);
print_path(pathB,lenB);
cout<<endl;
cout<< GetLength(pathA , pathB , lenA , lenB) << endl; //获得长度
DestoryTree(ptr);
return 0;
}