剑指 Offer 读书笔记(1) | 素履独行

剑指 Offer 读书笔记(1)

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

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

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

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

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的实例不会被修改。
方法二：先创建一个临时实例，再交换临时实例和原来的实例

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

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; 下面给出代码示例：

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)。
当我们需要从尾到头输出链表时，第一个遍历到的结点最后一个输出，而最后一个遍历到的结点第一个输出，这是典型的后进先出，因此我们可以考虑使用栈来实现这种顺序。下面是具体的代码实现：

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、递归与循环

递归实现的效率无法和循环相比，因此函数调用会造成时间和空间的损失、会造成重复计算、可能会造成栈溢出。在经典的斐波那契数列问题中，我们可以采用下面的方法来代替传统的递归方法：

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