/*16题：输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。
例如输入
8
/ \
6 10
/\ /\
5 7 9 11
输出8 6 10 5 7 9 11。
*/
//题目不是我们所熟悉的，树的前序，中序，后序。即是树的层次遍历。
/*308 楼 panda_lin 的回复，说的已经很好了。:)
利用队列,每个单元对应二叉树的一个节点.
1：输出8， 队列内容: 6, 10
2：输出6, 6的2个子节点5,7入队列。队列的内容：10， 5， 7
3：输出10，10的2个子节点9，11入队列。队列的内容：5，7，9，11。
4：输出5 ，5没有子节点。队列的内容：7，9，11
5：。。。
由于STL已经为我们实现了一个很好的deque（两端都可以进出的队列），
我们只需要拿过来用就可以了。
我们知道树是图的一种特殊退化形式。
同时如果对图的深度优先遍历和广度优先遍历有比较深刻的理解，
将不难看出这种遍历方式实际上是一种广度优先遍历。
因此这道题的本质是在二元树上实现广度优先遍历。
*/
//July、2010/10/19/晚。
#include <deque>
#include <iostream>
using namespace std;
struct BTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BTreeNode *m_pLeft; // left child of node
BTreeNode *m_pRight; // right child of node
};
BTreeNode* pListIndex;
BTreeNode* pHead;
void PrintFromTopToBottom(BTreeNode *pTreeRoot)
{
if(!pTreeRoot)
return;
// get a empty queue
deque<BTreeNode *> dequeTreeNode;
// insert the root at the tail of queue
dequeTreeNode.push_back(pTreeRoot);
while(dequeTreeNode.size())
{
// get a node from the head of queue
BTreeNode *pNode = dequeTreeNode.front();
dequeTreeNode.pop_front();
// print the node
cout << pNode->m_nValue << ' ';
// print its left child sub-tree if it has
if(pNode->m_pLeft)
dequeTreeNode.push_back(pNode->m_pLeft);
// print its right child sub-tree if it has
if(pNode->m_pRight)
dequeTreeNode.push_back(pNode->m_pRight);
}
}
// 创建二元查找树
void addBTreeNode(BTreeNode * & pCurrent, int value)
{
if (NULL == pCurrent)
{
BTreeNode * pBTree = new BTreeNode();
pBTree->m_pLeft = NULL;
pBTree->m_pRight = NULL;
pBTree->m_nValue = value;
pCurrent = pBTree;
}
else
{
if ((pCurrent->m_nValue) > value)
{
addBTreeNode(pCurrent->m_pLeft, value);
}
else if ((pCurrent->m_nValue) < value)
{
addBTreeNode(pCurrent->m_pRight, value);
}
}
}
int main()
{
BTreeNode * pRoot = NULL;
pListIndex = NULL;
pHead = NULL;
addBTreeNode(pRoot, 8);
addBTreeNode(pRoot, 6);
addBTreeNode(pRoot, 5);
addBTreeNode(pRoot, 7);
addBTreeNode(pRoot, 10);
addBTreeNode(pRoot, 9);
addBTreeNode(pRoot, 11);
PrintFromTopToBottom(pRoot);
return 0;
}
//输出结果：
//8 6 10 5 7 9 11 Press any key to continue
/*
第17题：
题目：在一个字符串中找到第一个只出现一次的字符。
如输入abaccdeff，则输出b。
这道题是2006年google的一道笔试题。
*/
/*
思路剖析：由于题目与字符出现的次数相关，我们可以统计每个字符在该字符串中出现的次数.
要达到这个目的，需要一个数据容器来存放每个字符的出现次数。
在这个数据容器中可以根据字符来查找它出现的次数，
也就是说这个容器的作用是把一个字符映射成一个数字。
在常用的数据容器中，哈希表正是这个用途。
由于本题的特殊性，我们只需要一个非常简单的哈希表就能满足要求。
由于字符（char)是一个长度为8的数据类型，因此总共有可能256 种可能。
于是我们创建一个长度为256的数组，每个字母根据其ASCII码值作为数组的下标对应数组的对应项，
而数组中存储的是每个字符对应的次数。
这样我们就创建了一个大小为256，以字符ASCII码为键值的哈希表。
我们第一遍扫描这个数组时，每碰到一个字符，在哈希表中找到对应的项并把出现的次数增加一次。
这样在进行第二次扫描时，就能直接从哈希表中得到每个字符出现的次数了。
*/
//July、2010/10/20
#include <iostream.h>
#include <string.h>
char FirstNotRepeatingChar(char* pString)
{
if(!pString)
return 0;
const int tableSize = 256;
unsigned int hashTable[tableSize];
for(unsigned int i = 0; i < tableSize; ++ i)
hashTable[i] = 0;
char* pHashKey = pString;
while(*(pHashKey) != '\0')
hashTable[*(pHashKey++)] ++;
pHashKey = pString;
while(*pHashKey != '\0')
{
if(hashTable[*pHashKey] == 1)
return *pHashKey;
pHashKey++;
}
return *pHashKey;
}
int main()
{
cout<<"请输入 一串字符："<<endl;
char s[100];
cin>>s;
char* ps=s;
cout<<FirstNotRepeatingChar(ps)<<endl;
return 0;
}
/*
第18题：
题目：n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始，
每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。
当一个数字删除后，从被删除数字的下一个继续删除第m个数字。
求出在这个圆圈中剩下的最后一个数字。
July：我想，这个题目，不少人已经 见识过了。
*/
/*--------------------------------------------------------
先看这个题目的简单变形。
n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），
凡报到3的人退出圈子，问最后留下的是原来第几号的那个人?
---------------------------------------------------------*/
//July、2010/10/20
//我把这100题，当每日必须完成的作业，来做了。:）。
#include <stdio.h>
int main()
{
int i,k,m,n,num[50],*p;
printf("input number of person:n=");
scanf("%d",&n);
printf("input number of the quit:m="); //留下->18题
scanf("%d",&m); //留下->18题
p=num;
for(i=0;i<n;i++)
*(p+i)=i+1; //给每个人编号
i=0; //报数
k=0; //此处为3
// m=0; //m为退出人数 //去掉->18题
while(m<n-1)
{
if(*(p+i)!=0)
k++;
if(k==3)
{
*(p+i)=0; //退出，对应的数组元素置为0
k=0;
m++;
}
i++;
if(i==n)
i=0;
}
while(*p==0)
p++;
printf("The last one is NO.%d\n",*p);
}
/*--------------------------------------------
int LastRemaining_Solution2(int n, unsigned int m)
{
// invalid input
if(n <= 0 || m < 0)
return -1;
// if there are only one integer in the circle initially,
// of course the last remaining one is 0
int lastinteger = 0;
// find the last remaining one in the circle with n integers
for (int i = 2; i <= n; i ++)
lastinteger = (lastinteger + m) % i;
return lastinteger;
}
---------------------------------------------*/
/*
第19题：
题目：定义Fibonacci数列如下：
/ 0 n=0
f(n)= 1 n=1,2
\ f(n-1)+f(n-2) n>2
输入n，用最快的方法求该数列的第n项。
分析：在很多C语言教科书中讲到递归函数的时候，都会用Fibonacci作为例子。
因此很多程序员对这道题的递归解法非常熟悉，但....呵呵，你知道的。。
*/
//0 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597..........
//注意，当求第100项，甚至更大的项时，请确保你用什么类型，长整型?or long long int存储。
//不然，计算机，将 得不到结果。
//若用递归方法，可写 下如下代码：
#include <iostream.h>
int Fibona(int n)
{
int m;
if(n==0)
return 0;
else if(n==1||n==2)
return 1;
else
{
m=Fibona(n-1)+Fibona(n-2);
return m;
}
}
int main()
{
cout<<"-----------------"<<endl;
cout<<Fibona(17)<<endl;
return 0;
}
/*-----------------------------
科书上反复用这个题目来讲解递归函数，并不能说明递归解法最适合这道题目。
我们以求解f(10)作为例子来分析递归求解的过程。
要求得f(10)，需要求得f(9)和f(8)。同样，要求得f(9)，要先求得f(8)和f(7)……
我们用树形结构来表示这种依赖关系
f(10)
/ \
f(9) f(8)
/ \ / \
f(8) f(7) f(6) f(5)
/ \ / \
f(7) f(6) f(6) f(5)
更简单的办法是从下往上计算，首先根据f(0)和f(1)算出f(2)，再根据f(1)和f(2)算出f(3)……
依此类推就可以算出第n项了。很容易理解，这种思路的时间复杂度是O(n)。
其实，就是转化为非递归程序，用递推。!
------------------------------------------*/
long long Fibonacci_Solution2(unsigned n)
{
int result[2] = {0, 1};
if(n < 2)
return result[n];
long long fibNMinusOne = 1;
long long fibNMinusTwo = 0;
long long fibN = 0;
for(unsigned int i = 2; i <= n; ++ i)
{
fibN = fibNMinusOne + fibNMinusTwo;
fibNMinusTwo = fibNMinusOne;
fibNMinusOne = fibN;
}
return fibN;
}
这还不是最快的方法。下面介绍一种时间复杂度是O(logn)的方法。在介绍这种方法之前，先介绍一个数学公式：
{f(n), f(n-1), f(n-1), f(n-2)} ={1, 1, 1,0}n-1
(注：{f(n+1), f(n), f(n), f(n-1)}表示一个矩阵。在矩阵中第一行第一列是f(n+1)，第一行第二列是f(n)，第二行第一列是f(n)，第二行第二列是f(n-1)。)
有了这个公式，要求得f(n)，我们只需要求得矩阵{1, 1, 1,0}的n-1次方，因为矩阵{1, 1, 1,0}的n-1次方的结果的第一行第一列就是f(n)。这个数学公式用数学归纳法不难证明。感兴趣的朋友不妨自己证明一下。
现在的问题转换为求矩阵{1, 1, 1, 0}的乘方。如果简单第从0开始循环，n次方将需要n次运算，并不比前面的方法要快。但我们可以考虑乘方的如下性质：
/ an/2*an/2 n为偶数时
an=
\ a(n-1)/2*a(n-1)/2 n为奇数时
要求得n次方，我们先求得n/2次方，再把n/2的结果平方一下。如果把求n次方的问题看成一个大问题，把求n/2看成一个较小的问题。这种把大问题分解成一个或多个小问题的思路我们称之为分治法。这样求n次方就只需要logn次运算了。
/*
第20题：
题目：输入一个表示整数的字符串，把该字符串转换成整数并输出。
例如输入字符串"345"，则输出整数345。
*/
/*------------------------------
此题一点也不简单。不信，你就先不看一下的代码，
你自己先写一份，然后再对比一下，便知道了。
1.转换的思路：每扫描到一个字符，我们把在之前得到的数字乘以10再加上当前字符表示的数字。
这个思路用循环不难实现。
2.由于整数可能不仅仅之含有数字，还有可能以'+'或者'-'开头，表示整数的正负。
如果第一个字符是'+'号，则不需要做任何操作；如果第一个字符是'-'号，
则表明这个整数是个负数，在最后的时候我们要把得到的数值变成负数。
3.接着我们试着处理非法输入。由于输入的是指针，在使用指针之前，
我们要做的第一件是判断这个指针是不是为空。
如果试着去访问空指针，将不可避免地导致程序崩溃。
4.输入的字符串中可能含有不是数字的字符。
每当碰到这些非法的字符，我们就没有必要再继续转换。
最后一个需要考虑的问题是溢出问题。由于输入的数字是以字符串的形式输入，
因此有可能输入一个很大的数字转换之后会超过能够表示的最大的整数而溢出。
*/
//July、2010、10/22。
enum Status {kValid = 0, kInvalid};
int g_nStatus = kValid;
int StrToInt(const char* str)
{
g_nStatus = kInvalid;
long long num = 0;
if(str != NULL)
{
const char* digit = str;
// the first char in the string maybe '+' or '-'
bool minus = false;
if(*digit == '+')
digit ++;
else if(*digit == '-')
{
digit ++;
minus = true;
}
// the remaining chars in the string
while(*digit != '\0')
{
if(*digit >= '0' && *digit <= '9')
{
num = num * 10 + (*digit - '0');
// overflow
if(num > std::numeric_limits<int>::max())
{
num = 0;
break;
}
digit ++;
}
// if the char is not a digit, invalid input
else
{
num = 0;
break;
}
}
if(*digit == '\0')
{
g_nStatus = kValid;
if(minus)
num = 0 - num;
}
}
return static_cast<int>(num);
}
//在C语言提供的库函数中，函数atoi能够把字符串转换整数。
//它的声明是int atoi(const char *str)。该函数就是用一个全局变量来标志输入是否合法的。