/*

* playcode.cpp

*

* Copyright 2012 radiohead <radiohead@ubuntu>

*

* This program is free software; you can redistribute it and/or modify

* it under the terms of the GNU General Public License as published by

* the Free Software Foundation; either version 2 of the License, or

* (at your option) any later version.

*

* This program is distributed in the hope that it will be useful,

* but WITHOUT ANY WARRANTY; without even the implied warranty of

* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

* GNU General Public License for more details.

*

* You should have received a copy of the GNU General Public License

* along with this program; if not, write to the Free Software

* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,

* MA 02110-1301, USA.

*

* http://blog.csdn.net/v_JULY_v/article/details/6234496

*/

#include <iostream>

#include <vector>

#include <algorithm>

#include <string.h>

using namespace std;

/*

* 1、有一个整数数组，请求出两两之差绝对值最小的值,

* 记住，只要得出最小值即可，不需要求出是哪两个数。

*

*/

int MinABSValue(vector<int> &vc)

{

int i, j;

int nTmp, nMin = 0x7FFFFFFF;

for (i = 0; i < vc.size(); ++i)

{

for (j = i + 1; j < vc.size(); ++j)

{

nTmp = abs(vc[i] - vc[j]);

if (nMin > nTmp) nMin = nTmp;

}

}

return nMin;

}

/*

*2、写一个函数，检查字符是否是整数，如果是，返回其整数值。

* （或者：怎样只用4行代码编写出一个从字符串到长整形的函数？）

*

*/

int CheckChar(char *pcStr,int nLen)

{

int i = 0;

int nNum = 0;

if (pcStr == NULL) return -1;

for (i = 0; i < nLen; ++i)

{

if (pcStr[i] < '0' || pcStr[i] > '9') return -1;

nNum = nNum * 10 + (pcStr[i] - '0');

}

return nNum;

}

/*

* 3、给出一个函数来输出一个字符串的所有排列。

*

*/

void SwapChar(char *p, char *q)

{

char c;

c = *p;

*p= *q;

*q = c;

}

void Permutation(char *pcStr, char *pcBegin)

{

char *p = NULL;

if (pcStr == NULL || pcBegin == NULL) return;

if (*pcBegin == '\0')

{

cout << pcStr << endl;

return;

}

for (p = pcBegin; *p != '\0'; ++p)

{

SwapChar(p, pcBegin);

Permutation(pcStr, pcBegin + 1);

SwapChar(p, pcBegin);

}

}

/*

* 4、（a）请编写实现malloc()内存分配函数功能一样的代码。

* （b）给出一个函数来复制两个字符串A和B。字符串A的后几个字节和字符串B的前几个字节重叠。

*

*/

void* MyMalloc(int nSize)

{

void *p = NULL;

if ((p = malloc(nSize)) == NULL) return NULL;

return p;

}

void CopyStr(char *pcStrA, char *pcStrB)

{

char *pcTmp = NULL;

pcTmp = (char *)malloc(strlen(pcStrA) + 1);

strcpy(pcTmp, pcStrA);

while (pcTmp != NULL && *pcTmp != '\0')

{

*pcStrB = *pcTmp;

++pcTmp;

++pcStrB;

}

if (pcTmp != NULL) free(pcTmp);

}

/*

* 6、怎样从顶部开始逐层打印二叉树结点数据？请编程。

*

*/

typedef struct _BTNode

{

int nData;

struct _BTNode *pLeft;

struct _BTNode *pRight;

struct _BTNode *pParant;

}BTNode, *LPBTNode, *LPBTree;

typedef struct _BTQNode

{

LPBTNode pData;

struct _BTQNode *next;

struct _BTQNode *prev;

}BTQNode, *LPBTQNode;

typedef struct _BTQueue

{

LPBTQNode pHead;

LPBTQNode pTail;

}BTQueue, *LPBTQueue;

void InitBTQueue(LPBTQueue pBTQueue)

{

pBTQueue->pHead = NULL;

pBTQueue->pTail = NULL;

}

int IsEmpty(LPBTQueue pBTQueue)

{

if (pBTQueue->pHead == NULL || pBTQueue->pTail == NULL) return 1;

return 0;

}

void EnQueue(LPBTQueue pBTQueue, LPBTNode pBTNode)

{

LPBTQNode pBTQNode = NULL;

pBTQNode = (LPBTQNode)malloc(sizeof(BTQNode));

memset(pBTQNode, 0, sizeof(BTQNode));

pBTQNode->pData = pBTNode;

pBTQNode->next = pBTQueue->pTail;

pBTQueue->pTail = pBTQNode;

if (pBTQueue->pHead == NULL) pBTQueue->pHead = pBTQueue->pTail;

}

LPBTNode DeQueue(LPBTQueue pBTQueue)

{

LPBTNode pBTNode = NULL;

LPBTQNode pBTQNode = NULL;

if (IsEmpty(pBTQueue)) return NULL;

pBTQNode = pBTQueue->pHead;

pBTQueue->pHead = pBTQNode->prev;

if (pBTQueue->pHead != NULL) pBTQueue->pHead->next = NULL;

else pBTQueue->pTail = NULL;

pBTNode = pBTQNode->pData;

free(pBTQNode);

return pBTNode;

}

void TraversalTreeByScope(LPBTree pBTree)

{

LPBTNode pBTHead, pBTNode;

BTQueue BtQueue;

pBTHead = pBTree;

InitBTQueue(&BtQueue);

EnQueue(&BtQueue, pBTHead);

while (!IsEmpty(&BtQueue))

{

pBTNode = DeQueue(&BtQueue);

cout << pBTNode->nData << " ";

if (pBTNode->pLeft != NULL) EnQueue(&BtQueue, pBTNode->pLeft);

if (pBTNode->pRight != NULL) EnQueue(&BtQueue, pBTNode->pRight);

}

}

/**

* 7、怎样把一个链表掉个顺序（也就是反序，注意链表的边界条件并考虑空链表）？

*

*/

typedef struct _LNode

{

int data;

struct _LNode *next;

}LNode, *LPLNode;

void ListReverseOrder(LPLNode pLNode)

{

LPLNode pNode = NULL, pNextNode = NULL;

if (pLNode->next == NULL) return;

pNode = pLNode->next;

pLNode->next = NULL;

while (pNode != NULL)

{

pNextNode = pNode->next;

pNode->next = pLNode->next;

pLNode->next = pNode;

pNode = pNextNode;

}

}

/**

* 8、请编写能直接实现int atoi(const char * pstr)函数功能的代码。

*

*/

int MyAtoi(const char *pcStr)

{

int num = 0, sym = 1;

if (*pcStr == '+')

{

++pcStr;

}

else if (*pcStr == '-')

{

++pcStr;

sym = -1;

}

while (*pcStr != '\0')

{

num = num * 10 + (*pcStr - '0');

++pcStr;

}

return sym * num;

}

/**

* 9.编程实现两个正整数的除法，当然不能用除法操作符。

*

*/

int div_int(const int x, const int y)

{

int left_num, result;

int multi;

left_num = x;

result = 0;

multi = 0;

while(left_num>=y)

{

multi = 1;

while(y*multi <= (left_num>>1))

multi = multi<<1;

result += multi;

left_num -= y*multi;

}

return result;

}

void devide(int val1, int val2, int& res, int &rev)

{

int maxv = max(val1, val2);

int minv = min(val1, val2);

res = 0;

rev = 0;

if(maxv == minv){

res = 1;

rev = 0;

return;

}else{

while(maxv > minv){

maxv = maxv - minv;

res += 1;

}

rev = maxv;

return;

}

}

/**

* 10、在排序数组中，找出给定数字的出现次数

*

*/

int FindNumTimes(int *pnArray, int size, int n)

{

int i, count = 0;

for (i = 0; i < size; ++i)

{

if (pnArray[i] == n) break;

}

while (i < size)

{

if (pnArray[i++] == n) ++count;

else break;

}

return count;

}

/**

* 13、设计一个算法，找出二叉树上任意两个结点的最近共同父结点。

*

*/

LPBTNode FindTheParant(LPBTree pBTree, LPBTNode pBTNode1, LPBTNode pBTNode2)

{

int i = 0, j = 0;

LPBTNode aNode1[32] = {0}, aNode2[32] = {0};

while (pBTNode1 != pBTree)

{

aNode1[i++] = pBTNode1;

pBTNode1 = pBTNode1->pParant;

}

while (pBTNode2 != pBTree)

{

aNode2[j++] = pBTNode2;

pBTNode2 = pBTNode2->pParant;

}

if (aNode1[i] != aNode2[j]) return pBTree;

while (aNode1[i] == aNode2[j]) --i, --j;

return aNode1[++i];

}

/**

* 14、一棵排序二叉树，令 f=(最大值+最小值)/2，

* 设计一个算法，找出距离f值最近、大于f值的结点。

*

*/

LPBTNode FindTheNode(LPBTree pBTree, int f)

{

/*

* int f, max, min;

* LPBTNode pBTNode;

*

pBTNode = pBTree;

while (pBTNode->pLeft != NULL) pBTNode = pBTNode->pLeft;

max = pBTNode->data;

pBTNode = pBTree;

while (pBTNode->pRight != NULL) pBTNode = pBTNode->pRight;

min = pBTNode->data;

f = (max + min)/2;

*/;

if (f >= pBTree->nData && f < pBTree->pLeft->nData) return pBTree;

else if (f < pBTree->nData && f >= pBTree->pRight->nData) return pBTree->pRight;

else if (f >= pBTree->pLeft->nData) FindTheNode(pBTree->pLeft, f);

else if (f < pBTree->pRight->nData) FindTheNode(pBTree->pRight, f);

else return NULL;

}

void PrintMatrixCircle(int **num,int sX,int sY,int eX,int eY);

//给定矩阵，给定行列，由外向内顺时针打印数字

void PrintMatrixClockwisely(int **matrix,int rows,int columns)

{

if(matrix == NULL || rows < 0 || columns < 0)

return;

int startX = 0;

int startY = 0;

int endX = rows - 1;

int endY = columns - 1;

while(1)

{

if(startX > endX && startY > endY)

break;

if(startX == endX && startY > endY)

break;

if(startX > endX && startY == endY)

break;

PrintMatrixCircle(matrix,startX,startY,endX,endY);

++startX;

++startY;

--endX;

--endY;

}

}

//对于给定矩阵，给定对角线上两点，打印这一周的元素

void PrintMatrixCircle(int **num,int sX,int sY,int eX,int eY)

{

//只有一行的情况，直接打印，返回。

if(sX == eX)

{

for(int j = sY;j <= eY;++j)

{

cout<<*(*(num+sX)+j)<<"\t";

}

return;

}

//只有一列的情况，直接打印，返回。

if(sY == eY)

{

for(int i = sX;i <= eX;++i)

{

cout<<*(*(num+i)+sY)<<"\t";

}

return;

}

//一般的情况打印四行

for(int p = sY;p < eY;++p)

{

cout<<*(*(num+sX)+p)<<"\t";

}

for(int q = sX;q < eX;++q)

{

cout<<*(*(num+q)+eY)<<"\t";

}

for(int m = eY;m > sY;--m)

{

cout<<*(*(num+eX)+m)<<"\t";

}

for(int n = eX;n > sX;--n)

{

cout<<*(*(num+n)+sY)<<"\t";

}

}

void knuth(int n, int m)

{

int i;

srand((unsigned int)time(0));

for (i = 0; i < n; ++i)

{

if (rand()%(n - i) < m)

{

cout << i << " ";

--m;

}

}

cout << endl;

}

int main(int argc, char **argv)

{

//char acStr[] = "123";

//cout << CheckChar(acStr, strlen(acStr)) << endl;

//Permutation(acStr, acStr);

//int n = atoi("+123");

//cout << n <<endl;

int a[][5] = {{1, 2, 3, 4, 5},

{6, 7, 8, 9, 10},

{11, 12, 13, 14, 15},

{16, 17, 18, 19, 20},

{21, 22, 23, 24, 25}};

int *a1[5] = {a[0], a[1], a[2], a[3], a[4]};

int **a2 = a1;

//PrintArray(a, 5, 5);

PrintMatrixClockwisely(a2, 5, 5);

cout << endl;

//knuth(100, 30);

return 0;

}