剑指offer第二章——c++实现 持续更新中

2.1面试官谈基础知识

1、c++的基础知识（面向对象的特性、构造函数、析构函数、动态绑定、内存管理）

2、设计模式

3、uml图

4、并发控制

5、对os的理解程度

时间复杂度排序：O(1) > O(lognN) > O(n) > O(NlogN) > O(N*N)

 

2.2 编程语言

c++三种考查方式：

1、考概念（重点考察c++关键字的理解程度。

例如，c++中，有哪四个与类型转换相关的关键字？这些关键字有什么特点，适合在什么场合下使用）

解答：http://www.cnblogs.com/mjiang2017/p/9358032.html   （先记这个，以后看书的时候发现更好的解答，就回来补充）

面试场景：

 

2、分析代码的运行结果

 

浅显分析：

A b = a;

这句会调用拷贝构造函数，因为赋值的时候，b还没被实例化。

拷贝构造函数参数必须是传引用的原因分析

如果拷贝构造函数是传值而不是传引用，当调用A b = a; 时，a作为参数传值给A(A other)，因为other没有被初始化，所以会继续调用拷贝构造函数，接下来是构造other，也就是A(A other)，必然又会有other传给A(A other)，那么又会触发拷贝构造函数，这样就无限递归下去了。

所以，拷贝构造函数的参数使用引用类型不是为了减少一次内存拷贝，而是避免拷贝构造函数无限制的递归下去。

下面这几种情况下会调用拷贝构造函数

（1）显式或隐式地用同类型的一个对象来初始化另外一个对象。如上例中的 A b = a;

（2）作为实参传递给一个函数。如上例中的bbb.myTestFunc(aaa);

（3）在函数体内返回一个对象时，也会调用返回值类型的拷贝构造函数

 

深度剖析

把参数传递给函数有三种方法，一种是值传递，一种是传地址，还有一种是传引用。前者与后两者不同的地方在于：当使用值传递的时候，会在函数里面生成传递参数的一个副本，这个副本的内容是按位从原始参数那里复制过来的，两者的内容是相同的。当原始参数是一个类的对象时，它也会产生一个对象的副本，不过在这里要注意。一般对象产生时都会触发构造函数的执行，但是在产生对象的副本时却不会这样，这时执行的是对象的拷贝构造函数。

为什么会这样？嗯，一般的构造函数都是会完成一些成员属性初始化的工作，在对象传递给某一函数之前，对象的一些属性可能已经被改变了，如果在产生对象副本的时候再执行对象的构造函数，那么这个对象的属性又再恢复到原始状态，这并不是我们想要的。所以在产生对象副本的时候，构造函数不会被执行，被执行的是一个默认的构造函数。

当函数执行完毕要返回的时候，对象副本会执行析构函数，如果你的析构函数是空的话，就不会发生什么问题，但一般的析构函数都是要完成一些清理工作，如释放指针所指向的内存空间。这时候问题就可能要出现了。

假如你在构造函数里面为一个指针变量分配了内存，在析构函数里面释放分配给这个指针所指向的内存空间，那么在把对象传递给函数至函数结束返回这一过程会发生什么事情呢？

首先有一个对象的副本产生了，这个副本也有一个指针，它和原始对象的指针是指向同块内存空间的。函数返回时，对象的析构函数被执行了，即释放了对象副本里面指针所指向的内存空间，但是这个内存空间对原始对象还是有用的啊，就程序本身而言，这是一个严重的错误。然而错误还没结束，当原始对象也被销毁的时候，析构函数再次执行，对同一块系统动态分配的内存空间释放两次是一个未知的操作，将会产生严重的错误。

上面说的就是我们会遇到的问题。解决问题的方法是什么呢？

首先我们想到的是不要以传值的方式来传递参数，我们可以用传地址或传引用。没错，这样的确可以避免上面的情况，而且在允许的情况下，传地址或传引用是最好的方法，但这并不适合所有的情况，有时我们不希望在函数里面的一些操作会影响到函数外部的变量。那要怎么办呢？可以利用拷贝构造函数来解决这一问题。拷贝构造函数就是在产生对象副本的时候执行的，我们可以定义自己的拷贝构造函数。在拷贝构造函数里面我们申请一个新的内存空间来保存构造函数里面的那个指针所指向的内容。这样在执行对象副本的析构函数时，释放的就是复制构造函数里面所申请的那个内存空间。（也就是自己写一个深拷贝的拷贝构造函数，系统默认生成的拷贝构造函数是浅拷贝的，容易发生内存泄漏）

在C++中，下面三种对象需要拷贝的情况。因此，拷贝构造函数将会被调用。 

1)． 一个对象以值传递的方式传入函数体 

2)． 一个对象以值传递的方式从函数返回 

3)． 一个对象需要通过另外一个对象进行初始化 

参考链接：

https://blog.csdn.net/xiaoquantouer/article/details/70145348    （比较浅）

https://my.oschina.net/N3verL4nd/blog/867052#comments        （更深入）

 

 

面试题一   考点：拷贝赋值函数的书写

 

拷贝赋值（赋值运算符）考点：

1、是否把返回值的类型声明为该类型的引用，并在函数结束前返回实例自身的引用（*this）。只有返回一个引用，才可以运行连续赋值。

2、是否把传入的参数类型声明为常量引用。如果传入的参数不是引用而是实例，那么从形参到实参会调用一次拷贝构造函数，把参数声明为引用可以避免这样的无谓消耗。

3、是否释放实例自身已有的内存（不释放会发生内存泄漏）

4、判断传入的参数和当前实例（*this）是否为同一个实例。如果是，则不进行复制操作，直接返回。

 

经典解法

#pragma once
#include <cstring>
class CMyString {
public:
	CMyString(char * pData = nullptr);
	CMyString(const CMyString& STR);
	CMyString& operator= (const CMyString& STR);
	~CMyString(void);
private:
	char * m_pData;
};

inline
CMyString& CMyString::operator=(const CMyString& str) {
	if (this == &str)
		return *this;

	delete[] m_pData;
	m_pData = new char[strlen(str.m_pData) + 1];
	strcpy(m_pData, str.m_pData);
	return *this;
}

缺点：如果内存不足导致new  char抛出异常，则m_pData将是一个空指针。

 

在拷贝构造函数中实现异常安全性的两种方法：

1、先用new分配内存，在delete原来的内容。

2、先创建一个临时实例，在交换临时实例和原来的实例。（推荐）

 

考虑异常安全性的解法

#pragma once
#include <cstring>
class CMyString {
public:
	CMyString(char * pData = nullptr);
	CMyString(const CMyString& STR);
	CMyString& operator= (const CMyString& STR);
	~CMyString(void);
private:
	char * m_pData;
};

inline
CMyString& CMyString::operator=(const CMyString& str) {
	if (this != &str) {
		CMyString strTemp(str);

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

 

个人扩展——既然复习了拷贝赋值函数，那就把构造函数、拷贝构造函数还有析构函数一起复习一下吧

#ifndef __MYSTRING__
#define __MYSTRING__

class String
{
public:                                 
   String(const char* cstr=0);                     
   String(const String& str);                    
   String& operator=(const String& str);         
   ~String();                                    
   char* get_c_str() const { return m_data; }
private:
   char* m_data;
};

#include <cstring>

//构造函数
inline
String::String(const char* cstr)
{
   if (cstr) {
      m_data = new char[strlen(cstr)+1];
      strcpy(m_data, cstr);
   }
   else {   
      m_data = new char[1];
      *m_data = '\0';
   }
}

//拷贝构造
inline
String::String(const String& str)
{
	m_data = new char[strlen(str.m_data) + 1];
	strcpy(m_data, str.m_data);
}

//拷贝赋值
inline
String& String::operator=(const String& str)
{
   if (this == &str)
      return *this;

   delete[] m_data;
   m_data = new char[ strlen(str.m_data) + 1 ];
   strcpy(m_data, str.m_data);
   return *this;
}

//析构函数
inline
String::~String()
{
	delete[] m_data;
}

#endif

 

面试场景

 

 

 

面试题二  考点：实现singleton模式

（书上用c#实现的题解，一年没用c#了，我用c++写一个）

 

饿汉模式——利用静态构造函数创建单例模式

#include<iostream>

class Singleton {
	Singleton() {
		std::cout << "Sigletion()" << std::endl;
	}
	//静态成员，指向Singleton对象的指针。
	static Singleton * intance; 

public:
	//提供静态共有方法，可以使用类名加域名进行访问，返回对象指针；
	static Singleton* GetSigletion()
	{
		return intance;
	}
};

int main()
{
	Singleton *ptr = Singleton::GetSigletion();
	system("pause");
	return 0;
}

 

懒汉模式——实现按需创建实例

#include<iostream>
using namespace std;

class Singleton {
	Singleton() {
		cout << "Sigletion2()" << endl;
	}
	static Singleton* intance2;
public:
	static Singleton* GetSigletion2() {
		if (intance2 == NULL) {
			intance2 = new Singleton();
			cout << "it is once" << endl;
		}else{
			cout << "it is not once" << endl;
		}
		return intance2;
	}
};

Singleton* Singleton::intance2 = NULL;  //先初始化为空，等真正用上这个单例的时候再创建这个例。

int main()
{
	
	Singleton *ptr = Singleton::GetSigletion2();
	system("pause");
	return 0;
}

 

扩展：懒汉模式、饿汉模式与线程安全

链接：https://blog.csdn.net/hj605635529/article/details/70172842

 

 

2.3 数据结构

2.3.1 数组

在c/c++中，当我们声明一个数组时，其数组的名字也是一个指针，该指针指向数组的第一个元素。用指针访问数组中的元素时，要小心不要超出数组的边界。

 

1、分析代码的运行结果

 

 

面试题三   数组中重复的数字

思路一：先排序，然后从前往后遍历查找   时间复杂度O(nlogn)

class Solution {
public:
    //手写快排
    void QuickSort(int a[], int l,int r){
        if (l >= r) return;
        int low = l, high=r;
        int key = a[low];
        while (low < high) {
            //从右往左找，如果该值小于key，则左移到low所指的位置
            for (;; high--) {
                if (high <= low) break;
                if (a[high] < key) {
                    a[low] = a[high];
                    break;
                }
            }
            //从左往右找，如果该值大于key，则右移到high所指的位置
            for (;; low++) {
                if (high <= low)break;
                if (a[low] > key) {
                    a[high] = a[low];
                    break;
                }
            }
        }
        //把key放在low和high重合的位置（即key应该在数组中的最终位置）
        if (low == high) a[low] = key;
        //分而治之
        QuickSort(a, l, low - 1);
        QuickSort(a, low+1, r);
    }

    //用duplication指向被找到的重复数字
    bool duplicate(int numbers[], int length, int* duplication) {
        QuickSort(numbers, 0, length );
        for(int i=0;i<length-1;i++){
            if(numbers[i]==numbers[i+1]){
                *duplication=numbers[i];
                return true;
            }
        }
        return false;
    }
};

每次只有看到这张图片，我才能心安啊，大哭

 

思路二    时间复杂度O(n)

从头到尾扫描数组，比较数字索引位置为 i 的值 m 是否等于 i ，如果不等，则将该值与索引位置为m的数组的值进行比较，如果不相等，则将索引位置为 i 的数组的值与索引位置为 m 的数组的值进行交换，如果相等，则说明 m 是一个重复的数字。

class Solution {
public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    bool duplicate(int numbers[], int length, int* duplication) {
        if((numbers==nullptr)||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++){
            if(numbers[i]!=i){
                if(numbers[numbers[i]]==numbers[i]){ 
                    * duplication=numbers[i];
                    return true;
                }
                 //交换
                int temp=numbers[i];
                numbers[i]=numbers[temp];
                numbers[temp]=temp;
            }
        }
        return false;
    }
};

 

 

题目变形——不修改数组找出重复数字

/*
题目：长度为n+1的数组里，所有的数字都在1~n之间，找出重复的数字
方法：把从1—n的数字，从中间值m分为两部分，前一半为1—m，后一半为m+1—n。
如果1—m区间中元素的个数超过m，则重复数字出现在该区间，
不断缩小范围即可查找到重复数字
*/
 
 
#include "stdafx.h"
#include<iostream>
using namespace std;
 
int search(int start,int end,int *array,int length) {
	
	if (array == nullptr || length <= 0) return -1;
 
	while (end >= start)
	{
		int middle = (start + end) / 2;
		int count = 0;
		for (int i = 0; i < length; i++) {
			if (array[i] >= start && array[i] <= middle) count++;
		}
		if (end == start) {
			if (count > 1) return start;
			else break;
		}
		if (count > (middle - start) + 1) end = middle;
		else   start = middle + 1;
	}
	return -1;
}
 
int main()
{
	int array[8] = { };
	int n = 7, m = 1;
	for (int i = 0; i < 8; i++) {
		//产生特定范围的随机数
		//m <= rand() % (n - m + 1) + m <= n
		array[i] = rand() % (n - m + 1) + m;
		cout << array[i] << endl;
	}
 
	//数组的长度要在调用函数之前获取，因为调用函数的时候，数组退化为指针
	int answer = search(1, 8, array, 8);
	cout <<"answer为"<< answer << endl;
	system("pause");
	return 0;
}

 

 

 

 

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

观察：二维数组四个角，左上角的数字最小，右下角的数字最大，右上角的数字是这一列里面最小的，这一行里面最大的，左下角的数字是这一列里面最大的，这一行里面最小的。因此，抓住右上角或者左下角数值的特性，就是本题解题的突破口。

#include <iostream>
#include<vector>
using namespace std;

bool Find(int target, vector<vector<int> > array) {
	if (array.empty()) return false;
	// array是二维数组，这里没做判空操作
	int rows = array.size();
	int cols = array[0].size();

	int i = 0, j = cols - 1;
	//防止数组越界，i的值等于rows时或者j的值小于0时，循环结束
	//如此不用担心数组越界，因为不合法的索引无法进入循环
	while (i < rows && j >= 0) {
		if (target < array[i][j]) {
			j--;
		}
		else if (target > array[i][j]) {
			i++;
		}
		else {
			return true;
		}
	}
	return false;
}

int main()
{
	vector<vector<int> >nums = { {1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
	int target = 7;
	bool answer = Find(target, nums);
	return 0;
}

 

 

2.3.2 字符串

预备知识

C/C++中，每个字符串都以“\0”作为结尾。

为了节省内存，C/C++常量字符串放在一个单独的区域。当几个指针赋值给相同的常量字符串时，他们实际上会指向相同的内存地址。

面试题：

运行结果：

 

 

面试题五 空格替换

思路：先遍历字符串，记录空格个数，从而计算出新字符串的长度。然后从后往前复制各个char。   时间复杂度 O(n)

注意：如果从前往后挪动，不仅挪的char的次数多，还容易发生内存覆盖。

class Solution {
public:
	void replaceSpace(char *str,int length) {
        if((str==nullptr)||(length==0)) return;
        //获取数组长度的方法，记录一下
        //int len=sizeof(str)/sizeof(char);
        int space_num=0;
        for(int i=0;i<length;i++){
            if(str[i]==' ') space_num++;
        }
        
        //新字符串的长度为原字符串的长度加上两倍的空格个数
        //两个长度都减一是为了防止数组越界
        int new_length=length+2*space_num-1;
        length-=1;
        
        //开始替换
        while(length>=0&&new_length>length){
            if(str[length]==' '){
                str[new_length--]='0';
                str[new_length--]='2';
                str[new_length--]='%';
            }else{
                str[new_length--]=str[length];
            }
            length--;
        }
	}
};

 

 

2.3.3 链表

链表结构体

struct ListNode {
	int val;
	ListNode * next = nullptr;
};

 

 

面试题六  从尾到头打印单链表

这种题就很简单了，实现的方式有很多，比如利用递归，利用栈，

递归实现代码：

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    void helper(vector<int>&answer, ListNode* head){
        if(head->next==nullptr) return;
        
        if(answer.empty()){
            head=head->next;
            helper(answer, head);
        }
        answer.push_back(head->val);
    }
    
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> answer;
        if(head==nullptr) return answer;
        
        helper(answer,head);
        
        //把链表头加入vector中
        answer.push_back(head->val);
        return answer;
    }
};

 

 

 

2.3.4 树

先来复习一下二叉树，来一个根据层序遍历的输出结果构建二叉树，然后分别按先序遍历、中序遍历和后序遍历打印二叉树。

#include <iostream>
#include<vector>
#include<queue>

struct TreeNode {
	int val;
	TreeNode * left;
	TreeNode * right;
	TreeNode(int x) 
		:val(x), left(nullptr), right(nullptr){}
};

//构建二叉树
TreeNode* CreatTree(std::vector<int>&num) {
	//判断边界条件
	int len = num.size();
	if (len == 0) return nullptr;

	//数据预处理(创建索引器，索引num中的值)
	int index = 0;
	//创建根节点
	TreeNode *root = new TreeNode(num[index]);
	TreeNode * temp = nullptr;
	//队列存储树的每个节点，分别为每个节点创建子节点
	std::queue<TreeNode*>trans;
	//根节点入队
	trans.push(root);

	//!trans.empty()，说明还有节点要被插入到二叉树中
	while (!trans.empty() && index < len) {
		temp = trans.front();
		trans.pop();
		//当前数组中的值非空
		if (index < len && num[index] != -1) {
			//构造节点
			TreeNode *LeftNode = new TreeNode(num[index]);
			//将构造出来的节点作为当前节点的左子树
			temp->left = LeftNode;
			trans.push(LeftNode);
		}
		index++;
		if (index < len && num[index] != -1) {
			TreeNode *RightNode = new TreeNode(num[index]);
			temp->right = RightNode;
			trans.push(RightNode);;
		}
		index++;
	}
	return root;
}


//前序遍历  根左右
void Preorder(TreeNode *root)
{
	//根为空，则跳出函数
	if (!root)
		return;
	//输出根的值
	std::cout << root->val << "  ";
	//递归获取左子树的值
	Preorder(root->left);
	//递归获取右子树的值
	Preorder(root->right);
}

//中序遍历  左根右
void Midorder(TreeNode *root)
{
	//根为空，则跳出函数
	if (!root)
		return;
	//递归获取左子树的值
	Midorder(root->left);
	std::cout << root->val << " ";
	Midorder(root->right);
}

//后序遍历  左右根
void Postorder(TreeNode *root)
{
	if (!root)
		return;
	Postorder(root->right);
	Postorder(root->left);
	std::cout << root->val << "  ";
}

int main()
{
	std::vector<int> num = 
	{ 3,5,1,6,2,0,8,-1,-1,7,4,-1,-1,-1,-1 };
	TreeNode* Tree = CreatTree(num);
	//前序遍历
	Preorder(Tree);
	//中序遍历
	Midorder(Tree);
	//后序遍历
	Postorder(Tree);
	return 0;
}

 

 

 

面试题七 重建二叉树

思路：用递归

先序遍历结果中，第一个节点为根节点，在中序遍历结果中找到该节点，则该节点左侧的各个节点即为左子树中的各个节点，相应的找到先序遍历中左子树的各个节点；

然后找到先序遍历中左子树的各个节点的第一个节点，即为左子树的根节点，在中序遍历中左子树节点的范围内找左子树的根节点，该节点左侧的即为左子树的左子树节点。以此类推。

写递归的时候，要注意先找好递归的终止条件是什么，边界条件是什么。

class Solution {
public:
    TreeNode* plantTree(vector<int> pre,vector<int> in){
        //递归的退出条件
        if(pre.size()==0||in.size()==0||pre.size()!=in.size())
            return NULL;
        TreeNode* root = new TreeNode(pre[0]);
        int index = 0;
        vector<int> left_pre,right_pre,left_in,right_in; 
        
        //找到中序遍历中，根节点的位置
        for(int i = 0;i<in.size();i++) {
            if(root->val==in[i])
                index=i;
        }
        
        //左子树的各个节点
        for(int i = 0;i<index;i++) {
            left_pre.push_back(pre[i+1]);
            left_in.push_back(in[i]);       
        }
        
        //右子树的各个节点
        for(int j = index+1;j<pre.size();j++) {
            right_pre.push_back(pre[j]);
            right_in.push_back(in[j]);
        }
        
        root->left = plantTree(left_pre,left_in);
        root->right = plantTree(right_pre,right_in);
        return root;
    }

    
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.empty()||vin.empty()) return nullptr;
        
        return plantTree(pre, vin);

    }
};

 

 

 

 

面试题八   二叉树的下一个节点

题目：给定一个二叉树和其中一个节点，如何找出中序遍历序列的下一个节点？树中节点除了分别指向左右子树的指针，还有一个指向父节点的指针。

如果当前考察的节点，如果该节点有右子树，则下一个节点是该节点右子树的最左子节点；如果该节点为其父节点的左子节点，则该节点的父节点为下一个节点；如果该节点的父节点没有左子节点，则其父节点的父节点

 

 

想起在百度的面试题，树的结构是只有指向左孩子的指针和兄弟节点的指针，找特定节点（都是换汤不换药，递归的去遍历而已）

 

未完待续。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

char转整数   -‘0’

整数转char要考虑正整数还是负整数

strcpy、strstr、strlen、sizeof