剑指offer

这本书很不错，在其中还发现了阿里面试的时候所问的问题。值得好好研究一下。

1.赋值运算符函数

题目：如下为类型CMyString的声明，请为该类型添加赋值运算符函数。
注意：1.是否把返回值的类型声明为该类型的引用，并在函数结束前返回实例自身的引用（返回引用才可以连续赋值）
2.是否把传入的参数类型声明为常量引用const。
3.是否释放实例自身已有的内存，防止内存泄露。
4.是都判断传入的参数和当前的实例(*this)是不是同一个实例。

#include <string>

class CMyString{
public:
    CMyString(char* pData=NULL);
    CMyString(const CMyString &str);
    ~CMyString(void);
    
    CMyString& operator=(const CMyString& str);
    void Print();

private:
    char* m_pData;
};

CMyString::CMyString(char *pData){
    if (pData==NULL) {
        m_pData=new char[1];
        m_pData[0]='\0';
    }else {
        int length=strlen(pData);
        m_pData=new char[length+1];
        strcpy(m_pData, pData);
    }
}
CMyString::CMyString(const CMyString& str){
    int length = strlen(str.m_pData);
    m_pData=new char[length+1];
    strcpy(m_pData,str.m_pData);
}

CMyString::~CMyString(){
    delete[] m_pData;
}
//赋值运算符函数
CMyString& CMyString::operator=(const CMyString& str){
    if (this==&str) return *this;
    delete []m_pData;
    m_pData=NULL;
    
    m_pData=new char[strlen(str.m_pData)+1];
    strcpy(m_pData, str.m_pData);
    return *this;
}
//测试代码，把一个类的实例赋值给另外一个实例
void CMyString::Print(){
    printf("%s",m_pData);
}
void Test1(){
    printf("Test1 begins:\n");
    char* text="Hello world";
    
    CMyString str1(text);
    CMyString str2;
    str2=str1;
    
    printf("the expected result is%s.\n",text);
    str2.Print();
    printf(".\n");
}
//赋值给自己
void Test2(){
    printf("Test2 begins:\n");
    char* text="hello world";
    CMyString str1(text);
    str1=str1;
    printf("the expected result is%s.\n",text);
    str1.Print();
    printf(".\n");
}
//连续赋值
void Text3(){
    printf("Test3 begins:\n");
    
    char* text ="Hello world";
    
    CMyString str1(text);
    CMyString str2,str3;
    str3=str2=str1;
    printf("the expected result is:%s.\n",text);
    str2.Print();
    printf(".\n");
    printf("the actual result is: ");
    str3.Print();
    printf(".\n");
}
int main(int argc,_TCHAR* argv[]){
    Test1();
    Test2();
    Text3();
    return 0;
}

2.实现Singleton模式

题目：设计一个类，只能生成该类的一个实例。
答案

1>在单线程的时候工作正常，但在多线程的情况下多个线程都会创建一个自己的实例，无法保证单例模式的要求。
//单例模式，懒汉式（在用的时候实例化），线程不安全

sealed class Singleton1{

    private Singleton1(){}
    private static Singleton1 Instance{
        get{
            if(instance==null)
                instance = new Singleton1();
                return instance;
        }
    }
};

2>虽然在多线程环境中能工作但效率不高
//懒汉式，线程安全

sealed class Singleton2{

    private Singleton2(){}
    private static readonly object synObj = new object();
    public static Singleton2 Instance{
        get{//每个线程来之前先等待锁
            lock(syncObj){
                if(instance==null)
                    instance = new Singleton1();
            }
            return instance;
        }
    }
};

保证了我们在多线程环境中也只能得到一个实例，但是加锁是一个非常耗时的操作，在没有必要的时候我们应该尽量避免。
3>可行的解法：加同步锁前后两次判断实例是否已存在

sealed class Singleton3{

    private Singleton3(){}
    
    private static object synObj = new object();
    private static Singleton3 instance=null;
    public static Singleton3 Instance{
        get{
            // Double-Check 双重判断避免不必要的加锁
            if(instance==null){// 确定实例为空时再等待加锁
                lock(syncObj){//确定加锁后实例仍然未创建
                    if (instance==null)
                        instance = new Singleton1();}
            }
            return instance;
        }
    }
};

4>强烈推荐：利用静态函数构造函数

sealed class Singleton4{

    private Singleton4(){}
    // 在大多数情况下，静态初始化是在.NET中实现Singleton的首选方法
    private static Singleton4 = new Singleton4();
    public static Singleton3 Instance{
        get{
            return instance;}
    }
};

5>强烈推荐：实现按需创建实例

sealed class Singleton5

{
    private Singleton5() { }
    public static Singleton5 Instance
    {
        get
        {
            return Nested.instance;
        }
    }
    // 使用内部类+静态构造函数实现延迟初始化
    class Nested
    {
        static Nested() { }
        internal static readonly Singleton5 instance = new Singleton5();
    }
}

答案
//饿汗模式(使用之前就创建了)

class A{

    private static A SingleInstance=new A();
    private A(){};
    public static A getInstance(){
        return SingleInstance();
    }
};

//懒汉模式(使用时候才创建)

class A{

    private static A SingleInstance=null;
    private A(){};
    public static A getInstance(){
        if (SinletonInstance==null) {
            lock(syncObj){
                    if (instance==null)
                    instance = new A();}
        }
        return SingletonInstance;
    }
};

3.二维数组中的查找

题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
输入：输入可能包含多个测试样例，对于每个测试案例，
输入的第一行为两个整数m和n(1<=m,n<=1000)：代表将要输入的矩阵的行数和列数。
输入的第二行包括一个整数t(1<=t<=1000000)：代表要查找的数字。
接下来的m行，每行有n个数，代表题目所给出的m行n列的矩阵(矩阵如题目描述所示，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
输出:
对应每个测试案例
输出”Yes”代表在二维数组中找到了数字t。
输出”No”代表在二维数组中没有找到数字t。
样例输入：
3 3
5
1 2 3
4 5 6
7 8 9
样例输出：
Yes
思路：首先选取数组中右上角的数字，如果该数字等于要查找的数字，查找过程结束；如果该数字大于要查找的数字，剔除这个数字所在的列；如果该数字小于要查找的数字，剔除这个数字所在的行。
代码：

#include <iostream>
#include <cstdio>
using namespace std;
string search(int a[][1000],int m,int n,int key){
    int i=0;
    int j= n-1;
    while (i<m && j>=0) {
        if (a[i][j]==key) return "Yes";
        else if (a[i][j]<key) i++;//i行往下移动
        else j--;//j列向左移动
    }
    return "NO";
}
int main(){
    int n,m;
    int a[1000][1000];
    while (scanf("%d%d",&m,&n)!=EOF) {
        int key;
        scanf("%d",&key);
        for (int i=0; i<m; i++)
            for (int j=0; j<n; j++)
                scanf("%d",&a[i][j]);
        cout << search(a, m, n, key) << endl;       
    }
}

4.替换空格

题目描述：
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

5.从尾到头打印链表

6.重建二叉树

7.用俩个栈实现队列

8.旋转数组的最小数字

9.斐波那契数列

10.二进制中1的个数

题目：请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如把9表示成二进制是1001，有两位是1.如果输入9，则输出2.
解法：为避免死循环，可以不右移输入的数字n。首先把n和1做与运算，判断n的最低位是不是1.接着把1左移一位得到2，再和n做与运算，

51.数组中重复的数字

题目：在一个长度为n的数组里的所有数字都在0到n-1范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复数字。
例如：如果输入长度为7的数组{2，3，1，0，2，5，3}。那么对应的输出是重复数字2或者3.

解法一：先把输入的数组排序，从排好序的数组中找出重复数字。O(nlogn)时间。
解法二：哈希表，从头到尾扫描数组中每个数，用O(1)时间来判断哈希表中是否包含了该数字，如果没有该数字，加入哈希表。如果有，就找到了重复的数字。时间复杂度：O(n).
解法三：所有数字都在0到n-1范围内，假设这个数组没有重复数字，那么数组排序之后数字i就会出现在下标为i的位置。但有重复数字，有些位置据肯存在多个数字，有些位置没有。
数组{2，3，1，0，2，5，3}，数组第0个数字是2与下标不等，把它和下标为2的1交换，交换后{1，3，2，0，2，5，3}，不等，再交换{3，1，2，0，2，5，3}，不等，再交换{0，1，2，3，2，5，3}。扫描到下标为4的数字2再比较它和下标为2的数字，发现相等，就找到了一个重复数字。时间复杂度：O(n).空间复杂度O(1)。
代码：

bool duplicate(int numbers[], int length, int* duplication) 
{     
    if(numbers == NULL || length <= 0)
    {
        return false;
    }
    
    for(int i = 0; i < length; ++i) 
    {         
        if(numbers[i] < 0 || numbers[i] > length - 1)             
            return false;     
    }  

    for(int i = 0; i < length; ++i) 
    {         
        while(numbers[i] != i) 
        {             
            if(numbers[i] == numbers[numbers[i]]) 
            {                 
                *duplication = numbers[i];             
                return true;
            }  

            // swap numbers[i] and numbers[numbers[i]]             
            int temp = numbers[i];             
            numbers[i] = numbers[temp];             
            numbers[temp] = temp;         
        }     
    }          
    
    return false;
}