在此将【剑指Offer】中的经典问题和重要内容整理出来,便于以后遇到类似的问题再次查阅。博主强烈为大家推荐这本书,因为这本书中的题目都来自真实的公司笔试,对于大家求职、找工作会有很大的帮助。

1、在定义一个赋值运算符时,通常需要考虑以下四点:

  • 是否将返回值的类型声明为该类型的引用,并在函数结束前返回实例自身的引用(即*this)。只有一个返回引用,才可以允许连续赋值,否则如果函数的返回值是void,应用该赋值运算符将不能做连续赋值。
  • 是否将传入的参数类型声明为常量引用。如果传入的参数不是引用而是实例,那么从形参到实参会调用一次复制构造函数,把参数声明为引用可以避免这样的无谓消耗,能提高代码的效率。同时,我们在赋值运算函数内部不会改变传入的实例状态,因此应该在传入的引用参数前加上const关键字。
  • 是否释放实例已有的内存,如果我们忘记在分配新内存之前释放自身已有的空间,恒旭将出现内存泄漏。
  • 是否判断传入的参数和当前的实例是否是同一个实例。如果是同一个,则不进行赋值运算,直接返回,如果事先不判断就进行赋值,那么在释放实例自身内存的时候就会导致严重的问题,当*this和传入的参数是同一个实例时,一旦释放了自身的内存,传入的参数的内存将同时被释放,因此将再也找不到需要赋值的内容了。

  当我们完整的考虑了上述四个方面以后,我们可以写出如下的代码:

1
2
3
4
5
6
7
8
9
10
11
CMyString& CMyString::operator = (const CMyString &str)
{
if(this==&str)
return;
delete []m_pData;
m_pData=NULL;
m_pData=new char[strlen(str.m_pData)+1];
strcpy(m_pData,str.m_pData);

return *this;
}

2、要想在赋值运算符函数中实现异常安全性,我们有两种方法

  • 方法一:先用new分配新内容再用delete释放已有内容。这样只有当分配内容成功后再释放原来的内容,换句话说当分配内存失败时我们可以确定CMyString的实例不会被修改。
  • 方法二:先创建一个临时实例,再交换临时实例和原来的实例

  下面给出第二种方法的实现代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
CMyString& CMyString::operator = (const CMyString &str)
{
if(this!=&str){

CMyString strTemp(str);

char* pTemp=strTemp.m_pData;
strTemp.m_pData=m_pData;
m_pData=pTemp;
}

return *this
}

3、对于C++和C#中的struct和class的认识

  • C++:在C++中如果没有标明成员函数或者成员变量的访问权限级别,则在struct中默认的是public,在class中的默认的private。
  • C#:在C#中如果没有标明成员函数或者成员变量的访问级别,则struct和class默认都是private,不同的是struct定义的是值类型,其实例在栈上分配内存;class定义的是引用类型,其实例在堆上分配内存。

4、在C#中实现单例模式

  • 原理:在C#语法中C#是在调用静态函数时初始化静态变量,.NET运行时可以保证只调用一次静态构造函数,这样我们就可以保证仅初始化一次Instance;
    下面给出代码示例:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    public sealed class Singleton
    {
    private Singleton()
    {

    }

    private static Singleton instance=new Singleton();
    public static Singleton Instance
    {
    get{ return instance;}
    }
    }

5、C++数组重要概念

  • 数组是最简单的一种数据结构,它占据一块连续的内存并按照顺序存储数据。
  • 在C/C++中,数组和指针是相互关联又有区别的两个概念。当我们声明一个数组时,其数组的名字同时是一个指针,该指针指向数组的第一个元素,因此我们可以使用一个指针来访问数组。可是值得注意的是,C/C++并没有记录数组的大小,因此使用指针访问数组中的元素时要注意不能超出数组的边界。
  • 使用sizeof计算指针的大小时,在32位操作系统中,对于任意指针结果都是4。
  • 二维数组在内存中占据连续的空间。在内存中从上到下存储各行元素,在同一行中按照从左到右的顺序存储。因此我们可以根据行号和列号计算出相对于数组首地址的偏移量,从而找到对应的元素。

6、C#中的String类型

  • 在C#中封装字符串的类型Sysytem.String有一个非常特殊的性质,即String中的内容是不能改变的。当尝试改变String中的内容,就会产生一个新的实例。
  • 如果要连续多次修改字符串内容,可以考虑使用StringBuilder。
  • 当我们需要在函数或者方法中返回一个String实例时,我们需要在传入的参数前加上ref或者out标记

7、链表

  • 链表是一种动态数据结构,因为在创建链表的时候,不需要知道链表的长度。当插入一个结点时,我们只需要为新结点分配内存,然后调整指针的指向来确保新结点被链接到链表当中。内存分配不是在创建链表时一次性完成,而是每添加一个结点分配一次内存。由于没有闲置的内存,因此链表的空间效率比数组要高。
  • 因为链表中的内存不是一次性分配的,所以我们不能确定链表的内存和数组一样是连续的,因此如果想在链表中找到第i个结点,我们只能从头结点开始,沿着指向下一个结点的指针遍历链表,其效率是O(n)。而在数组中,我们可以根据下标i直接找到第i个元素,其效率是O(1)。
  • 当我们需要从尾到头输出链表时,第一个遍历到的结点最后一个输出,而最后一个遍历到的结点第一个输出,这是典型的后进先出,因此我们可以考虑使用栈来实现这种顺序。下面是具体的代码实现:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    void PrintListReversingly_Iteratively(ListNode* pHead)
    {
    std::stack<ListNode*> nodes;

    ListNode* pNode=pHead;
    while(pNode!=NULL)
    {
    nodes.push(pNode);
    pNode=pNode->m_pNext;
    }

    while(!nodes.empty())
    {
    pNode=nodes.top();
    printf("%d\t",pNode->m_nValue);
    nodes.pop();
    }
    }

8、树

  • 除了根节点之外每个结点只有一个父结点,根节点没有父结点。
  • 除了叶节点以外所有结点都有一个或者多个子结点,叶结点没有子结点。父结点和子结点间用指针链接。
  • 二叉树是树的一类特殊结构,在二叉树的每个结点最多只能有两个子结点。二叉树有三种主要的遍历方式,即前序遍历(根、左、右)、中序遍历(左、根、右)、后序遍历(左、右、根)。
  • 二叉搜索树是二叉树的一个特例,其特点是左子节点总是小于或等于根节点,右子结点总是大于或等于根节点。

9、栈和队列

  • 栈的特点是后进先出,即最后一个被压入(Push)栈的元素会第一个被弹出(Pop)。
  • 队列的特点是先进先出,即第一个进入队列(入队)的元素将会第一个出来(出队)。

10、递归与循环

  • 递归实现的效率无法和循环相比,因此函数调用会造成时间和空间的损失、会造成重复计算、可能会造成栈溢出。
    在经典的斐波那契数列问题中,我们可以采用下面的方法来代替传统的递归方法:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    int Fiboncci(int n)
    {
    int[] result=new int[]{0,1};
    if(n<2)
    return result[n];

    int m=1;
    int n=0;
    int k=0;
    for(int i=2;i<=n;i++)
    {
    k=m+n;
    n=m;
    m=k;
    }

    return k;
    }

11、位运算

  • 左移m<<n表示把m左移n位。左移n位的时候,最左边的n位将被丢弃,同时在最右边补上n个0。如:

    00001010<<2=00101000
    10001010<<3=01010000

  • 右移m>>n表示把m右移n位。右移n位的时候,最右边的n位将被丢弃。此时如果数字是一个无符号数值,则用0填补最左边的n位;如果数字是一个正数,则在右移之后在左边补n个0;如果数字是一个负数,则右移之后在左边补n个1。如:

    00001010>>2=00000010
    10001010>>3=11110001