面试题1赋值运算符函数 
面试题2 实现Singleton模式 
面试题3 二维数组中的查找
 
面试题4 替换空格
 
面试题5 从头到尾打印链表
 
面试题6 重建二叉树
 
面试题7 用两个栈实现队列
 
面试题8 旋转数组的最小数字 
面试题9 斐波那契数列
 
面试题9(变形) 跳台阶
 
面试题9(变形) 变态跳台阶 
面试题9(变形) 矩形覆盖
 
面试题10 二进制中1的个数 

面试题1赋值运算符函数 

为以下类型加入赋值运算符

class CMyString
{
public:
CMyString(char *pData = NULL);
CMyString(const CMyString &str);
~CMyString(void); private:
char *m_pData;
};

答案例如以下:

CMyString& CMyString::operator==(const CMyString &str)
{
char *temp;
if (&str==this)/*指针推断*/
{
return *this;/*返回应用*/
}
temp= (char *)malloc(strlen(this->m_pData)+1);
strncpy(temp, this->m_pData, strlen(this->m_pData)); if (m_pData != NULL)
{
free(m_pData);
m_pData = NULL;
}
m_pData = (char *)malloc(strlen(str.m_pData)+1);
if (m_pData == NULL)
{
strncpy(this->m_pData,temp,strlen(temp));
return *this;
}
strncpy(this->m_pData, str.m_pData, strlen(str.m_pData));
return *this;
}

注意:

         1. 返回值是类型的引用 CMyString& ,使得能够连续赋值 str1 = str2 =str3

         2. 穿入參数是常量引用,假设是实例则会多出一个从形參到实參构造函数。

         3. 是否释放了自身内存,否则会出现内存泄露。

         4. 必须推断是否是自身实例。否则内存释放之后,会出现空指针訪问

         5. 申请内存是否推断申请成功,注意保存先前值,在没有申请成功的

面试题2 实现Singleton模式

答案例如以下:

单线程模式下的单利模式

class Singleton
{
public:
static Singleton* GetInstance(void)
{
if (m_instance == NULL)
{
m_instance = new Singleton();
}
return m_instance;
}
private:
Singleton();
static Singleton *m_instance;
};

说明:程序退出时会自己主动析构静态变量和全局变量

多线程模式下的单利模式

class Singleton
{
public:
static Singleton* GetInstance(void)
{
if (m_instance == NULL)
{
lockBase* lockbase = new lockBase();
lockBase->lock();
if (m_instance == NULL)
{
m_instance = new Singleton();
}
lockBase->unlock();
} return m_instance;
}
private:
Singleton();
static Singleton *m_instance; };
class lockBase{
protected:
friend class singleStance;
CRITICAL_SECTION cs;
public :
lockBase(){
::InitializeCriticalSection(&cs);
}
void lock(){
::EnterCriticalSection(&cs);
}
void unlock(){
::LeaveCriticalSection(&cs);
}
~lockBase(){
::DeleteCriticalSection(&cs);
} };

面试题3 二维数组中的查找

               在一个二维数组中,每一行都是从左到右递增,每一列都是从上到下递增。给定一个二维数组,推断一个数是否在这个二维数组中。

比如 7在以下的数组中 

 1,2,3

 4。5,6

 7,8,9 

答案例如以下:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define VOS_ERR 1
#define VOS_OK 0
int IsHaveValue(int str[][4],int a, int b, int value)
{
int i = 0;
int j = b - 1;
while(i<a && j >= 0)/* 还没有到达左下角*/
{
if (str[i][j] == value)
{
return VOS_OK;
}
else if (str[i][j] > value)/* 大于要查找的数 ,去列 */
{
j--;
}
else
{
i++;
}
}
return VOS_ERR;
}
int main()
{
int str[][4] = { {1, 2, 8, 9},
{2, 4, 9,12},
{4, 7, 10, 13},
{6, 8, 11, 15}};
printf("%d\n",IsHaveValue(str,4,4,7));
printf("%d\n",IsHaveValue(str,4,4,26));
getchar();
}

注意:

1、简单粗暴的方式就是遍历,这样的显而易见的方式绝对不是面试官想要的。

         2、从右上角開始查找,大于要查找的数。则该列都不是想要的,删除该列(列以下都大于要查找数)

                                                   小于要查找的数,则该行都不是想要的,删除该行(行曾经都小于要查找数)

  相等则返回OK

面试题4 替换空格 

                实现一个函数。输入一个字符串,将字符串中的空格替换成%20。比如输入"we are happy"替换成"we%20are%20happy"

实现例如以下:         

#include <iostream>
#define VOS_OK 0
#define VOS_ERR 1 char *ReplaceBank(char * str)
{
int strLen = 0;
int iBankNum = 0;
int iTotalNUm = 0;
char *strResult = NULL;
char *strTemp =NULL;
strLen = strlen(str); for (int i=0; i<strLen; i++)
{
if (str[i] == ' ')
{
iBankNum++;
}
}
iTotalNUm = strLen + 2*iBankNum + 1;
strResult = (char*)malloc(iTotalNUm);
if (strResult == NULL)
{
return NULL;
}
strTemp = strResult; for (int i = 0; i<iTotalNUm; i++)
{
if (str[i] == ' ')
{
*strTemp++ = '%';
*strTemp++ = '2';
*strTemp++ = '0';
}
else
{
*strTemp++ = str[i];
}
}
return strResult; }
int main()
{
printf("%s\n",ReplaceBank("we are happy"));
getchar();
return VOS_OK;
}

注意:

1、空格*2 + 原来的长度是最后的长度。

2、假设传入的是一个数组,则要复制成的长度要与原来的进行比較,假设大于数组长度则返回错误。

同类题目:

        1、有两个排序的数组A、B,当中A中有空间容纳下B,实现一种方法将B插入到A中,并排序。

       思路:从A、B的尾部进行比較。将大的插入到合适的位置

面试题5 从尾到头打印链表,输入一个链表的头指针,从尾部到头输出该链表。

思路:

假设同意改变链表结构,则将链表指针翻转,即先前的头部变成了尾部,尾部变成了头部,然后顺序顺序输出该链表。

        假设不同意改变链表结构。则将顺序读链表,并依次放入栈中,等读完链表之后,将栈中元素依次出栈则得到结果。

实现例如以下:

void PrintListReverse(Node *pHead)
{
stack<Node*> m_stack;
Node *pNode = pHead;
while(pNode != NULL)
{
m_stack.push(pNode);
pNode++;
} while(!m_stack.empty())
{
pNode = m_stack.top();
printf("%s",pNode->data);
m_stack.pop();
}
}

    使用栈来实现的还有一种变形为递归:

void PrintListReverse(Node *pHead)
{
if (pHead == NULL)
return;
if (pHead->next != NULL)
PrintListReverse(pHead->next);
printf("%s",pHead->data);
}

面试题6 重建二叉树 

输入二叉树的前序遍历和中序遍历结果,输出该树。

比如输入前序遍历结果为:1、2、4、7、3、5、6、8。中序遍历结果为:4、7、2、1、5、3、8、6

BinaryTreeNode *Construct(int *preOrder,int *inOrder,int length)
{
if (preOrder == NULL || preOrder == NULL || length <= 0)
{
return NULL;
}
BinaryTreeNode * root = ConstructCore(preOrder,preOrder + length - 1, inOrder,inOrder + length - 1);
}
BinaryTreeNode *ConstructCore(int *preOrderStart, int *preOrderEnd,
int *inOrderStart, int *inOrderEnd)
{
/*參数在调用处保证*/
BinaryTreeNode * root;
int inOrderleftLength = 0;
int *inOrderLocal; root = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
if (root == NULL)
{
return NULL;
}
root->data = *preOrderStart;
root->lchild = root->rchild = NULL; if (preOrderStart == preOrderEnd)
{
if (inOrderStart == inOrderEnd && *perOrderStart == *inOrderStart)
{
return root;
} throws exception;
} inOrderLocal = inOrderStart;
while(inOrderLocal++ != inOrderEnd)
{
if(*inOrderLocal != *preOrderStart)
{
inOrderleftLength++;
}
break;
}
root->lchild = ConstructCore(preOrderStart+1,preOrderStart+inOrderleftLength,inOrderStart,inOrderStart+inOrderleftLength);
root->rchild = ConstructCore(preOrderStart+inOrderleftLength+1,preOrderEnd, inOrderStart+inOrderleftLength+1,inOrderEnd);
return root; }

注意:

1、利用递归的方法求解,注意入參。

面试题7 用两个栈实现队列

template <typename T>
class CQueue
{
public:
CQueue();
~CQueue();
void appendTail(const T &node);
T deleteHead();
private:
stack<T> stack1;
stack<T> stack2;
};
void CQueue::appendTail(const T & node)
{
stack1.push(node);
}
T CQueue::deleteHead()
{
T data;
if (!stack2.empty())
{
data = stack2.top();
stack2.pop();
return data;
} while (!stack1.empty())
{
data = stack1.top();
stack2.push(data);
stack1.pop();
} if (!stack2.empty())
{
data = stack2.top();
stack2.pop();
return data;
} throw exception; }

同类题目:

使用两个队列。实现一个栈。

实现例如以下:

class CStack
{
public:
CStack();
~CStack();
void pop();
void push();
private:
queue<T> queue1;
queue<T> queue2;
};
void CStack::push()
{
queue1.push();
}
void CStack::pop()
{
T data;
while (queue1.size()>1)
{
data = queue1.front();
queue2.push(data);
queue1.pop();
}
if (queue1.size()== 1)
{
queue1.pop();
return;
} if (queue1.size()== 0)
{
if (queue2.size() == 0)
{
return;
} while (queue2.size()>1)
{
data = queue2.front();
queue1.push(data);
queue2.pop();
}
if (queue2.size() == 1)
{
queue2.pop();
}
} }

面试题8 旋转数组的最小数字 

#include <iostream>
int GetMinValueException(int a[],int beginIndex, int endIndex)
{
int minValue;
if (beginIndex >= endIndex)
return a[beginIndex]; minValue = a[beginIndex]; for (int i = beginIndex + 1; i<=endIndex; i++)
{
if (a[i] < minValue)
minValue = a[i];
}
return minValue; }
int GetMinValue(int a[],int beginIndex, int endIndex)
{
int midIndex = (beginIndex + endIndex)>>1; if (beginIndex == endIndex)
{
return a[midIndex];
} if (a[beginIndex] < a[endIndex])
{
return a[beginIndex];
} if (a[midIndex] > a[beginIndex])
{
if (a[midIndex] > a[endIndex])
{
return GetMinValue(a,midIndex + 1, endIndex);
}
else
{
return GetMinValue(a,beginIndex,midIndex - 1);
}
}
if (a[midIndex] < a[beginIndex])
{
return GetMinValue(a,beginIndex,midIndex);
} return GetMinValueException(a,beginIndex, endIndex); }
int main()
{
int a[]={3,4,5,1,2};
int b[]={4,5,1,2,3};
int c[]={5,1,2,3,4};
int d[]={1,2,3,4,5};
int e[]={0,0,-1,0,0};
printf("%d\n",GetMinValue(a,0, 4));
printf("%d\n",GetMinValue(b,0, 4));
printf("%d\n",GetMinValue(c,0, 4));
printf("%d\n",GetMinValue(d,0, 4));
printf("%d\n",GetMinValue(e,0, 4));
}

面试题9 斐波那契数列。写一个函数。输入n。输出斐波那契的第n个元素。

答案例如以下:

#include <iostream>
int Fibonacci(int n)
{
if (n == 0 || n == 1)
return n;
return Fibonacci(n-1) + Fibonacci(n-2);
}
int FibonacciSimple(int n)
{
int iIndex = 0;
int a1 = 0;
int a2 = 1;
int Result;
if (n == 0 || n == 1)
return n;
int *sArray = (int *)malloc(n);
for (iIndex = 2; iIndex <= n; iIndex++)
{
Result = a1 + a2;
a1 = a2;
a2 = Result; }
return Result;
}
int main()
{
printf("%d\n",Fibonacci(10));
printf("%d\n",FibonacciSimple(10));
getchar();
}

说明:方法一採用递归,效率较低。

方法二採用循环,先将结果存储起来。再利用已经得到的结果求解,效率得到大幅度提升。

面试题9(变形) 跳台阶,青蛙一次能够跳上1阶,能够跳上2阶,也能够跳到n阶。问跳到n阶总共同拥有多少种跳法?

 Fib(n) = Fib(n-1)+Fib(n-2)+Fib(n-3)+..........+Fib(n-n)

= Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-1)

      又由于Fib(n-1)=Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-2)

      两式相减得:Fib(n)-Fib(n-1)=Fib(n-1)         =====》  Fib(n) = 2*Fib(n-1)     n >= 2

归纳总结为 2^(n-1) 

面试题10 二进制中1的个数 。输入一个数,输出该数的二进制表示中,1的个数。

比如9表示为1001 共同拥有2个1

实现一:1挨个移位,挨个推断是否为1

#include <iostream>
int GetOneNum(int n)
{
int num = 0;
int i = 1;
for (i = 0;i<32;i++)
{
if (n&(1<<i))
{
num++;
} }
return num;
}
int main()
{
printf("%d\n",GetOneNum(9));
getchar();
}

实现二:仅仅推断1的个数

int GetOneNum(int n)
{
int num = 0;
while(n)
{
num++;
n= (n -1) & n;
}
return num;
}

05-11 19:35