本文主要是介绍【剑指Offer】鸟瞰50题之1-10题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
面试题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 1char *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;
}这篇关于【剑指Offer】鸟瞰50题之1-10题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
