一，数值的整数次方。
1）题目：实现函数double Power(double base, int exponent)，求base 的exponent 次方。不需要考虑溢出。
2）分析：这是一道看起来很简单的问题。却暗藏玄机
3）源码：
第一反应：我想这个代码应该都能写出来吧
#include <iostream>
using namespace std;
double Power(double base, int exponent)
{
double result = 1.0;
for(int i = 1; i <= exponent; ++i)
result *= base;
return result;
}
int main()
{
double result= Power(2, 4);
cout<<result<<endl;
}
面试不会仅仅考察这么简单的问题吧？是不是要考虑代码的鲁棒性呢？
1> exponent=0 ，则结果为 1
2> exponent<0 ，则结果应该是另一种求法
3> base = 0 或 base =1 应该单独考虑，base =0 exponent<0 相当于 0作为分母，这是错误的输入
4> 判断double 变量是否为0 不能直接使用（==）因为计算机表达的 小数存在误差
改进后的代码：
注意判断double 类型相等不能直接使用 ==
#include <iostream>
#include <stdlib.h>
using namespace std;
bool isInvalidInput=false;
double PowerWithUnsingedExponent(double base,unsigned int absExp)
{
double result=1.0; //这里初始化为1.0 ，当 absExp==0时候，直接返回结果 1
for(int i=0;i<absExp;i++)
result*=base;
return result;
}
//由于精度原因，double类型的变量不能用等号判断两个数是否相等，因此需要写equsl函数
bool equal(double a,double b)
{
if((a-b>-0.000001)&&(a-b<0.000001))
return true;
else
return false;
}
double Power(double base,int exponent)
{
//如果底数为0且指数小于0，则表明是非法输入。
if(equal(base,0.0) && exponent<=0)
{
isInvalidInput=true;
return 0;
}
unsigned int absExp;
//判断指数正负，去指数的绝对值
if(exponent<0)
absExp=(unsigned int)(-exponent);
else
absExp=(unsigned int)exponent;
double result=PowerWithUnsingedExponent(base,absExp);
//如果指数小于0则取倒数
if(exponent<0)
result=1/result;
return result;
}
int main()
{
double a=Power(2.0,13);
cout<<a<<endl;
system("pause");
}
其实这里PowerWithUnsingedExponent(double base,unsigned int absExp) 可以改进的，思想是：
比如求X16,可以分解成：X16=X8*X8，于是，只要求出X8，再做一个乘积就可得到X16，同理，X8=X4*X4，……依次类推。所以求X16，只需要做4次乘积：X*X、X2*X2、X4*X4、X8*X8。如果用上面代码所述方法，要进行15次乘积。
现在问题变成，怎么把exponent分解成2的若干个整数次方，尤其是当exponent不是2的整数次方时，比如6。这里就用到了二进制的一些特点，比如6的二进制为0110，6可以分解为4+2，二进制熟悉的话，这里应该是一眼可以看出来的，就是对应二进制为1的位所表示的数的和。则X6=X4*X2。
double PowerWithUnsingedExponent(double base,unsigned int absExp)
{
if(absExp==0)
return 1;
else if(absExp==1)
return base;
double result=1.0*base;
for(int i=2;i<=absExp;i=i*2)
result*=result;
if(absExp%2==1)//如果指数为奇数，还得再乘一次底数
result*=base;
return result;
}
二，单例模式
1）题目：设计一个类，我们只能生成该类的一个实例。
2）分析：只能生成一个实例的类是实现了Singleton模式的类型
3）源码：
class Singleton
{
private:
Singleton();
~Singleton();
static Singleton *instance;
public:
static Singleton* getSingleton ();
};
Singleton::instance=NULL;
Singleton::Singleton()
{
}
Singleton::~Singleton()
{
if(instance != NULL)
{
delete instance;
}
}
Singleton* Singleton::getSingleton()
{
if(instance==NULL)
instance=new Singleton();
return instance;
}
三，对称字符串的最大长度。
1）题目：输入一个字符串，输出该字符串中对称的子字符串的最大长度。比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。
2）分析：找出字符串中最长的回文子串
3）源码：注意string 的应用
#include <iostream>
#include <cstring>
using namespace std;
bool isPalindrome(string str)
{
int i=0;
int j=str.length()-1;
while(i<=j)
{
if(str.at(i)==str.at(j))
{
i++;
j--;
}
else
return false;
}
return true;
}
int getResult(string str)
{
string temp;
int position;
int length=1;
for(int i=0;i<str.length();++i)
{
for(int j=i+1;j<str.length();++j)
{
temp=str.substr(i,j-i+1);//注意这里的个数 j-i+1
cout<<temp<<endl;
if(isPalindrome(temp))
{
length=max(length,j-i+1); //注意这里的个数 j-i+1
position=i;
}
}
}
return length;
}
int main()
{
cout<<getResult("google")<<endl; //4
cout<<getResult("abcdeffedcba")<<endl;// 12
}
四，数组中超过出现次数超过一半的数字【精华】
1）题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。
2）分析：这是一道广为流传的面试题，包括百度、微软和Google在内的多家公司都曾经采用过这个题目。
解法一：O(n^2) 排序，则中间数为所求
解法二：O（nlogn）堆排序，则中间数为所求
解法三：O(n) 抵消法，temp记录假设的 目标数，count 记录该数个数，当遇到不同值时 count--。 遇到相同值时 count++。count == 0时更换一个假设目标
3）源码：
#include <iostream>
#include <cstring>
using namespace std;
int getMajor(int a[], int n)
{
int asume;
int count=0;
for(int i=0;i<n;++i)
{
if(count==0)
{
asume=a[i];
count++;
}
else if(asume == a[i])
count++;
else
count--;
}
return asume;
}
int main()
{
int s[]={1,2,1,3,1};
cout<<getMajor(s, 5)<<endl; //4
}
五，二叉树两个结点的最低共同父结点
1）题目：二叉树的结点定义如下：
struct TreeNode
{
int m_nvalue;
TreeNode* m_pLeft;
TreeNode* m_pRight;
};
输入二叉树中的两个结点，输出这两个结点在数中最低的共同父结点。
2）分析：求数中两个结点的最低共同结点是面试中经常出现的一个问题。这个问题至少有两个变种。
第一个变种：是二叉树是一种特殊的二叉树，查找二叉树。也就是树是排序过的，位于左子树上的结点都比父结点小，而位于右子树的结点都比父结点大。
求解：我们只需要从根结点开始和两个结点进行比较。
如果当前结点的值比两个结点都大，则最低的共同父结点一定在当前结点的左子树中。
如果当前结点的值比两个结点都小，则最低的共同父结点一定在当前结点的右子树中。
第二个变种：是树不一定是二叉树，每个结点都有一个指针指向它的父结点。于是我们可以从任何一个结点出发，得到一个到达树根结点的单向链表。因此这个问题转换为两个单向链表的第一个公共结点。我们在本面试题系列的第35题讨论了这个问题。
现在我们回到这个问题本身。所谓共同的父结点，就是两个结点都出现在这个结点的子树中。因此我们可以定义一函数，来判断一个结点的子树中是不是包含了另外一个结点。这不是件很难的事，我们可以用递归的方法来实现：
bool HasNode(TreeNode* pHead, TreeNode* pNode)
{
if(pHead == pNode)
return true;
bool has = false;
if(pHead->m_pLeft != NULL)
has = HasNode(pHead->m_pLeft, pNode);
if(!has && pHead->m_pRight != NULL)
has = HasNode(pHead->m_pRight, pNode);
return has;
}
我们可以从根结点开始，判断以当前结点为根的树中左右子树是不是包含我们要找的两个结点。如果两个结点都出现在它的左子树中，那最低的共同父结点也出现在它的左子树中。如果两个结点都出现在它的右子树中，那最低的共同父结点也出现在它的右子树中。如果两个结点一个出现在左子树中，一个出现在右子树中，那当前的结点就是最低的共同父结点。基于这个思路，我们可以写出如下代码：
TreeNode* LastCommonParent_1(TreeNode* pHead, TreeNode* pNode1, TreeNode* pNode2)
{
if(pHead == NULL || pNode1 == NULL || pNode2 == NULL)
return NULL;
// check whether left child has pNode1 and pNode2
bool leftHasNode1 = false;
bool leftHasNode2 = false;
if(pHead->m_pLeft != NULL)
{
leftHasNode1 = HasNode(pHead->m_pLeft, pNode1);
leftHasNode2 = HasNode(pHead->m_pLeft, pNode2);
}
if(leftHasNode1 && leftHasNode2)
{
if(pHead->m_pLeft == pNode1 || pHead->m_pLeft == pNode2)
return pHead;
return LastCommonParent_1(pHead->m_pLeft, pNode1, pNode2);
}
// check whether right child has pNode1 and pNode2
bool rightHasNode1 = false;
bool rightHasNode2 = false;
if(pHead->m_pRight != NULL)
{
if(!leftHasNode1)
rightHasNode1 = HasNode(pHead->m_pRight, pNode1);
if(!leftHasNode2)
rightHasNode2 = HasNode(pHead->m_pRight, pNode2);
}
if(rightHasNode1 && rightHasNode2)
{
if(pHead->m_pRight == pNode1 || pHead->m_pRight == pNode2)
return pHead;
return LastCommonParent_1(pHead->m_pRight, pNode1, pNode2);
}
if( (leftHasNode1 && rightHasNode2)
|| (leftHasNode2 && rightHasNode1))
return pHead;
return NULL;
}
接着我们来分析一下这个方法的效率。函数HasNode的本质就是遍历一棵树，其时间复杂度是O(n)（n是树中结点的数目）。由于我们根结点开始，要对每个结点调用函数HasNode。因此总的时间复杂度是O(n2)。
我们仔细分析上述代码，不难发现我们判断以一个结点为根的树是否含有某个结点时，需要遍历树的每个结点。接下来我们判断左子结点或者右结点为根的树中是否含有要找结点，仍然需要遍历。第二次遍历的操作其实在前面的第一次遍历都做过了。由于存在重复的遍历，本方法在时间效率上肯定不是最好的。
前面我们提过如果结点中有一个指向父结点的指针，我们可以把问题转化为求两个链表的共同结点。现在我们可以想办法得到这个链表。我们在本面试题系列的第4题中分析过如何得到一条中根结点开始的路径。我们在这里稍作变化即可：
// Get the path form pHead and pNode in a tree with head pHead
bool GetNodePath(TreeNode* pHead, TreeNode* pNode, std::list<TreeNode*>& path)
{
if(pHead == pNode)
return true;
path.push_back(pHead);
bool found = false;
if(pHead->m_pLeft != NULL)
found = GetNodePath(pHead->m_pLeft, pNode, path);
if(!found && pHead->m_pRight)
found = GetNodePath(pHead->m_pRight, pNode, path);
if(!found)
path.pop_back();
return found;
}
由于这个路径是从跟结点开始的。最低的共同父结点就是路径中的最后一个共同结点：
// Get the last common Node in two lists: path1 and path2
TreeNode* LastCommonNode(const std::list<TreeNode*>& path1,
const std::list<TreeNode*>& path2)
{
std::list<TreeNode*>::const_iterator iterator1 = path1.begin();
std::list<TreeNode*>::const_iterator iterator2 = path2.begin();
TreeNode* pLast = NULL;
while(iterator1 != path1.end() && iterator2 != path2.end())
{
if(*iterator1 == *iterator2)
pLast = *iterator1;
iterator1++;
iterator2++;
}
return pLast;
}
有了前面两个子函数之后，求两个结点的最低共同父结点就很容易了。我们先求出从根结点出发到两个结点的两条路径，再求出两条路径的最后一个共同结点。代码如下：
// Find the last parent of pNode1 and pNode2 in a tree with head pHead
TreeNode* LastCommonParent_2(TreeNode* pHead, TreeNode* pNode1, TreeNode* pNode2)
{
if(pHead == NULL || pNode1 == NULL || pNode2 == NULL)
return NULL;
std::list<TreeNode*> path1;
GetNodePath(pHead, pNode1, path1);
std::list<TreeNode*> path2;
GetNodePath(pHead, pNode2, path2);
return LastCommonNode(path1, path2);
}
这种思路的时间复杂度是O(n)，时间效率要比第一种方法好很多。但同时我们也要注意到，这种思路需要两个链表来保存路径，空间效率比不上第一个方法。
还有一种给力的 后续递归求解
TreeNode* getLCA(TreeNode* root, TreeNode* X, TreeNode *Y)
{
if (root == NULL)
return NULL;
if (X == root || Y == root)
return root;
TreeNode * left = getLCA(root->m_pLeft, X, Y);
TreeNode * right = getLCA(root->m_pRight, X, Y);
if (left == NULL)
return right;
else if (right == NULL)
return left;
else
return root;
}