剑指Offer-一刷

DataStruct and Algorithm

1 赋值运算符函数

为类型CMyString的声明添加赋值运算符函数

Testing case

• 一个CMyString实例赋予另外一个实例
• 一个CMyString实例赋值给它自己
• 连续赋值

Key

• 考虑测试用例，是否传入参数是对象本身

  若传入参数为自身，则释放原有内存后将无法继续赋值，因为参数内存也被释放

• 考虑函数返回值是否为引用，并相应的返回引用

  引用作函数返回值使=运算符可连=

• 函数参数是否为常引用

  传入参数类型为引用将避免无谓的消耗，常引用则不希望影响原对象

  传值时会调用拷贝构造，降低效率

• 为已存在指针创建新的内存前是否释放原内存并置空

  若为释放原内存则会造成内存泄漏

  若释放后未置空，则导致野指针出现

Answer

经典解法

class CMyString {

public:
	CMyString(char* pData = nullptr);
	CMyString(const CMyString& str);
	~CMyString(void);
	//12
	CMyString& operator= (const CMyString& str) {

		//3
		if (&str == this) {
			return *this;
		}

		//4
		delete[]m_pData;
		m_pData = nullptr;

		//5
		char* m_pData = new char[strlen(str.m_pData) + 1];

		strcpy(m_pData, str.m_pData);
		//copy时包括终止符'\0'

		//6
		return *this;
	}

private:
	char* m_pData;
};

考虑异常安全性

//考虑异常安全性 -先new后delete
CMyString& operator= (const CMyString& str) {

	if (&str == this) {
		return *this;
	}

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

	return *this;
}


//考虑异常安全性 -临时对象交换
CMyString& operator= (const CMyString& str) {

	if (&str == this) {
		return *this;
	}
	
	CMyString temp(str);
    
	char* p = temp.m_pData;
	temp.m_pData = m_pData;
	m_pData = p;
    
	p = nullptr;
	return *this;
}

• 临时指针

  完成copy操作，这样即使new时内存不足导致异常也不会影响原m_pData状态，不至于为nullptr

• 临时对象

  该临时对象为传入对象的copy

  将该对象与原对象的成员进行交换，在跳出临时对象作用域时，其内存会被自动释放

  若不交换仍会导致内存泄漏，交换的目的就在于使用作用域机制，让系统自动释放内存

2.1 数组中重复的数字

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

Testing case

• 长度为n的数组里包含一个或多个重复数字
• 数组不包含重复的数字
• 无效输入(空指针;0~n-1范围之外的数字)

Key

• 数组可支持O(1)的随机访问，可使用该性质结合哈希表实现时间复杂度为O(n)，空间复杂度为O(n)的算法

  创建一个等大的数组，遍历原数组，从头开始将每一个元素模n，得到对应的索引位置(角标)

  若角标处无元素，则存入，若有元素则为重复数字

• 基于原数组，结合哈希表实现时间复杂度为O(n)，空间复杂度为O(1)的算法

  1. 从头遍历原数组，判断索引值与元素值是否相等

  2. 相等，则说明该元素位置正确

  3. 不相等，则将该元素置于其值对应的索引处，若对应索引处元素值与该元素相等，则重复，否则交换元素，重复1

  当遍历完原数组后，则无重复且元素排列有序(元素均位于”正确”的位置)或者找出重复

Answer

哈希表 T(n)=O(n) S(n)=O(n)

void repeat(int arr[], int n) {

	if (arr != nullptr) {
		int* temp = new int[n];

		//初始化哈希表值为-1，表示位置为空
     for (int i = 0; i < n; i++) {
			temp[i] = -1;
		}
		//遍历原数组
		for (int i = 0; i < n; i++) {
			if (arr[i] > n - 1 || arr[i] < 0) {
				cout << "存在无效数字" << arr[i] << endl;
				continue;
			}

			if (temp[arr[i] % n] == arr[i]) {
				cout << arr[i] << " ";
			}
			else {
				temp[arr[i] % n] = arr[i];
			}
		}
	}
}

归位法 T(n)=O(n) S(n)=O(1)

bool repeat(int arr[], int n) {

	bool re = false;

	if (arr == nullptr || n < 0) {
		return false;
	}

	for (int i = 0; i < n; i++) {
		if (arr[i] > n - 1 || arr[i] < 0)
		{
			return false;
		}
	}

	for (int i = 0; i < n; i++) {

		if (i != arr[i]) {
			if (arr[i] == arr[arr[i]]) {
				cout << arr[i] << " ";
				re = true;
			}
			else {
				int t = arr[i];
				arr[i] = arr[arr[i]];
				arr[arr[i]] = t;
			}
		}

	}

	return re;
}

2.2 数组中的重复数字

在一个长度为n+1的数组里的所有数字都在1~n的范围内,所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字,但不能修改输入的数组。例如,如果输入长度为8的数组(2, 3, 5, 4, 3, 2, 6,7,那么对应的输出是重复的数字2或者3

Testing case

• 长度为n的数组里包含一个重复数字
• 长度为n的数组里包含多个重复数字
• 无效输入(空指针;1~n范围之外的数字)

Key

• 哈希法 T(n)=O(n) S(n)=O(n)

  • 二分法 T(n)=O(nlogn) S(n)=O(1)

  在一个长度为n+1的数组里的所有数字都在1~n的范围内,所以数组中至少有一个数字是重复的。

  1. 将1n范围内的数字分两部分，1n/2 - n/2+1~n，若1-2/n中的数字出现个数大于n/2，则认为这个范围内的数字存在重复数字，否则另一部分存在重复
  2. 重复数字部分重复步骤1

  注意:

  1. 不更改原数组，原数组仅用于遍历判断范围内的数字出现的次数

  2. 若出现个数与范围n同，则不能保证没有重复数字，精度有些问题

  3. 仅能找出一个重复数字

Answer

void repeat(const int* arr, int n) {

	if (arr == nullptr || n < 0) {
		return;
	}

	for (int i = 0; i < n; i++) {
		if (arr[i] > n - 1 || arr[i] < 1)
		{
			return;
		}
	}
	//确定有重复数字的范围
	int low = 1;
	int high = n - 1;
	
	//在该范围内进行二分，缩小重复数字的范围
	while (low < high) {

		int mid = (high + 1) / 2;
		int nums = 0;

		//遍历数组判断指定范围内 (1 - mid) 的数字出现的次数
		for (int i = 0; i <= n; i++) {

			if (arr[i] <= mid && arr[i] >= 1) {
				nums++;
			}

		}

		//得到该数字范围的长度
		int count = mid - low + 1;

		//若数组中数字出现次数大于该数字范围的长度，说明该数字范围内存在重复数字
		if (nums > count) {
			high = mid;
		}
		else {
			low = mid + 1;
		}

	}

	cout << arr[high];
}

4 二维数组中的查找

在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

Testing case

• 二维数组中存在/不存在该整数

Key

• 选取右上角或者左下角开始作比较，每比较一次可缩减一次查找范围，直到找到或者不存在该整数

Answer

bool search(int* arr,int rows,int cols, int n) {
	
	//锁定右上角位置
	int row = 0;
	int col = cols - 1;

	//直到越界结束查找
	while (row < rows && col >= 0) {
		if (n > arr[row*cols + col]) {
			//剔除一行
			row++;
		}
		else if (n == arr[row*cols + col]) {
			return true;
		}
		else {
			//剔除一列
			col--;
		}
	}

	return false;
}

5.1 替换空格

请实现一个函数,把字符串中的每个空格替换成”%20”。例如,输入”We are happy.”,则输出 “We%20are%20happy.”

Testing case

• 字符串中含有空格(空格位于字符串前面，后面，中间)，含有连续空格
• 字符串无空格
• 输入无效字符(空字符串，空指针)

Key

• 注意字符串变长导致的内存覆盖

• 从前往后替换空格 T(n)=O(n2)

  前向遍历字符数组，只要含有空格就将空格之后的字符后移两位并替换空格

  缺点是每含一个空格就需要进行一次整体移位，含多次重复操作

• 从后往前替换空格 T(n)=O(n)

  反向遍历字符数组，设置两个指针，一个指向原字符串末尾，一个指向将所有空格替换后(增长后)的末尾

  1. 对于接受到的数组，遍历数组的同时记录空格数(每替换一个空格字符串长度加2)，进而定位两个指针的位置
  2. 循环开始，若p指向的元素不是空格，则将该元素转到q指向的位置，并前移1位
  3. 若p指向的元素是空格，则将q指向的位置使用%20替代空格，并p前移1位，q前移三位
  4. 直至p==q，循环终止，空格均替代完毕

Answer

void replace(char* arr) {
	if (arr == nullptr || strlen(arr) == 0) {
		return;
	}
	char* p = arr;

	//定位p指针位置并计数空格数，进而定位q指针位置
	int nums = 0;
	for (; *p != '\0'; p++) {
		if (*p == ' ') {
			nums++;
		}
	}

	char* q = p + nums * 2;

	while (p != q) {
		if (*p != ' ') {
			*q = *p;
			p--;
			q--;
		}
		else {
			
			p--;
			for (int i = 0; i < 3; i++){
				if (i == 0) {		
					*q = '0';
					q--;
				}
				else if (i == 1) {
					*q = '2';
					q--;
				}
				else {
					*q = '%';
					q--;
				}
			}
			
		}
	}
}

5.2 合并两个有序数组

有两个排序的数组A1和A2,内存在A1的末尾有足够多的空余空间容纳A2,请实现一个函数,把A2中的所有数字插入A1中,并且所有的数字是排序的。

Testing case

• 长度相等/不等的升序数组合并
• 无效数组输入

Key

• 从后往前合并有序数组 T(n)=O(n + m)

  反向遍历两个数组，并于A1数组设置三个指针，一个p1指向A1元素末尾，一个p2指向A2元素末尾，一个q指向A1数组合并后预留位置后的末尾

  1. 通过比较p1与p2指向的元素大小决定q指向的元素内容，合并元素后移动相应指针
  2. 直至有一个数组元素全部合并完毕后，将另一个数组未合并完成的数组元素按序填充至A1剩余空位处

Answer

>void combine(vector<int>& v1,const vector<int>&v2) {
	if (v1.size() == 0 && v2.size() == 0) {
		return;
	}

	//vector扩容后为重新申请了一块两倍大小内存，注意获取迭代器的时机
		v1.resize(v1.size() + v2.size());

	//定位迭代器指向
	auto p1 = v1.end() - 1 - v2.size();
	auto p2 = v2.end() - 1;
	auto q = p1 + v2.size();

	//合并数组
	while (q != v1.begin() && p1 >= v1.begin() && p2 >= v2.begin()) {
		if (*p1 >= *p2) {			
			*q = *p1;
			q--;
			if (p1 == v1.begin()) {
				break;
			}
			p1--;
		}
		else {	
			*q = *p2;
			q--;
			if (p2 == v2.begin()) {
				break;
			}
			p2--;
		}
	}

	//将剩余未合并元素有序合并
	if (p1 == v1.begin() && p2 != v2.begin()) {

		auto re = v2.begin();
		while (re <= p2) {
			*p1 = *re;
			re++;
			p1++;
		}

	}

}

6 从尾到头打印链表

输入一个链表的头节点,从尾到头反过来打印出每个节点的值。链表节点定义如下

struct ListNode {
    int m_nKey;
    ListNode* m_pNext;
}；

Testing case

• 输入的链表有多个结点
• 输入的链表只有一个结点
• 链表的头结点指针为nullptr

Key

• 正向遍历，压栈输出
• 正向遍历，递归输出

Answer

//压栈输出
void reprint(ListNode* head) {

	if (head == nullptr) {
		return;
	}

	ListNode* q = head->m_pNext;
	stack<int> st;
	while (q != nullptr) {	
		st.push(q->m_nKey);
		q = q->m_pNext;
	}

	while (!st.empty()) {
		cout << st.top() << " ";
		st.pop();
	}
}

//递归
void rreprint(ListNode* head) {

	if (head == nullptr) {
		return;
	}

	if (head->m_pNext != nullptr) {
		reprint(head->m_pNext);
	}
	cout << head->m_nKey << " ";
}

7 重建二叉树

输入某二又树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

Testing case

• 完全二叉树，非完全二叉树
• 特殊二叉树(无左子树，无右子树)
• 头结点为nullptr，两个遍历序列不匹配

Key

• 两者结合，相辅相成

  1. 前序遍历序列先出现的为根节点，可先于前序遍历序列中找到根节点

  2. 再于中序遍历序列中确定该根节点的左右子树，中序遍历序列中其左边结点属于左子树

  3. 递归再使用同样的方法在左子树中去前序遍历序列中找寻根节点，确定根节点后再回到中序遍历序列确定左右子树范围

Answer

BinaryTreeNode* constructBTreeCore(int* stp, int*sep, int*itp, int*iep) {
	//于先序遍历序列中找到根节点
	int rootValue = stp[0];
	//创建根节点
	BinaryTreeNode* root = new BinaryTreeNode();
	root->m_nValue = rootValue;
	root->m_pLeft = root->m_pRight = nullptr;

	//设置递归终止条件并判断异常
	if (stp == sep) {
		if (itp == iep && *stp == *itp) {
			return root;
		}
		else {
			throw std::exception();
		}
	}

	//创建左右子树
	int *Iroot = itp;
	while (Iroot != iep && *Iroot != rootValue) {
		Iroot++;
	}
	
	//异常处理
	if (Iroot == iep && *Iroot != rootValue) {
		throw std::exception();
	}

	//确定左右子树范围
	int leftlen = Iroot - itp;

	//构建左子树
	if (leftlen > 0) {
		root->m_pLeft = constructBTreeCore(stp + 1, stp + leftlen, itp, Iroot - 1);
	}
	//构建右子树 - 若仅有左子树则无需构建
	if (leftlen < iep - itp) {
		root->m_pRight = constructBTreeCore(stp + leftlen + 1, sep, Iroot + 1, iep);
	}

	return root;

}

8 二叉树的下一个结点

给定一棵二叉树和其中的一个节点,如何找出中序遍历序列的下一个节点?

树中的节点除了有两个分别指向左、右子节点的指针,还有一个指向父节点的指针

Testing case

• 普通二叉树(完全二叉树，不完全二叉树)
• 特殊二叉树(所有结点都没有右节点，所有结点都没有左子节点，只有一个结点，根节点为nullptr)
• 不同位置结点的下一个结点(下一个结点为当前结点的右子结点，右子结点的最左子节点，父结点，跨层的父结点等，或当前结点没有下一个结点)

Key

• 区分求结点下一结点的两种情况

  1. 该结点存在右子树，则该节点的下一个结点为右子树的最左结点
  2. 该节点不存在右子树，但是该节点存在父结点，则向上遍历，直至找到其及其上层子结点是其上层父结点的左子树，则该父结点为其下一个结点
  3. 该节点不存在右子树，且不存在父结点，则无下一个结点
  4. 该节点不存在右子树，存在父结点，但是不存在2的情况，则无下一个结点

Answer

BinaryTreeNode* GetNext(BinaryTreeNode* pNode)
{
	if (pNode == nullptr) {
		return nullptr;
	}

	BinaryTreeNode* pNext = nullptr;

	if (pNode->m_pRight != nullptr) {
		
		BinaryTreeNode* pCurrent = pNode->m_pRight;
		while (pCurrent->m_pLeft != nullptr) {
			pCurrent = pCurrent->m_pLeft;
		}
		pNext = pCurrent;
	}
	else if (pNode->m_pParent != nullptr) {
		
		BinaryTreeNode* pCurrent = pNode;
		BinaryTreeNode* pParent = pNode->m_pParent;

		while (pParent->m_pParent != nullptr && pCurrent == pParent->m_pRight) {
			pCurrent = pParent;
			pParent = pParent->m_pParent;
		}

		if (pCurrent == pParent->m_pLeft) {
			pNext = pParent;
		}
	}

	return pNext;

}

9 用两个栈实现队列

用两个栈实现一个队列,队列的声明如下,请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入节点和在队列头部删除节点的功能。

Testing case

• 往空的队列中添加，删除元素
• 往非空的队列中添加，删除元素
• 连续删除元素直至队列为空

Key

• 熟悉栈与队列的特性

  队列先进先出，栈后进先出

• appendTail队尾插入

  插入的元素均置于stack1中

• deleteHead队头删除

  删除结点时，为保证删除结点的顺序，因此需要

  1. 判断stack2是否为空，若不为空，则直接于stack2中弹出
  2. 若为空，则先将stack1中的元素全部弹出并插入到stack2中，再于stack2中弹出

Answer

template<typename T>
void CQueue<T>::appendTail(const T&node) {
	stack1.push(node);
}

template<typename T>
T CQueue<T>::deleteHead() {

	if (stack2.size() == 0) {

		while (stack1.size() != 0) {
			stack2.push(stack1.top());
			stack1.pop();
		}

	}

	if (stack2.size() == 0) {
		throw new exception("stack2 is empty!");
	}

	T head = stack2.top();
	stack2.pop();

	return head;
}

10 用两个队列实现栈

用两个队列实现一个栈,栈的声明如下,请实现它的两个函数appendTail和deleteHead的功能。

Testing case

• 往空的栈中添加，删除元素
• 往非空的栈中添加，删除元素
• 连续删除元素直至栈为空

Key

• 熟悉栈与队列的特性

  队列先进先出，栈后进先出

• appendTail 栈顶插入

  1. 若插入元素时两个队列均为空，则随意，指定为queue1
  2. 若插入元素时含不为空的队列，则插入到不为空的队列中去

• deleteHead 栈顶弹出

  删除结点时，为保证删除结点的顺序，因此需要

  1. 先将不为空的队列的元素除最后插入的元素以外全部弹出并压入到空的队里中去
  2. 将该队列最后插入元素于队列中弹出

Answer

template<typename T>
void CStack<T>::appendTail(const T&node) {
	if (queue1.size() == 0 && queue2.size() == 0) {
		queue1.push(node);
	}
	else if (queue1.size() != 0) {
		queue1.push(node);
	}
	else {
		queue2.push(node);
	}
}

template<typename T>
T CStack<T>::deleteHead() {

	if (queue2.size() == 0 && queue1.size() == 0) {
		throw new exception("queue is empty!");
	}
	else if (queue2.size() != 0) {
		while (queue2.size() != 1) {
			
			queue1.push(queue2.front());
			queue2.pop();
		}

		T head = queue2.front();
		queue2.pop();

		return head;
	}
	else {
		while (queue1.size() != 1) {

			queue2.push(queue1.front());
			queue1.pop();
		}

		T head = queue1.front();
		queue1.pop();

		return head;
	}
}

11 斐波那契数列

求斐波那契数列的第n项。写一个函数,输入n,求斐波那契(Fibonacci)数列的第n项。

Testing case

• 功能测试(3,5,10)
• 边界测试(0,1,2)
• 性能测试(40,50,100)

Key

• T(n) = O(2^n) S(n) = O(n)

  自上而下回溯递归，按条件形式递归

  缺陷:

  1. 每次递归需要存放函数返回地址，临时变量等，占用栈空间
  2. 每次递归调用时栈的弹出，压入需要耗费时间
  3. 每个进程的栈空间有限，可能存在栈溢出问题

• T(n) = O(n) S(n) = O(1)

  自下而上循环累加代替自上而下的回溯递归

Answer - T(n) = O(n)

long Fibonaci(int n) {
	if (n <= 0) {
		return 0;
	}
	else if (n <= 1) {
		return 1;
	}
	else {
		long one = 0;
		long two = 1;
		long FN = 0;

		for (int i = 2; i <= n; i++) {
			FN = one + two;
			one = two;
			two = FN;
		}

		return FN;
	}
}

11.1 青蛙跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

Testing case

• 功能测试(3,5,10)
• 边界测试(0,1,2)
• 性能测试(40,50,100)

Key

• 数学建模能力

  青蛙跳上一级台阶有一种跳法，青蛙跳上二级台阶有两种跳法，当N>2时，的跳法总数可经过分析得为f(n) = f(n-1)+f(n-2)

  分析:

  青蛙第一跳可以选择跳一级台阶也可以选择跳两级台阶，总跳法取决于含第一跳的剩余台阶的跳法

  • 若选择跳一级台阶，则剩下n-1个台阶共含有f(n-1)种跳法

  • 若选择跳二级台阶，则剩下n-2个台阶共含有f(n-2)种跳法

  因此f(n) = f(n-1) + f(n-2)

Answer

long Fibonaci_F(int n) {
	if (n <= 0) {
		return 0;
	}
	else if (n <= 1) {
		return 1;
	}
	else if (n <= 2) {
		return 2;
	}
	else {
		long one = 1;
		long two = 2;
		long FN = 0;

		for (int i = 2; i < n; i++) {
			FN = one + two;
			one = two;
			two = FN;
		}

		return FN;
	}
}

11.2 青蛙变态跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶，也可以一次跳上n级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

Testing case

• 功能测试(3,5,10)
• 边界测试(0,1,2)
• 性能测试(40,50,100)

Key

• 数学建模能力

  1. 青蛙跳上最后一级台阶的跳法有，从n-1层台阶跳一级，或者从n-2级台阶跳二级…从1级台阶跳n级，所以f(n) = f(n-1) + f(n-2)+ … + f(1)

  2. 青蛙跳上n-1级台阶的跳法有 f(n-1) = f(n-2) + … + f(1)

  3. 所以f(n) = 2f(n-1) = 4f(n-2) = 2^(n-1) * f(1) = 2^(n-1)

—- 快速排序算法 —-

Testing case

• 功能测试
• 边界测试(nullptr)
• 性能测试

Key

• 随机基数分治法

  随机选择数组中的一个元素作为基数pivot，将比基数小的元素移动到基数左边，比基数大的元素移动到基数右边，递归对基数左右的元素再进行基数分治，直至范围长度为1

• 随机基数分治法 - 双指针交替

  使用left,right指针与index指针三个指针实现

  left: 时刻应指向比基数小的元素

  right:时刻应指向不比基数小的元素

  index:指向基数应存放的位置，在该位置未被赋予key值前，该位置均认为为空，原元素可被覆盖，暂存left或者right不应指向的元素

  1. 从左开始，left指针指向的元素与基数比较，若比基数小，left指针后移，否则，将该元素赋值到index处，并将index设置到left当前指向
  2. 从right开始交替判断，若right指向的元素不比基数小，right指针前移，否则，将该元素赋值到index处，并将index设置到right当前指向
  3. 1,2往复交替，直至left==right，该位置为key值应存位置

• 随机基数分治法 - 单指针交换

  使用small指针单指针实现

  small:small时刻指向当前最后一个比基数小的元素

  1. 随机获取关键字索引，并于数组末暂存key，对key前元素进行排序
  2. 遍历数组，若元素比基数小，small++，使small指向比基数小的元素，否则，small不自增，继续向下遍历数组
  3. 直至再次遇到比基数小的元素，small自增，将该元素与small当前指向元素进行交换
  4. 重复3，直至遍历完数组，数组当前状态为small指向最后一个比基数小的元素，基数存放于数组末
  5. 将基数归位，与(++small)位置处的比基数大的元素进行交换

Answer

1

//普遍方法
int Position(int *arr, int len, int start, int end) {
	if (arr == nullptr || len <= 0 || start < 0 || end >= len) {
		throw new exception("数组异常");
	}
	//随机获取关键字索引
 //index必须使用范围内随机数或者首尾，不能使用常数，因为每次递归常量index可能会导致越界
	int index = start;
	int key = arr[index];

	while (start < end) {
		while (start < end &&arr[start] < key) {
			start++;
		}
		//移动元素时必须每次判断是否满足循环条件，否则将导致越界访问
		if (arr[start] >= key) {
			arr[index] = arr[start];
			index = start;
		}
		//移动元素时必须每次判断是否满足循环条件，否则将导致越界访问
		while (start < end &&arr[end] >= key) {
			end--;
		}

		if (arr[end] < arr[index]) {
			arr[index] = arr[end];
			index = end;
		}
	}

	arr[index] = key;
	return index;

}

void QuickSort(int *arr, int len, int start, int end)
{
	if (start >= end) {
		return;
	}
	//获取关键字位置
	int index = Position(arr, len, start, end);
	//递归快排index左边的数据
	if (index > start)
		QuickSort(arr, len, start, index - 1);
	//递归快排index右边的数据
	if (index < end)
		QuickSort(arr, len, index + 1, end);
}

2

int Partition(int data[], int length, int start, int end)
{
	if (data == NULL || length <= 0 || start < 0 || end >= length)
	{
		cout << "error1!" << endl;
		exit(0);
	}

	int index = RandomInRange(start, end);
	//在数组末尾暂存基数，对基数前面的数据进行移动
	swap_element(&data[index], &data[end]);

	//设置small指针，时刻指向当前最后一个比基数小的元素
	int small = start - 1;

	//遍历数组，移动small指针，最终使small指向当前最后一个比基数小的元素
	for (index = start; index < end; index++) {
		if (data[index] < data[end]) {
			small++;
			if (small != index) {
				swap_element(&data[index], &data[small]);
			}
		}
	}
	//移动small指针，使其指向基数应在的位置，但是当前存放着比基数大的元素
	small++;
	//将末尾暂存的基数归位
	swap_element(&data[end], &data[small]);
	return small;
}
void Quicksort(int data[], int length, int start, int end)
{
	if (start == end)
	{
		return;
	}
	int index = Partition(data, length, start, end);
	if (index > start)
		Quicksort(data, length, start, index - 1);
	if (index < end)
		Quicksort(data, length, index + 1, end);
}
int RandomInRange(int start, int end)
{
	if (end > start)
	{
		srand(time(NULL));//srand函数是随机数发生器的初始化函数,使得随机数种子随时间的变化而变化
		return start + rand() % ((end - start));//产生start~end之间的随机数
	}
	return 0;
}
void swap_element(int *a, int *b)
{
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}

12 旋转数组最小数字

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。

输入一个递增有序数组的一个旋转,输出旋转数组的最小元素。例如,数组(3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1

Testing case

• 功能测试(输入的数组是升序数组的一个旋转，有重复数字或无重复数字)
• 边界测试(仅含有一个元素的数组)
• 性能测试(nullptr)

Key

• 二分思维(缩小查找范围)

  将整个旋转数组看做两个递增序列，且第一个递增序列的值始终大于等于第二个递增序列的值，且最小的元素位于两个递增序列的边界

  1. 设置两个指针分别指向整个序列的首尾，选取两指针范围内的元素与两端进行比较，判断该元素位于哪一个递增序列中
  2. 若该元素位于左边递增序列中，则移动left指针至该元素处，否则，移动right指针至该元素处
  3. 直至left与right相差1，此时right指向最小的元素

  注意:

  1. 2中若左右两端元素相等且中间元素值也与端值相等，则无法判断该元素位于哪一个序列，需要顺序查找

     10111 - 11101 无法判断1位于哪一个递增序列中

  2. 若旋转数组旋转尺度为0，则不存在两个序列，直接返回首元素即可

Answer

int getMin(int *arr, int length) {
	//异常处理
	if (arr == nullptr || length <= 0) {
		throw new exception("数组异常！");
	}

	//指针初始化
	int left = 0;
	int right = length - 1;
	//考虑到旋转数组旋转尺度为0时，即整个数组递增有序时的情况，返回首元素
	int mid = left;
	/*int mid = left;*/
	
	while (arr[left] >= arr[right]) {
		if (right - left == 1) {
			mid = right;
			break;
		}

		//取范围内的一个数
		mid = (left + right) / 2;
		if (arr[left] == arr[right] && arr[mid] == arr[left]) {
			//指定范围内顺序查找
			_getMin(arr, left, right);
		}

		if (arr[mid] >= arr[left]) {
			left = mid;
		}
		else if (arr[mid] <= arr[right]) {
			right = mid;
		}

	}
	return arr[mid];
}

int _getMin(int *arr, int left, int right) {
	int min = arr[left];
	for (int i = left + 1; i <= right; i++) {
		if (arr[i] <= min) {
			min = arr[i];
		}
	}
	return min;
}

—- Exhaustive Search 穷举搜索 —-

Pattern - 决策树下的递归

void explore(options, soFar)
{
    if (no more decisions to make) {
        // base case
    } else {
        // recursive case, we have a decision to make
        for (each available option) {
            choose (update options/sofar)
            explore (recur on updated options/sofar)
            [backtracking (undo changes to options/sofar)] //chooseable
        }
    }
}

• base case 递归终止条件
• make decisions 作决策
• explore -递归处理该决策下的决策
• backtracking 决策失败后的回溯

13 矩阵中的路径

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始,每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格,那么该路径不能再次进入该格子。例如,在下面的3x4的矩阵中包含一条字符串”bfce”的路径(路径中的字母用下画线标出)。但矩阵中不包含字符串”abtb”的路径,因为字符串的第一个字符b占据了矩阵中的第一行第三个格子之后,路径不能再次进入这个格子。

Testing case

• 功能测试(多行多列的矩阵中存在/不存在路径)
• 边界测试(矩阵只有一行/一列，矩阵中所有字符相同)
• 性能测试(nullptr)

Key

• 递归回溯-穷举法

  1. 对于给定的矩阵进行遍历，与给定字符串中的元素进行匹配

  2. 每匹配到一个元素，便对其相邻元素进行递归查找，若相邻元素无匹配项，则回溯到上一个元素

     注意:由于每个格子仅能访问一次，因此需要为每个格子设置访问标识

• 递归模式

  1. base case 递归终止的条件
  2. 对匹配元素的四周递归搜索
  3. 若四周无匹配元素，回溯回退到上一格

Answer

bool hasPath(char* arr, int cols, int rows, string str) {
	//异常处理
	if (arr == nullptr || cols < 1 || rows < 1 || str.empty()) {
		throw new exception("异常!");
	}

	//设置访问标识数组
	bool* visited = new bool[cols*rows];
	//初始化
	memset(visited, 0, cols*rows);
	//设置路径状态变量，用于标识路径搜索状态，str中字符匹配位置状态
	int pathLength = 0;

	//遍历矩阵每一个元素进行路径搜索
	for (int col = 0; col < cols; col++) {
		for (int row = 0; row < rows; row++) {
			if (hasPathCore(arr, cols, col, rows, row, pathLength, str, visited)) {
				return true;
			}
		}
	}

	delete []visited;
	return false;
	
}

bool hasPathCore(char* arr, int cols, int col, int rows, int row, int& pathLength,string str, bool*&visited) {
	//base case
	if (str[pathLength] == '\0') {
		return true;
	}
	
	//设置返回值
	bool hasPath = false;
	if (col >= 0 && col < cols&&row>=0 && row < rows&&arr[row*cols + col] == str[pathLength] && visited[row*cols + col] != true) {
		//找到匹配路径元素，查找下一个匹配的路径元素
		pathLength++;
		//设置访问状态
		visited[row*cols + col] == true;
		
		//查找该元素的相邻元素
		if (hasPathCore(arr, cols, col + 1, rows, row, pathLength, str, visited)
			|| hasPathCore(arr, cols, col, rows, row + 1, pathLength, str, visited)
			|| hasPathCore(arr, cols, col - 1, rows, row, pathLength, str, visited)
			|| hasPathCore(arr, cols, col, rows, row - 1, pathLength, str, visited)) {
			hasPath = true;
		}

		//若未找到下一个匹配元素，需要回溯到上一个元素
		if (!hasPath) {
			pathLength--;
			visited[row*cols + col] == false;
		}
	}

	return hasPath;
}

14 机器人的运动范围

地上有一个m行n列的方格。一个机器人从坐标(0, 0)的格子开始移动,它每次可以向左、右、上、下移动一格,但不能进入行坐标和列坐标的数位之和大于k的格子。

例如,当k为18时,机器人能够进入方格(35, 37),因为3+5+3+7-18,但它不能进入方格(35, 38),因为3+5+3+8-19,请问该机器人能够到达多少个格子?

Testing case

• 功能测试(矩阵为多行多列，k为正数)
• 边界测试(矩阵为一行一列，k为0)
• 性能测试(k为负数)

Key

• 递归

  1. 从矩阵左上角首元素开始，若元素所在行列不满足阈值条件，则直接返回0，表示从该元素开始的运动范围为0
  2. 若满足阈值条件，则从该元素位置开始计数，并对其四周进行递归计数，最终将该计数总和返回即可得到可抵达的所有范围

Answer

bool isOK(int cols, int rows, int k) {
	int sum = 0;
	while (cols != 0) {
		sum += cols % 10;
		cols /= 10;
	}

	while (rows != 0) {
		sum += rows % 10;
		rows /= 10;
	}

	if (sum > k) {
		return false;
	}
	else {
		return true;
	}
}

int getNum(int* arr, int rows, int cols, int k) {
	//异常处理
	if (arr == nullptr || cols < 1 || rows < 1 || k < 0) {
		throw new exception("异常!");
	}

	//设置访问标识数组
	bool* visited = new bool[cols*rows];
	//初始化
	memset(visited, 0, cols*rows);
	//设置出发点
	int col = 0;
	int row = 0;

	int num = getNumCore(arr, row, rows, col, cols, k, visited);

	//回收内存
	delete[] visited;
	return num;

}

int getNumCore(int* arr,int row, int rows,int col, int cols, int k, bool*visited) {
	//base case
	if (!isOK(cols, rows, k)) {
		return 0;
	}
	else {

		int num = 0;
		if (!visited[row*cols + col]) {
			num++;
			visited[row*cols + col] = true;

			num += getNumCore(arr, row - 1, rows, col, cols, k, visited);
			num += getNumCore(arr, row + 1, rows, col, cols, k, visited);
			num += getNumCore(arr, row, rows, col - 1, cols, k, visited);
			num += getNumCore(arr, row, rows, col + 1, cols, k, visited);

		}

		return num;
	}
}

15 剪绳子

给你一根长度为n的绳子,请把绳子剪成m段(m、n都是整数,n1并且m>1),每段绳子的长度记为A[0].A[1]..A[m]

请问k[0]×…×k[m]可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2,3,3的三段,此时得到的最大乘积是18

Testing case

• 功能测试(初始长度大于5)
• 边界测试(边界值1,2,3,4)

Key

• 动态规划 T(n)=O(n2) S(n)=O(n)

  自下而上的迭代计算代替自顶向下的递归计算，减少重复计算

  1. 自顶向下分析可得，剪得的最后一次的绳子段长度可能为 1,2…n-1，共n-1种可能将0绳子分为两部分，所以最大乘积 f(n)=max{f(i)*f(n-i)}，最大乘积为最后两部分相应乘积最大值的乘积，max{f(i)*f(n-i)} =>max{f(i)} × max{f(n-i)} ,而max{f(i)}仍可拆解为两段分析
  2. 自下向上迭代计算剩余长度为0,1…n的部分的最大乘积，并使用数组顺序存放每部分的最大乘积值

• 贪心算法 T(n)=O(1) S(n)=O(1)

  当n>=5时，剪得的绳子段长度为3的数目越多越好，其中两段长度分别为3和1的需要用两段长度为2和2的绳子段代替，因为3×1 < 2×2

  1. 计算绳子最多可容纳的长度为3的绳子段的个数
  2. 计算是否存在长度为1的绳子段，若存在，则有一段长度为3的绳子段不可用，需用长度为2的代替
  3. 计算剩余长度可容纳的长度为2的绳子段的个数
  4. 返回乘积结果

Answer

1

int getMax(int length) {
	//对输入长度作初始判断
	if (length < 2) {
		//没办法砍
		return 0;
	}
	if (length == 2) {
		//只能砍一刀
		return 1;
	}
	if (length == 3) {
		return 3;
	}

	//使用数组暂存自下向上的各长度的最大乘积值
	int* temp = new int[length + 1];
	for (int i = 0; i < 4; i++) {
		temp[i] = i;
	}

	//设置记录长度为n时的乘积max变量
	int max = 0;

	//计算其余长度的最大乘积值
	for (int i = 4; i <= length; i++) {
		max = 0;
		//使用已记录的值迭代进行计算，防止重复计算乘积值，设置终止条件为i/2
		for (int j = 1; j <= i / 2; j++) {
			max = temp[j] * temp[i - j];
			if (max >= temp[i]) {
				temp[i] = max;
			}
		}
	}

	max = temp[length];

	//防止内存泄漏
	delete[] temp;
	return max;

}

2

int getMaxx(int length) {
	//对输入长度作初始判断
	if (length < 2) {
		//没办法砍
		return 0;
	}
	if (length == 2) {
		//只能砍一刀
		return 1;
	}
	if (length == 3) {
		return 3;
	}

	//记录绳子可剪为长度为3的绳子段的个数与长度为2的绳子段的个数
	int threeTimes = length / 3;
	int twoTimes = 0;
	//记录是否存在裁剪为3*1的情况，需使用2*2替代
	if (length - 3 * threeTimes == 1) {
		threeTimes -= 1;
	}
	
	twoTimes = (length - 3 * threeTimes) / 2;
	return pow(2, twoTimes) * pow(3, threeTimes);
}

16 二进制中1的个数

请实现一个函数,输入一个整数,输出该数二进制表示中1的个数。

例如,把9表示成二进制是1001,有2位是1。因此,如果输入9,则该函数输出2

Testing case

• 正数(边界值 1,0x7fffffff)
• 负数(0x80000000,0xffffffff)
• 0

Key

• 右移整数

  从低位开始判断是否为1，为1则右移一位继续判断次低位，直至整数为0

  判断是否为1可与1作&运算

  注意:若输入负数将引起死循环，负数右移左补1，不会使原数至0

• 左移标志数

  从低位开始判断是否为1，为1则标志数左移一位继续判断整数的次低位，直至标志数为0

  判断次低位是否为1可与10作&运算，次次低位…

  操作次数与整数二进制位数相同

• 消除二进制中的所有1

  只要整数不为0，则其二进制中必含1，从低位开始将整数二进制中的1置为0，直至整数为0时的置0操作次数即为0的个数

  将整数减去1后与自身作与运算即可消去低位的1

  操作次数与整数二进制中1的个数相同

Answer

1

int getNOne1(int n){
	int nums = 0;
	while (n) {
		if (n & 1) {
			nums++;
		}
		n >>= 1;
	}
	return nums;
}

2

int getNOne2(int n){
	int nums = 0;
	unsigned int flag = 1;
	while (flag) {
		if (n & flag) {
			nums++;
		}
		flag <<= 1;
	}
	return nums;
}

3

int getNOne3(int n){
	int nums = 0;
	while (n) {
		nums++;
		n = (n - 1)&n;
	}
	return nums;
}

17 数值的整数次方

实现函数double Power(double base, int exponent),求base的exponent次方。

不得使用库函数,同时不需要考虑大数问题。

Testing case

• 功能测试(正数负数的任意整数次幂)
• 边界测试(0的负数次幂)

Key

• 考虑边界值的处理

• 考虑指数为负数时的倒数处理

• 考虑错误处理的方式 - 返回值，全局变量，异常

  	方式	优缺点
  返回值	返回0表示调用成功，否则调用失败	与系统API一致但是执行结果不便于操作
  全局变量	通过全局变量的值的情况反应函数是否调用成功	便于操作计算结果但是容易忘记处理失败调用
  异常	通过抛出异常的类型对不同类型的异常作不同的处理	方便处理异常但是有性能开销，有的语言不支持异常

• 累乘法

  累乘的次数与指数的大小相同

• 递归法

  1. 若指数为偶数，则|index|整数次方可以由 |index/2| 的乘积得出
  2. 若指数为奇数，则|index|整数次方可以由 |index/2| 的乘积 × n 得出
  3. 由此可递归计算n的|index|整数次幂

  注意:

  1. 使用右移一位操作代替除以2
  2. 使用&0x1操作代替%2，可提高性能执行效率

Answer

1.

//设置用于检查调用是否成功的全局变量
bool failed = false;

double getPow(double n, int index) {
	//考虑n为0时index为负数的情况，无法求倒数
	if (n == 0.0&index < 0) {
		failed = true;
		return 0;
	}
	//无论指数正负，先求指数求绝对值后的次方结果
	unsigned int absIndex;

	if (index < 0) {
		absIndex = -index;
	}
	else {
		absIndex = index;
	}

	double result = getAbsPow(n, absIndex);
	//对指数为负数的情况求倒数
	if (index < 0) {
		result = 1.0 / result;
	}

	return result;
}

double getAbsPow(double n, unsigned int absIndex) {
	double sum = 1.0;
	for (int i = 1.0; i <= absIndex; i++) {
		sum *= n;
	}
	return sum;
}

2.

double getAbsPow2(double n, unsigned int absIndex) {
	
	//basecase
	if (absIndex == 0) {
		return 1;
	}
	else if (absIndex == 1) {
		return n;
	}
	else {
		double pow = getAbsPow2(n, absIndex >> 1);
		pow *= pow;
		if (absIndex & 0x1 == 1) {
			pow *= n;
		}

		return pow;
	}
}

18 打印从1到最大的n位数

输入数字n,按顺序打印出从1到最大的n位十进制数。

比如输入3,则打印出1,2,3一直到最大的3位数999

Testing case

• 功能测试(1,2,3)
• 边界测试(0,-1)

Key

• 大数问题

  当n过大，无论是int还是long长整型均会溢出，因此无法预先算出max(n)后顺序输出

• 字符串模拟

  使用字符串来存放数字并模拟数字加法，最终将字符串表达的数字输出

  1. 设置字符串的长度为n+1,使用’\0’初始化而非0，并将末尾值为空操作符
  2. 在字符串上模拟对数字的加法，设置进位标志，先取出对应位上的数字(-‘\0’)，进行加法运算后覆盖置回
  3. 输出数字时从字符串第一个非零的数字字符开始输出
  4. 若进位产生于字符串第一个位置，则已到达最大数位，不再输出

• 全排列递归

  将1到最大n位数的所有数当做0-9的全排列问题

  1. 从首位开始递归排列直至到达最后一位进行回溯顺序输出

• Bitmap算法

  使用bit作存储单元，使用更贴合计算机底层的运算，性能与内存使用效率都很高

  bitmap中0表示无意义，1表示存放了索引对应的数据

Answer

1.

void printNum(int n) {
	//异常处理
	if (n <= 0) {
		xfailed = true;
		return;
	}

	//考虑大数问题，设置字符串或者数组来存放数字(此处选择字符串)
	char* str = new char[n + 1];
	memset(str, '0', n);
	str[n] = '\0';

	while (!increment(str)) {
		printNumCore(str);
	}

	//防止内存泄漏
	delete[] str;
}
//对字符串模拟加1
bool increment(char* str){
	//记录字符串长度
	int len = strlen(str);
	//设置进位值
	int carry = 0;
	//设置返回值判断是否至最大数进位
	bool arrive = false;


	for (int i = len - 1; i >= 0; i--) {
		//设置模拟加法的临时数字变量
		int num = str[i] - '0' + carry;
		//若为个位，则直接进行加1即可
		if (i == len - 1) {
			num++;
		}

		if (num >= 10) {
			if (i == 0) {
				arrive = true;
			}
			else {
				//设置进位后，将本位设置为0后写回
				num -= 10;
				str[i] = num + '0';
				carry = 1;
			}
		}
		else {
			//直接写回
			str[i] = num + '0';
			//break作用为:所有的直接加一运算仅作用于个位，其余位的加1运算均来自carry的进位
			break;
		}
	}

	return arrive;
}

void printNumCore(char* str) {
	//设置判断是否为第一个非零数的变量
	bool first = false;
	int len = strlen(str);
	for (int i = 0; i <= len; i++) {

		if (!first&&str[i] != '0') {
			first = true;
		}
		if (first)
			cout << str[i];
	}
	cout << " ";
}

2.

void printNum2(int n) {
	//异常处理
	if (n <= 0) {
		xxfailed = true;
		return;
	}

	//考虑大数问题，设置字符串或者数组来存放数字(此处选择字符串)
	char* str = new char[n + 1];
	memset(str, '0', n);
	str[n] = '\0';

	//从第一位开始递归排列
	for (int i = 0; i < 10; i++) {
		str[0] = i + '0';
		permutation(str, n, 0);
	}

	//防止内存泄漏
	delete[] str;
}

void permutation(char* str, int length, int index) {
	
	//base case
	if (index == length - 1) {
		printNumCore2(str);
		return;
	}

	for (int i = 0; i < 10; i++) {
		str[index + 1] = i + '0';
		permutation(str, length, index + 1);
	}
}

void printNumCore2(char* str) {
	//设置判断是否为第一个非零数的变量
	bool first = false;
	int len = strlen(str);
	for (int i = 0; i <= len; i++) {

		if (!first&&str[i] != '0') {
			first = true;
		}
		if (first)
			cout << str[i];
	}
	cout << " ";
}

19.1 删除链表的结点

在0(1)时间内删除链表节点

给定单向链表的头指针和一个节点指针,定义一个函数在O(1)时间内删除该节点

假设待删除的结点位于链表中

Testing case

• 功能测试(要删除的结点在首尾结点之间，删除首元结点，删除尾元结点)
• 边界测试(nullpter)

Key

• 顺序删除 T(n)=O(n)

  从头结点开始顺序遍历至待删除结点的前一个结点进行删除

• 伪删除 T(n)=O(1)

  1. 使用待删除结点的后一个结点值赋值替代待删除结点的值，待删除结点”伪装”为后一个结点
  2. 将待删除结点的next指针指向后一个 结点的next指向
  3. 删除后一个结点即可

Answer

struct LinkNode {
	LinkNode* pNext;
	int pValue;
};

void deleteNode(LinkNode** pHead, LinkNode* dNode) {
	//判断异常
	if (pHead == nullptr || dNode == nullptr) {
		doFalse = true;
		return;
	}

	if (dNode == *pHead) {
		//删除的结点为头结点
		delete dNode;
		dNode = nullptr;
		*pHead = nullptr;
	}
	else if (dNode->pNext != nullptr) {
		//删除的结点为首尾结点之间的结点
		LinkNode* ppNext = dNode->pNext;
		dNode->pValue = ppNext->pValue;
		dNode->pNext = ppNext->pNext;

		delete ppNext;
		ppNext = nullptr;
	}else {
		//删除的结点为尾元结点
		LinkNode* pPre = (*pHead)->pNext;
		//遍历至待删除结点的前一个结点
		while (pPre->pNext != dNode) {
			pPre = pPre->pNext;
		}

		pPre->pNext = nullptr;
		delete dNode;
		dNode = nullptr;
	}
}

19.2 删除链表中的重复连续结点

删除链表中重复连续的节点

重复结点指连续的值相同的结点

Testing case

• 功能测试(要删除的结点在首尾结点之间，首元结点，尾元结点)
• 边界测试(nullpter)

Key

• 顺序删除

  1. 顺序遍历整个链表，从第一个结点开始查找，是否存在连续的相同的结点

  2. 若存在，则需要删除当前连续结点，且判断其后续结点是否仍然连续

  3. 若不存在，则向后遍历，直至遍历完所有结点

  注意:

  1. 为了保证链表连续，需要时刻记录当前遍历结点的前一个结点，在进行删除操作后，将前一个结点的pNext更新，保持链表连续
  2. 使用一个ppNext时刻指针指向preNode的下一个结点

Answer

void deleteNode2(LinkNode** PHead) {
	//判断异常
	if (PHead == nullptr || *PHead== nullptr) {
		/*doFalse = true;*/
		return;
	}

	//为保证连续性需要每次记录当前未被删除结点的上一个结点
	LinkNode* preNode = nullptr;
	LinkNode* pNode = *PHead;
	//遍历链表找寻重复结点
	while (pNode != nullptr) {
		//设置结点是否需要删除的标志
		bool deleteY = false;
		//设置指向当前结点下一结点的指针
		LinkNode* ppNext = pNode->pNext;

		//判断当前结点是否需要删除
		if (ppNext != nullptr && ppNext->pValue == pNode->pValue) {
			deleteY = true;
		}

		//若不要删除则继续向下遍历
		if (!deleteY) {
			preNode = pNode;
			pNode = pNode->pNext;
		}
		else {

			//记录当前需要删除的结点
			LinkNode* DeleteNeed = pNode;
			//记录重复的元素值
			int value = DeleteNeed->pValue;
			//若当前结点需要删除，继续循环判断当前结点的下一个是否需要删除，判断结束后再进行删除
			ppNext = DeleteNeed->pNext;
			//删除当前结点
			delete DeleteNeed;
			DeleteNeed = nullptr;

			while (ppNext != nullptr&&ppNext->pValue == value) {																		//设置当前结点为需要删除的结点，注意顺序，不可和下面调换
				DeleteNeed = ppNext;																									//继续判断下一结点是否需要删除
				ppNext = ppNext->pNext;																					
				//删除结点
				delete DeleteNeed;
				DeleteNeed = nullptr;
			}

			if (preNode == nullptr) {
				*PHead = ppNext;
			}
			else {
				preNode->pNext = ppNext;
			}

			pNode = ppNext;

		}
	}
}

20 正则表达式匹配

请实现一个函数用来匹配包含‘.’和‘*’的正则表达式。模式中的字符’.’表示任意一个字符,而’米’表示它前面的字符可以出现任意次(含0次)。

在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串”aa”与模式”a.a”和”ab米ac米a”匹配,但与”aa.a”和”ab*a”均不匹配。

Testing case

• 功能测试(模式与输入字符串匹配或不匹配，模式字符串中含有普通字符,’.’,’*’，输入字符串为空字符串)
• 边界测试(nullptr)

Key

• 分治递归

  1. 在考虑当前字符是否匹配之前，先进行判断当前字符的下一个模式字符是否 ‘*’
  2. 若不是，则直接判断当前字符是否匹配，不匹配直接返回false，若匹配，移动指针，递归判断子字符串是否匹配
  3. 若是，则分三种情况讨论，当前字符出现0次，当前字符出现1次，当前字符出现多次
  4. 直至模式字符串匹配完成

  注意:

  1. ‘*’ 可以忽略前一个字符(出现0次)，但是’.’不可以忽略，该字符必须参与比较
  2. 防止*(pattern + 1)越界，所以basecase使用pattern到末尾做基准

Answer

bool match(char* str, char* pattern) {
	if (str == nullptr || pattern == nullptr) {
		isfalse = true;
		return false;
	}

	return matchCore(str, pattern);

}
bool matchCore(char* str, char* pattern) {
	//base case
	if (*str == '\0'&&*pattern == '\0') {
		return true;
	}

	if (*str != '\0'&&*pattern == '\0') {
		return false;
	}

	//首先判断当前判定模式字符的下一位是否为*
	if (*(pattern + 1) == '*') {
		if (*str == *pattern || *pattern == '.'&&*str != '\0') {
			return matchCore(str, pattern + 2) || matchCore(str + 1, pattern + 2) || matchCore(str + 1, pattern);
		}
		else {
			return matchCore(str, pattern + 2);
		}
	}
	else {
		if (*str == *pattern || *pattern == '.'&&*str != '\0') {
			//第一个字符匹配,两个匹配字符串指针均后移一位
			return matchCore(str + 1, pattern + 1);
		}
	}

	return false;

}

21 表示数值的字符串

请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串”+100”，”5e2”，”-123”，”3.1416”及”-1E-16”都表示数值,但”12e”，”1a3.14”，”1.2.3”，”+-5”及”12e+5.4”都不是。

Testing case

• 功能测试(有无整数部分，有无小数部分，有无指数部分，正数负数，含其他字符)
• 边界测试(nullptr，字符串为空)

Key

• 模式有序分析

  若一个字符串是数值字符串，则其满足[A][.B][e|EC],即A整数部分，B小数部分，C指数部分

  1. 先判断整数部分，最大努力寻找整数，直至遇到’’.’或者’e|E’或其他字符停止或至末尾
  2. 再判断小数部分，若遇到’.’，则再向后最大努力寻找整数，直至遇到’e|E’或其他字符停止或至末尾
  3. 最后判断指数部分，若遇到’e|E’，则再向后最大努力寻找整数，直至遇到其他字符停止或至末尾
  4. 若三部分判断完毕且字符串也遍历完毕则为数值字符串

  注意:

  1. 判断小数部分时使用 || 的原因为考虑无整数部分的小数也满足条件，无小数部分的整数也满足条件
  2. 判断指数部分时使用 && 的原因为考虑若含指数部分，则e之前至少含小数或整数，不可为空，e之后必含整数不可为空

Answer

bool isNum(const char* str) {
	
	//异常判断
	if (str == nullptr) {
		return false;
	}
	//首先判断A整数部分是否满足条件
	bool numric = isInteger(&str);

	//判断B小数部分是否满足条件
	if (*str == '.') {
		str++;

		numric = isUInteger(&str) || numric;
	}

	//判断C指数部分是否满足条件
	if (*str == 'e' || *str == 'E') {
		str++;
		numric = isInteger(&str) && numric;
	}

	//判断字符串是否还有剩余的其他字符

	numric = numric && *str == '\0';

	return numric;
}

bool isUInteger(const char** str) {
    const char *temp = *str;

	while (**str != '\0' && **str >= '0' && **str <= '9') {
		(*str)++;
	}
	//只要*str移动了则一定含有数字字符，一定大于temp，temp始终指向字符首部不变
	return *str > temp;
}

bool isInteger(const char** str) {
	if (**str == '+' || **str == '-') {
		(*str)++;
	}
	return isUInteger(str);
}

22 调整数组顺序使奇数位于偶数前面

输入一个整数数组,实现一个函数来调整该数组中数字的顺序使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。

Testing case

• 功能测试(数组奇数偶数交替，所有偶数在奇数前面，所有奇数在偶数前面)
• 边界测试(nullptr，仅含一个数字)

Key

• 双指针交换

  1. 设置两个指针分别为指向奇数的指针p1初始指向首元素，指向偶数的指针p2初始指向尾元素
  2. 移动两个指针，直至p1指向偶数，p2指向奇数，若p1<=p2，表明存在一个偶数在奇数之前，交换其位置
  3. 当p1>p2后，数组遍历完成，交换完成

• 考虑拓展性

  将性质判断从交换元素中解耦出来，使用函数指针指明判断方法即可

Answer

void Move(int* base, int length) {
	//异常判断
	if (base == nullptr || length < 0) {
		return;
	}

	//设置指针
	int* pOdd = base;
	int* pEven = base + length - 1;

	//通过交换移动奇数于偶数之前
	while (pOdd <= pEven) {
		while (pOdd <= pEven && (*pOdd & 0x1) != 0) {
			pOdd++;
		}

		while (pOdd <= pEven && (*pEven & 0x1) == 0) {
			pEven--;
		}

		if (pOdd <= pEven) {
			int temp;
			temp = *pOdd; *pOdd = *pEven; *pEven = temp;
		}

	}
}

//考虑拓展性
bool standard(int n) {
	return (n & 0x1) == 0;
}

void Move(int* base, int length, bool(*func)(int)) {
	//异常判断
	if (base == nullptr || length < 0) {
		return;
	}

	//设置指针
	int* pOdd = base;
	int* pEven = base + length - 1;

	//通过交换移动奇数于偶数之前
	while (pOdd <= pEven) {
		while (pOdd <= pEven && !func((*pOdd))) {
			pOdd++;
		}

		while (pOdd <= pEven && func((*pEven))) {
			pEven--;
		}

		if (pOdd <= pEven) {
			int temp;
			temp = *pOdd; *pOdd = *pEven; *pEven = temp;
		}

	}
}

23.1 链表中倒数第k个结点

输入一个链表,输出该链表中倒数第k个节点。

为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。

例如,一个链表有6个节点,从头节点开始,它们的值依次是1.2.3.4.5.6,这个链表的倒数第3个节点是值为4的节点。

Testing case

• 功能测试(倒数第k个结点为首结点，尾结点，中间结点)
• 边界测试(nullptr，链表结点数小于k)

Key

• 遍历两次链表

  第一次从头遍历链表获取链表长度，第二次直接移动至 n-k+1 个结点处，即为倒数第k个结点

• 遍历一次链表

  使用范围指针对，指针对始终相差k-1，当范围指针对右边界指针移动至链表尾部时，左边界指向的结点即为倒数第k个结点

  1. 首先定位左右指针的边界，初始左边界为链表头，右边界为首部右移 k-1 次后的结点
  2. 移动该范围指针对，直至右边界指针指向尾部元素

  注意:

  1. 注意代码的鲁棒性，对输入参数进行鲁棒性校验
  2. 在移动范围指针对时，注意k的取值是否会导致指针指向越界

Answer

struct ListNode
{
	int pValue;
	ListNode* pNext;
};

ListNode* LastK(ListNode* pHead, unsigned int k) {
	//异常判断
	if (pHead == nullptr || k <= 0) {
		return nullptr;
	}

	//设置范围指针对
	ListNode* pRight = pHead;
	//设置范围指针对的左起始边界
	ListNode* pLeft = pHead;

	//设置范围指针对的右起始边界
	for (int i = 0; i < k - 1; i++) {
		if (pRight->pNext == nullptr) {
			return nullptr;
		}
		pRight = pRight->pNext;
	}

	//移动范围指针对，直至右边界指针至尾结点
	while (pRight->pNext != nullptr) {
		pRight = pRight->pNext;
		pLeft = pLeft->pNext;
	}

	return pLeft;
}

23.2 求链表的中间结点

求链表的中间节点

如果链表中的节点总数为奇数,则返回中间节点;如果节点总数是偶数,则返回中间两个节点的任意一个

Testing case

• 功能测试(链表结点个数为奇数，为偶数，结点长度为1)
• 边界测试(nullptr，结点长度为0)

Key

• 遍历两次链表

  第一次从头遍历链表获取链表长度，根据长度奇偶性决定第二次移动的次数

• 遍历一次链表

  使用两个指针，一个faster指针一次移动2单位，一个slower指针一次移动一单位

  1. 设置两个指针的起始位置均为头结点，则faster指针移动至尾结点时，slower指针指向即为中间结点

  注意:

  1. faster指针在移动时只能一次一次移动，第二次移动时需要判断是否为nullptr，防止越界

Answer

struct ListNode
{
	int pValue;
	ListNode* pNext;
};

ListNode* Middle(ListNode* pHead) {
	//判断异常
	if (pHead == nullptr) {
		return nullptr;
	}

	//设置遍历指针与定位指针
	ListNode* faster = pHead;
	ListNode* slower = pHead;

	while (faster->pNext != nullptr) {
		faster = faster->pNext;
		if (faster->pNext != nullptr) {
			faster = faster->pNext;
		}
		slower = slower->pNext;
	}

	return slower;

}

24 链表中环的入口结点

如果一个链表中包含环,如何找出环的入口节点?

Testing case

• 功能测试(链表有无环，链表中仅有一个结点)
• 边界测试(nullptr)

Key

• 顺序求解

  1. 首先判断链表中是否有环
  2. 若链表中有环，则进而判断环中结点的个数
  3. 进而求得环的入口结点

• 双指针

  1. 设置两个速度不同的指针，若某一时刻快的指针追赶到慢的指针，说明有环，若快的指针遍历完链表后为nullptr，则说明无环
  2. 若链表中有环，则1中两个指针相遇的结点必定在环中，只需设置一个指针从该结点开始向后移动，同时计数，回到该结点的计数值即为环中结点数
  3. 使用范围指针对，范围长度为n+1，n为环中结点数，初始左边界为首部结点，右边界向右移动n个单位，向后移动，两个指针相遇的结点即为环入口

  注意:

  1. 范围指针对长度为n+1的原因为当右边界到达环末尾时，左边界将位于入口前一个结点，范围长度只会在 n+1 - 0 两值之间反复横跳

Answer

ListNode* getMeetNode(ListNode* pHead) {

	//异常判断
	if (pHead == nullptr) {
		return nullptr;
	}

	//若仅有一个结点则无环，无相遇结点可
	if (pHead->pNext == nullptr) {
		return nullptr;
	}

	//设置快慢指针
	ListNode* faster = pHead;
	ListNode* slower = pHead;

	while (faster != nullptr) {
		faster = faster->pNext;
		if (faster != nullptr) {
			faster = faster->pNext;
		}

		slower = slower->pNext;

		if (faster == slower) {
			return faster;
		}
	}

	//若无环，返回nullptr
	return nullptr;
}

ListNode* getEntryPoint(ListNode* pHead)
	ListNode* pMeetNode = getMeetNode(pH
	if (pMeetNode == nullptr) {
		return nullptr;
	}

	//若存在环，则计算环中结点个数
	int num = 1;
	ListNode* p = pMeetNode;

	while (p->pNext != pMeetNode) {
		p = p->pNext;
		num++;
	}


	//设置范围指针对，并设置初始位置
	ListNode* pRight = pHead;
	ListNode* pLeft= pHead;

	for (int i = 0; i < num; i++) {
		pRight = pRight->pNext;
	}

	//移动范围指针对找寻入口点
	while (pRight != pLeft) {
		pRight = pRight->pNext;
		pLeft = pLeft->pNext;
	}

	return pLeft;

}

25 反转链表

定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点

Testing case

• 功能测试(链表有一个或者多个结点)
• 边界测试(nullptr)

Key

• 遍历逐元素反转

  从头至尾遍历链表，将每个元素的pNext均置为前一个元素，首结点置为nullptr

  1. 设置两个指针，一个pPre指向当前结点的前一个结点，一个pNode指向当前结点，初始首结点的pPre置为nullptr
  2. 开始向后遍历，每次遍历到下一个元素时马上通过ppNext记录其下一个结点，并使用pPre指向设置其pNext指向，使当前结点指向其前一个结点
  3. 反转当前结点后，更新下一个结点的pPre指向

  注意:

  1. 由于单向链表向后遍历时，一个指针只能获得当前结点的状态，因此到下一个结点之前，需要使用pPre记录当前结点，使得设置下一个结点的pNext时可以获得前一个结点的状态
  2. 由于单向链表在反转某个结点时，会导致其与原本之后的结点断裂，导致无法向下遍历，因此在反转当前结点之前先记录当前结点的pNext值，反转之后，将该值赋值给pNode继续向下遍历

• 递归

  1. 从首节点开始，递归求得除当前结点外，其后剩余结点的反转链表
  2. 将当前结点作为其后反转链表的新尾部结点
  3. 直至当前结点为尾元结点

  注意:

  1. 当前结点其后剩余结点的反转链表的尾元结点为当前结点的下一个结点，该结点由剩余结点的头结点反转后成为尾元结点

Answer

1.

ListNode* Reverse(ListNode* pHead) {

	//异常判断
	if (pHead == nullptr) {
		return nullptr;
	}
	//设置状态保存变量
	ListNode* pPre = nullptr;
	ListNode* pNode = pHead;

	//遍历链表并设置每一个结点的pNext为前一个结点
	while (pNode != nullptr) {
		//保存下一个结点，防止链表断裂后无法遍历
		ListNode* ppNext = pNode->pNext;

		//设置当前结点的pNext为s前一个结点
		pNode->pNext = pPre;

		//更新状态保存变量值对应于下一个结点
		pPre = pNode;
		pNode = ppNext;
	}

	return pPre;
}

2.

ListNode* RReverseCore(ListNode* pNowHead) {
	//basecase
	if (pNowHead->pNext == nullptr) {
		return pNowHead;
	}
	
	//记录分治后的尾元结点即当前结点的下一个结点
	ListNode* LastTail = pNowHead->pNext;
	//递归返回分治后新的首结点
	ListNode* NewHead = RReverseCore(pNowHead->pNext);
	//将当前结点与已"反转"的后半部分的尾元结点连接
	LastTail->pNext = pNowHead;
	//当前结点成为新的尾元结点
	pNowHead->pNext = nullptr;

	return NewHead;
}

ListNode* RReverse(ListNode* pHead) {
	//异常判断
	if (pHead == nullptr) {
		return nullptr;
	}
	return RReverseCore(pHead);		
}

26 合并两个排序的链表

输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的

Testing case

• 功能测试(两个链表均为长度不为0排序的链表)
• 边界测试(两个链表有一个为nullptr，两个链表均为nullptr)

Key

• 递归

  1. 比较两个链表的首元结点的值的大小，选取小的结点作为当前合并后的首元结点
  2. 选取除1中结点两个链表中较小的首元结点作剩余结点合并后的首节点，作1中结点的下一个结点
  3. 直至有一个链表选取完全，首元结点为nullptr，则选取另一个链表的首元结点作剩余结点的首元结点

  注意:

  1. 鲁棒性的校验于basecase中完成，即使传入nullptr仍可作处理

Answer

ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
	//basecase
	if (pHead1 == nullptr) {
		return pHead2;
	}
	else if (pHead2 == nullptr) {
		return pHead1;
	}

	//设置指向合并后首结点的指针
	ListNode* MergedHead = nullptr;

	if (pHead1->pValue <= pHead2->pValue) {
		MergedHead = pHead1;
		MergedHead->pNext = Merge(pHead1->pNext, pHead2);
	}
	else {
		MergedHead = pHead2;
		MergedHead->pNext = Merge(pHead1, pHead2->pNext);
	}

	return MergedHead;
}

27 树的子结构

输入两棵二叉树A和B,判断B是不是A的子结构

Testing case

• 功能测试(AB均为普通二叉树，树B 是/不是 A的子结构)
• 边界测试(AB至少有一棵为空，二叉树仅有左子树，仅有右子树)

Key

• 穷举递归

  A树的每一个结点都有可能作B子结构的根节点(匹配)，因此需要穷举遍历A中所有结点

  1. 选择A树的当前根节点与当前正匹配的B的根节点作比较
  2. 若相等，则进而判断该A中该根节点的左右子树是否与B中当前正匹配的根节点相等
  3. 若左右子树均匹配，则返回true，否则返回false
  4. 若不相等，则选择A中下一个结点作匹配的根节点
  5. 直至当前匹配的B中根结点为nullptr，即匹配完成

  注意:

  1. double类型数据在判断是否相等时需要考虑精度问题，即 |x-y| 的绝对值在某个精度内方可判断x,y是否相等

Answer

bool hasSubTree(TreeNode* pHead, TreeNode* pSHead) {
	//判断异常
	if (pHead == nullptr || pSHead == nullptr) {
		return false;
	}
	//设置返回值
	bool result = false;

	//判断是否是否含有与sub根结点相同的结点
	if (Equal(pHead->pValue, pSHead->pValue)) {
		//若根结点相同则继续判断是否含有sub子树
		result = hasSubTreeCore(pHead, pSHead);
	}

	//若该根结点与sub子树根结点不同，或该根结点下的子树与sub子树结构不同，则向下遍历
	if (!result) {
		result = hasSubTreeCore(pHead->pLeft, pSHead);
	}
	if (!result) {
		result = hasSubTreeCore(pHead->pRight, pSHead);
	}

	return result;

}

bool hasSubTreeCore(TreeNode* pHead, TreeNode* pSHead) {
	//base case
	if (pSHead == nullptr) {
		return true;
	}
	if (pHead == nullptr) {
		return false;
	}
	//判断当前结点是否相同
	if (!Equal(pHead->pValue, pSHead->pValue)) {
		return false;
	}
	//递归判断左右子树是否结构相同
	bool hasLeftSub = hasSubTreeCore(pHead->pLeft, pSHead->pLeft);
	bool hasRightSub = hasSubTreeCore(pHead->pRight, pSHead->pRight);
	
	return hasLeftSub && hasRightSub;
}

bool Equal(double x, double y) {
	return (x - y >= -0.001) && (x - y <= 0.001);
}

28 二叉树的镜像

请完成一个函数,输入一棵二叉树,该函数输出它的镜像

Testing case

• 功能测试(普通二叉树，仅有一个结点的二叉树，仅有左/右子树的二叉树)
• 边界测试(nullptr)

Key

• 递归交换

  1. 先序遍历一颗二叉树
  2. 每到根节点时交换根节点的左右子树，递归向下继续遍历
  3. 直至根节点为nullptr

• 层次遍历

  1. 使用队列进行层次遍历
  2. 每遍历到一个结点，将其左右子树交换后再重新压入队列
  3. 直至队列为空，即遍历完成

Answer

1.

void TreeMirro(TreeNode* pHead) {
	//base case
	if (pHead == nullptr) {
		return;
	}

	//先根遍历的同时交换左右子结点，由根开始
	TreeNode* pTemp = pHead->pLeft;
	pHead->pLeft = pHead->pRight;
	pHead->pRight = pTemp;

	cout << pHead->pValue << " ";

	//左子树
	if (pHead->pLeft) {
		TreeMirro(pHead->pLeft);
	}

	if (pHead->pRight) {
		TreeMirro(pHead->pRight);
	}

}

2.

void Non_RecursiveTreeMirro(TreeNode* pHead) {
	//判断异常
	if (pHead == nullptr) {
		return;
	}

	//使用队列完成非递归遍历
	queue<TreeNode*> Tqueue;
	Tqueue.push(pHead);
	
	//层次遍历
	while (!Tqueue.empty()) {

		//弹出根结点
		TreeNode* pTempHead = Tqueue.front();
		Tqueue.pop();
		
		//交换根节点的左右子树
		TreeNode* pTemp = pTempHead->pLeft;
		pTempHead->pLeft = pTempHead->pRight;
		pTempHead->pRight = pTemp;

		cout << pTempHead->pValue << " ";

		//将交换后的左右子树压入队列遍历交换
		if (pTempHead->pLeft) {
			Tqueue.push(pTempHead->pLeft);
		}

        		if (pTempHead->pRight) {
        			Tqueue.push(pTempHead->pRight);
		}
	}
}

29 对称的二叉树

请实现一个函数,用来判断一棵二叉树是不是对称的

如果一棵二叉树和它的镜像一样,那么它是对称的

Testing case

• 功能测试(对称/部队称的二叉树)
• 边界测试(nullptr，只有一个结点的二叉树，所有结点值相同的二叉树)

Key

• 对称前序遍历

  使用一个递归同时完成前序遍历与对称前序遍历，对称前序遍历为根右左

  1. 设置递归的参数结点为两个，一个为前序遍历的结点，一个为对称前序遍历的结点
  2. 判断当前前序与对称前序遍历的结点的值是否相等，相等继续判断之后遍历结点的值是否相等(根左右-根右左)，若不相等则不对称
  3. 直至两种遍历次序下的结点同时为空，若不同时为空，表明不对称

  注意:

  1. 对称为结构对称与值对称，若各结点值均相等，则需要将nullptr的孩子结点考虑在内，进而判断结构是否对称
  2. 通过设置两个参数同时完成两种遍历次序的递归，进而同时完成对称结点的相等判断

Answer

bool isSymmetry(TreeNode* pHead) {
	//判断异常
	if (pHead == nullptr) {
		return false;
	}

	return isSymmetryCore(pHead, pHead);
}

bool isSymmetryCore(TreeNode* pHead, TreeNode* pSHead) {
	//base case
	//若前序遍历与对称前序遍历的头结点同时为空，满足对称条件
	if (pHead == nullptr && pSHead == nullptr) {
		return true;
	}
	//若前序遍历与对称前序遍历的头结点不同时为空，则不满足对称条件
	if (pHead == nullptr || pSHead == nullptr) {
		return false;
	}

	if (!(pHead->pValue == pSHead->pValue)) {
		return false;
	}

	//递归判断前序遍历与对称前序遍历的结点
	return isSymmetryCore(pHead->pLeft, pSHead->pRight) && isSymmetryCore(pHead->pRight, pSHead->pLeft);

}

30 顺时针打印矩阵

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字

Testing case

• 功能测试(数组具有多行多列，数组只有一行/一列)
• 边界测试(nullptr)

Key

• 逐圈输出

  1. 每次循环从圈的起点 (start,start) [start取值0,1…k] 开始顺时针输出
  2. 记录圈右边界与下边界，先从起始行开始输出至右边界
  3. 若起始行下界仍有未输出元素，则从当前列开始，起始行下一行向下输出该列元素，至下界
  4. 若右边界列左边仍有未输出元素，则从当前行开始，右边界列的前一行开始向左(前)输出该行元素，至左界
  5. 若左边界列的上边仍有未输出元素，则从当前列开始，下边界的上一行开始向上输出该列元素，至起始行的下一行

  注意:

  1. 因为矩阵不是方阵，因此循环次数判断时需要行列分别判断是否大于 2 * start
  2. 将通过二级指针参数传递二维数组时，可以动态创建一个一级指针数组，使用二级指针指向，并使用已创建的二维数组的各行为其初始化后再传递该二级指针

Answer

void Sprint(int** arr, int rows, int cols) {
	if (arr == nullptr || rows <= 0 || cols <= 0) {
		hasException = true;
		return;
	}

	int start = 0;

	//判断循环输出圈的次数
	while (rows > 2 * start && cols > 2 * start) {
		
		SprintCore(arr, rows, cols, start);
		start++;

	}

}

void SprintCore(int** arr, int rows, int cols, int start) {
	
	//当前坐上结点的坐标为 (start,start)
	
	//记录当前待输出圈的边界
	int endX = cols - 1 - start;
	int endY = rows - 1 - start;

	//输出圈的上半部分
	for (int i = start; i <= endX; i++) {
		cout << arr[start][i] << " ";
	}
	//判断圈是否需要继续向下输出右半部分
	if (endY > start) {
		for (int i = start + 1; i <= endY; i++) {
			cout << arr[i][endX] << " ";
		}
	}
	//判断圈是否需要继续向左输出下半部分
	if (endY > start && endX > start) {
		for (int i = endX - 1; i >= start; i--) {
			cout << arr[endY][i] << " ";
		}
	}
	//判断圈是否需要继续向上输出左半部分
	if (endY - 1 > start && endX > start) {
		for (int i = endY - 1; i > start; i--) {
			cout << arr[i][start] << " ";
		}
	}
	
}

31 包含min函数的栈

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数

在该栈中,调用min,push及pop的时间复杂度都是O(1)

Testing case

• 新压入的元素比数据栈中元素小
• 新压入的元素比数据栈中元素大
• 新弹出的元素是最小元素
• 新弹出的元素不是最小元素

Key

• 辅助栈记录数据栈的最小值状态

  1. 压入元素于数据栈，判断当前压入的元素与min栈栈顶元素的大小
  2. 若min栈为空，表示当前数据栈无元素，直接压入即可
  3. 否则将小的元素再次压入min栈，作为当前数据栈的最小元素，位于min栈栈顶
  4. 弹出时，若栈非空，则同时弹出数据栈，min栈的栈顶
  5. 取数据栈当前的最小元素直接取当前min栈的栈顶即可

  注意:

  1. 为了保证O(1)的复杂度，因此必须在数据栈元素全部压入前进行最小值状态记录，否则压入后记录只能从栈顶取出
  2. 为保证min栈的每个元素均对应数据栈每一种状态下的最小值，需要保证两栈元素个数相同，即使压入的元素与当前最小值相同，仍需再次压入min栈

Answer

template <class T> 
class StackWithMin {

public:
	StackWithMin() = default;
	~StackWithMin() = default;

	void push(const T& value) {
		//压入元素
		m_data.push(value);
		//更新min栈的栈顶元素
		if (m_min.size() == 0 || value <= m_min.top()) {
			//若min栈为空或者压入的元素为最小元素，即小于等于min栈栈顶元素
			m_min.push(value);
		}
		else {
			//保持两栈元素个数相等，保证min栈的每个栈顶元素均对应data栈不同状态下的最小值
			m_min.push(m_min.top());
		}
	}
	void pop() {
		if (m_data.size() != 0 && m_min.size() != 0) {
			m_data.pop();
			m_min.pop();
		}
	}

	const T& getMin() const {
		if (m_min.size() != 0) {
			return m_min.top();
		}
	}
private:
	stack<T> m_data;
	stack<T> m_min;
};

32 栈的压入,弹出序列

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序,假设压入栈的所有数字均不相等

Testing case

• 功能测试(输入的数组有两个数字，一个数字，第二个序列是/不是第一个序列的输出序列)
• 边界测试(nullptr)

Key

• 辅助栈模拟序列的输入输出

  1. 从输出队列入手，遍历输出队列的每一个元素，判断当前输出队列元素是否与辅助栈中栈顶元素匹配
  2. 若匹配，将栈顶元素弹出，输出队列指针后移判断下一个元素是否匹配
  3. 若不匹配或者栈为空，则判断输入队列的元素是否已全部入栈，若未全部入栈，则将输入队列的中的一个元素压栈，进而继续1中判断
  4. 若输入队列的元素已全部入栈，且输出队列未遍历完毕，则不是匹配序列，退出遍历
  5. 若输出队列元素已全部匹配且栈为空，则是匹配队列

Answer

bool isIOMatch(const int* pInput, const int* pOutput, int length) {
	
	//设置返回值
	bool imatch = false;
	//异常判断
	if (pInput == nullptr || pOutput == nullptr || length <= 0) {
		isException = true;
		return imatch;
	}

	//创建辅助栈
	stack<int> helperStack;

	//设置临时指针
	const int* tInput = pInput;
	const int* tOutput = pOutput;

	//逐个判断输出队列中的各元素是否匹配
	while (tOutput - pOutput != length) {

		//若栈中无元素或者当前栈顶元素与输出指针指向的元素不匹配，则将输入队列的元素压入栈
		if (helperStack.size() == 0 || helperStack.top() != *tOutput) {
			
			if (tInput - pInput == length) {
				break;
			}

			helperStack.push(*tInput);
			tInput++;
		}

		//若当前栈顶元素与当前输出指针指向的元素，则将栈顶元素弹出，判断当前栈顶与输出指针的下一个指向是否匹配
		if (helperStack.top() == *tOutput) {
			helperStack.pop();
			tOutput++;
		}

	}

	//若输出队列遍历完毕且辅助栈为空，则表示匹配
	if (helperStack.size() == 0 && tOutput - pOutput == length) {
		imatch = true;
	}

	return imatch;
}

33.1 从上到下打印二叉树

不分行

从上到下打印二叉树从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印

Testing case

• 功能测试(完全二叉树,只有左/右子树的二叉树)
• 边界测试(nullptr,只有一个结点的二叉树)

Key

• 辅助队列存储当前遍历结点的左右子结点

  1. 将根节点压入队列
  2. 遍历队列的队首节点，并弹出队列
  3. 若当前遍历节点含有左右子结点，则从左至右将左右子节点压入队列尾部，否则结束本次循环
  4. 重复步骤2，直至队列为空

Answer

void printTree(TreeNode* pHead) {
	//异常判断
	if (pHead == nullptr) {
		return;
	}

	//设置辅助队列
	deque<TreeNode*> deque;

	//首先将根节点压入队列
	deque.push_back(pHead);

	//遍历
	while (deque.size() != 0) {

		//取出当前队列中的头元素
		TreeNode* pTemp = deque.front();
		deque.pop_front();

		//输出元素
		cout << pTemp->pValue << " ";

		//若取出的结点含左右子树，则重新压入队列
		if (pTemp->pLeft)
			deque.push_back(pTemp->pLeft);
		if (pTemp->pRight)
			deque.push_back(pTemp->pRight);

	}
}

33.2 从上到下打印二叉树

分行

从上到下打印二叉树从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印

Testing case

• 功能测试(完全二叉树,只有左/右子树的二叉树)
• 边界测试(nullptr,只有一个结点的二叉树)

Key

• 辅助队列存储当前遍历结点的左右子结点

  1. 将根节点压入队列
  2. 遍历队列的队首节点，并弹出队列
  3. 若当前遍历节点含有左右子结点，则从左至右将左右子节点压入队列尾部，否则结束本次循环
  4. 重复步骤2，直至队列为空

• 状态记录变量

  1. 设置记录当前层仍未输出的节点数的变量 toBePrinted
  2. 设置记录下一层节点数的累加计数变量 numNextLayer
  3. 每遍历一个节点，toBePrinted减1，若减为0，则表示本层节点输出完毕，应换行
  4. 每将一个节点压入队列，numNextLayer增1，记录下一层的节点数，直至toBePrinted为0(本层节点输出完毕)时，使用numNextLayer更新toBePrinted，并将自身重置为0，进行下一层节点的输出

Answer

void lprintTree(TreeNode* pHead) {
	//异常判断
	if (pHead == nullptr) {
		return;
	}

	//设置辅助队列
	deque<TreeNode*> deque;

	//首先将根节点压入队列
	deque.push_back(pHead);

	//设置状态记录变量
	//记录下一层的节点个数
	int NextLayer = 0;
	//记录本层仍未输出的节点个数
	int toBePrinted = 1;

	//遍历
	while (deque.size() != 0) {

		//取出当前队列中的头元素
		TreeNode* pTemp = deque.front();
		deque.pop_front();

		//输出元素
		cout << pTemp->pValue << " ";
		toBePrinted--;

		//若取出的结点含左右子树，则重新压入队列
		if (pTemp->pLeft) {
			deque.push_back(pTemp->pLeft);
			NextLayer++;
		}
		if (pTemp->pRight) {
			deque.push_back(pTemp->pRight);
			NextLayer++;
		}

		if (toBePrinted == 0) {
			//本层的元素输出完毕，换行，进行下一行元素的输出
			cout << endl;
			//更新toBePrinted为下一层应输出的节点数
			toBePrinted = NextLayer;
			//重置NextLayer，记录下一层的下一层节点数
			NextLayer = 0;
		}

	}
}

33.3 从上到下打印二叉树

之字形打印二叉树

请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推

Testing case

• 功能测试(完全二叉树,只有左/右子树的二叉树)
• 边界测试(nullptr,只有一个结点的二叉树)

Key

• 双栈完成之字形输出更替

  1. 将根节点压入栈1
  2. 遍历栈1元素，逐个将栈1中的元素弹出，并将弹出的每个元素的左右节点按自左向右的顺序压入栈2，直至栈1为空，并输出换行
  3. 遍历栈2元素，逐个将栈2中的元素弹出，并将弹出的每个元素的左右节点按自右向左的顺序压入栈1，直至栈2为空，并输出换行
  4. 重复2,3直至栈2与栈3均为空

Answer

void SprintTree(TreeNode* pHead) {
	//异常判断
	if (pHead == nullptr) {
		return;
	}

	//设置两个辅助栈
	deque<TreeNode*> deque1;
	deque<TreeNode*> deque2;

	//首先将根节点压入栈1
	deque1.push_back(pHead);

	//遍历
	while (deque1.size() != 0 || deque1.size() != 0) {

		//取出并遍历栈1中的元素
		while (deque1.size() != 0) {
			TreeNode* pTemp = deque1.back();
			deque1.pop_back();

			//输出元素
			cout << pTemp->pValue << " ";

			//若取出的结点含左右子树，则自左向右压入栈2
			if (pTemp->pLeft) {
				deque2.push_back(pTemp->pLeft);
			}
			if (pTemp->pRight) {
				deque2.push_back(pTemp->pRight);
			}

		}

		cout << endl;

		//取出并遍历栈2中的元素
		while (deque2.size() != 0) {
			TreeNode* pTemp2 = deque2.back();
			deque2.pop_back();

			//输出元素
			cout << pTemp2->pValue << " ";

			//若取出的结点含左右子树，则自右向左压入栈1
			if (pTemp2->pRight) {
				deque1.push_back(pTemp2->pRight);
			}

			if (pTemp2->pLeft) {
				deque1.push_back(pTemp2->pLeft);
			}
			
		}

		cout << endl;

	}
}

34 二叉搜索树的后序遍历序列

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果

如果是则返回true,否则返回false,假设输入的数组的任意数字都互不相同

Testing case

• 功能测试(后序遍历序列对应/不对应一颗搜索二叉树，二叉树可以为完全二叉搜索树，普通二叉搜索树，无左/右子树的二叉搜索树，只有一个结点的二叉树)
• 边界测试(nullptr)

Key

• 递归

  1. 二叉树后序遍历序列的最后一个节点为本树的根节点，选取该根节点
  2. 结合二叉搜索树的性质，找寻序列根节点之前第一个比根节点的大的节点作为该根节点左右子树的分界
  3. 在左子树满足均小于根节点的性质下，判断右子树中是否存在比根节点小的节点
  4. 完成一轮二叉搜索树判断后，进而递归判断该根节点的左右子树是否也满足二叉搜索树性质

  注意:

  1. 二叉树的后序遍历序列的最后一个节点为根节点
  2. 二叉搜索树根节点的左子树所有节点均小于根节点，右子树的所有节点均大于根节点
  3. 递归时通过序列首部与序列长度确定左右子树范围，若当前根节点无左/右子树，则无需判断

Answer

bool VerifySquenceOfBST(int* Seq, int Slength) {
	
	//异常判断
	if (Seq == nullptr || Slength <= 0) {
		return false;
	}

	//判断当前根节点与其左右子树是否满足二叉搜索树
	//取当前根节点
	int root = Seq[Slength - 1];

	//找寻第一个比根节点大节点作为左右子树分界，此时左子树均比根节点小
	int i = 0;
	for (; i < Slength - 1; i++) {
		if (Seq[i] > root) {
			break;
		}
	}

	//判断该根节点右子树是否存在比其小的节点
	int j = i;
	for (; j < Slength - 1; j++) {
		if (Seq[j] < root) {
			return false;
		}
	}

	//此时根节点左子树的节点均比根节点小，右子树的节点均比根节点大，满足二叉搜索树性质
	//--------------------------------------------------------------------
	//进而判断该根节点的左右子树是否满足二叉搜索树性质

	//若含左子树，则判断左子树是否满足二叉搜索树性质
	bool left = true;
	if (i > 0)
		left = VerifySquenceOfBST(Seq, i);

	//若含右子树，判断右子树是否满足二叉搜索树性质
	bool Right = true;
	if (i < Slength - 1)
		Right = VerifySquenceOfBST(Seq + i, Slength - i - 1);

	return left && Right;
}

35 二叉树中和为某一值的路径

输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径

从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。二叉树节点的定义如下:

Testing case

• 功能测试(二叉树中有一/多条符合的路径，二叉树中没有符合的路径)
• 边界测试(nullptr)

Key

• 先序遍历寻找路径

• 设置路径数组与状态记录变量来记录当前路径状态

  1. 先序遍历二叉树，当遍历到根节点时，将当前节点压入数组并记录当前路径累加和
  2. 若当前路径数组中的结点已构成一条路径(当前压入的结点为叶子结点)且满足期望和，则对数组中的路径序列进行输出
  3. 否则递归判断左右子树(若含有左右子树)的路径情况
  4. 若已为一条路径却不满足期望和，则先将当前结点从路径数组中弹出后继续遍历

  注意:

  1. 当前结点从路径数组中弹出后累加和currentSum也需要回退，但是currentSum为值传递，在递归回溯再递归时，currentSum始终表示当前的累加和，也就是说当函数回到上一级时，当前currentSum的状态不再保存，自动还原到上一级的状态
  2. 树的路径为从根节点出发到叶子结点，因此若为到叶子结点但是期望值满足的并不符合路径要求

Answer

void FindPathInTree(TreeNode* pHead, int ExpectedNum) {
	//判断异常
	if (pHead == nullptr) {
		return;
	}

	//设置存储路径的容器与记录和的变量
	vector<int> path;
	int currentSum = 0;

	//转调路径函数
	FindPathInTree(pHead, ExpectedNum, path, currentSum);
}

void FindPathInTree(TreeNode* pHead, int ExpectedNum, vector<int>& path, int currentSum) {
	
	//先序遍历
	
	//将当前结点的值压入路径数组，记录当前路径
	path.push_back(pHead->pValue);

	//累加和，记录当前路径和
	currentSum += pHead->pValue;

	//判断当前路径和是否为期望值且为一条树的路径(该结点为叶子结点)
	if (pHead->pLeft == nullptr && pHead->pRight == nullptr && ExpectedNum == currentSum) {
		//找到一条路径，输出该路径
		cout << "Path1 : ";
		for (auto i : path) {
			cout << i << " ";
		}
	}

	//先序遍历，判断左右子树中是否存在路径
	if (pHead->pLeft != nullptr)
		FindPathInTree(pHead->pLeft, ExpectedNum, path, currentSum);

	if (pHead->pRight != nullptr)
		FindPathInTree(pHead->pRight, ExpectedNum, path, currentSum);

	//直到找寻到叶子结点且不满足路径和才回退
	path.pop_back();
}

36 复杂链表的复制

请实现函数ComplexListNode* Clone(ComplexListNode* pHead)，复制一个复杂链表

在复杂链表中,每个节点除了有一个m_pNext指针指向下一个节点,还有一个m_pSibling指针指向链表中的任意节点或者nullptr

Testing case

• 功能测试(结点中m_pSibling指向自身，两个结点m_pSibling形成环状结构，链表只有一个结点)
• 边界测试(nullptr)

Key

• 复杂问题分解 T(n) = O(n) S(n) = 1

  1. 对链表结点进行复制并与原链表链接 A-A‘-B-B’

     遍历原链表逐个结点复制，并将复制后的结点插入到原结点与原节点的下一个结点之间

     注意:

     1. 链接的作用在于进行第二步时，复制后结点的m_pSibling指向为其原结点的m_pSibling的下一个结点

  2. 对复制后且与原链表链接的新链表的m_pSibling指向更新

     遍历原链表每个结点，若其m_pSibling不为nullptr则将其复制结点(下一个结点)的m_pSibling置为其m_pSibling的下一个结点

  3. 拆解链接链表并返回新链表头

     1. 遍历链接链表，通过两个指针实现将每一个结点的pNext指向其下下一个结点
     2. pNode指针从头开始将其指向的结点的pNext指向其下下一个结点(原链表)
     3. pCNode指针记录pNode的下一个结点，并将该结点的pNext指向其下下一个结点(复制后链表)

     注意:

     1. 在拆解过程中应注意需要将原链表还原，因为整个复制过程是基于原链表的

• 哈希表 T(n) = O(n) S(n) = n

  1. 完成链表结点的复制与pNext的指向复制
  2. 同时使用map容器完成原结点与相应复制结点映射关系的存储
  3. 同时遍历原链表与复制链表，将新链表结点的pSibiling指向置为相应原链表结点pSibiling指向在map中的映射即可

Answer

1.

void CopyNode(LinkNode* pHead) {

	//创建临时指针
	LinkNode* pNode = pHead;
	//遍历链表并完成结点创建与链接
	while (pNode != nullptr) {
		LinkNode* pCopyNode = new LinkNode();
		pCopyNode->pSibling = nullptr;
		//复制结点
		pCopyNode->pValue = pNode->pValue;
		//链接结点
		pCopyNode->pNext = pNode->pNext;
		pNode->pNext = pCopyNode;

		//向下遍历
		pNode = pCopyNode->pNext;
	}
}

void ConnectSibiling(LinkNode* pHead) {

	//创建临时指针
	LinkNode* pNode = pHead;
	//遍历链表并完成sibiling指向的复制
	while (pNode != nullptr) {
		//创建指向当前结点对应的复制结点的指针
		LinkNode* pCopyNode = pNode->pNext;

		//设置复制结点的sibiling指向
		if (pNode->pSibling)
			pCopyNode->pSibling = pNode->pSibling->pNext;

		//向下遍历
		pNode = pCopyNode->pNext;
	}
}

LinkNode* ConnectNext(LinkNode* pHead) {

	//创建临时遍历指针
	LinkNode* pNode = pHead;
	LinkNode* pCNode = nullptr;
	//创建最终存放复制链表头的指针
	LinkNode* pCopyHead = nullptr;


	//首先确定复制后的链表头
	pCopyHead = pNode->pNext;
	//还原原链表
	pNode->pNext = pCopyHead->pNext;
	//初始化复制链表遍历指针
	pCNode = pCopyHead;
	//向下遍历
	pNode = pNode->pNext;
	//此时pNode位于pCNode之后一个结点

	while (pNode != nullptr) {
		//将复制后的结点的指向更新，使其指向下一个复制后的结点
		pCNode->pNext = pNode->pNext;
		//向下遍历
		pCNode = pCNode->pNext;
		//将复制前的结点的指向更新，使其指向下一个复制前的结点
		pNode->pNext = pCNode->pNext;
		//向下遍历
		pNode = pNode->pNext;
	}

	return pCopyHead;
}

LinkNode* CopyFromComplexList(LinkNode* pHead) {

	//异常判断
	if (pHead == nullptr) {
		return nullptr;
	}

	//分三步完成复杂链表的复制

	//第一步 复制每个结点并与原链表链接
	CopyNode(pHead);
	//第二步 将原链表的sibiling指向复制到新链表
	ConnectSibiling(pHead);
	//第三步 拆解链表，并完成新链表的pNext指向
	return ConnectNext(pHead);
}

2.

LinkNode* CopyFromComplexListByMap(LinkNode* pHead) {
	//异常判断
	if (pHead == nullptr) {
		return nullptr;
	}

	//复制结点并将结点对应关系存入Map
	map<LinkNode*, LinkNode*> NodeMap;

	//设置临时遍历指针,并完成链表头的复制
	LinkNode* pNode = pHead;
	LinkNode* pCopyHead = new LinkNode();

	pCopyHead->pValue = pNode->pValue;
	pCopyHead->pNext = nullptr;
	pCopyHead->pSibling = nullptr;

	//map存放原结点与复制结点的映射
	NodeMap[pNode] = pCopyHead;

	//向下遍历
	LinkNode* pCNode = pCopyHead;
	pNode = pNode->pNext;
	
	//遍历原链表完成结点的复制与映射的存放
	while (pNode != nullptr) {

		//结点复制
		LinkNode* pCTemp = new LinkNode();
		pCTemp->pValue = pNode->pValue;
		pCTemp->pNext = nullptr;
		pCTemp->pSibling = nullptr;

		//map存放原结点与复制结点的映射
		NodeMap[pNode] = pCTemp;

		//复制链表的链接
		pCNode->pNext = pCTemp;

		//向下遍历
		pCNode = pCNode->pNext;
		pNode = pNode->pNext;

	}

	//重置遍历指针于链表表头
	pNode = pHead;
	pCNode = pCopyHead;

	//遍历原链表完成复制链表的pSibiling指向
	while (pNode != nullptr) {
		if (pNode->pSibling != nullptr) {
			pCNode->pSibling = NodeMap[pNode->pSibling];
		}

		//向下遍历
		pNode = pNode->pNext;
		pCNode = pCNode->pNext;
	}

	return pCopyHead;
}

37 二叉搜索树与双向链表

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表

要求不能创建任何新的节点,只能调整树中节点指针的指向

Testing case

• 功能测试(二叉搜索树为完全二叉树，无左/右子树，只有一个结点)
• 边界测试(nullptr)

Key

• 中序遍历与链表尾部实时记录

  1. 中序遍历二叉搜索树并使用PointToListTail指针实时记录当前形成双向链表的尾部
  2. 遍历至根节点时，将该根节点与双向链表链接，并作为新的尾部
  3. 直至遍历结点为nullptr

  注意:

  1. 二叉搜索树的中序遍历序列为小大排序的
  2. 一定要使用PointToListTail记录双向链表末尾结点，否则仅依靠递归返回当前遍历结点会遗漏部分结点
  3. 从最左下的最小结点开始将整个二叉搜索树串成一个小大排序的双向链表

Answer

TreeNode* Convert(TreeNode* pHead) {
	
	//异常判断
	if (pHead == nullptr) {
		return nullptr;
	}

	//设置记录当前双向链表尾部的指针
	TreeNode* PointToListTail = nullptr;
	//将尾部的指针一并传入进行递归
	ConvertCore(pHead, &PointToListTail);
	//返回双向链表的首部
	while (PointToListTail != nullptr && PointToListTail->pLeft != nullptr) {
		PointToListTail = PointToListTail->pLeft;
	}

	return PointToListTail;
}

void ConvertCore(TreeNode* pHead, TreeNode** PointToListTail) {
	
	//设置遍历指针
	TreeNode* pCurrentNode = pHead;
	
	//basecase
	if (pHead == nullptr) {
		return;
	}

	//中序遍历
	if (pCurrentNode->pLeft != nullptr) {
		ConvertCore(pCurrentNode->pLeft, PointToListTail);
	}

	//设置当前根节点为双向链表的新尾部
	pCurrentNode->pLeft = *PointToListTail;

	if (*PointToListTail != nullptr) {
		(*PointToListTail)->pRight = pCurrentNode;
	}

	*PointToListTail = pCurrentNode;

	//将新双向链表与右子树连接
	if (pCurrentNode->pRight != nullptr) {
		ConvertCore(pCurrentNode->pRight, PointToListTail);
	}

}

38 序列化二叉树

请实现两个函数,分别用来序列化和反序列化二叉树

Testing case

• 功能测试(二叉树为完全二叉树，无左/右子树，只有一个结点，值均相同的二叉树)
• 边界测试(nullptr)

Key

• 先序遍历 -序列化

  先序遍历二叉树，并且将根结点为nullptr的左右孩子使用特殊字符表示

• 遍历序列化数组 -反序列化

  1. 遍历序列化数组，为数字元素创建结点，特殊字符元素跳过
  2. 直至序列化数组元素遍历完毕

  注意:

  1. 递归条件以序列化数组为主，并且在设置当前根节点的左右子树时，应注意序列化数组指针的移动
  2. 二级指针的使用目的在于使用参数记录一级指针的改动(传出参数)，如序列化数组指针，根节点指针

Answer

//用于异常判断的全局变量
bool hasException = false;

//序列化
void Serializaion(TreeNode* pHead) {

	//异常判断
	if (pHead == nullptr) {
		cout << "$,";
		return;
	}

	//先序遍历
	cout << pHead->pValue << ",";
	Serializaion(pHead->pLeft);
	Serializaion(pHead->pRight);

}

//反序列化
bool isNumber(char c) {
	if (c == '$') {
		return false;
	}
	else if (c >= '0' && c <= '9') {
		return true;
	}
	else {
		hasException = true;
		return false;
	}
}

void ReSerializaionCore(TreeNode** pRoot, char** ser) {

	if (isNumber(**ser)) {
		*pRoot = new TreeNode();
		(*pRoot)->pValue = **ser - '0';
		(*pRoot)->pLeft = nullptr;
		(*pRoot)->pRight = nullptr;

		//序列指针后移
		(*ser)++;

		ReSerializaionCore(&((*pRoot)->pLeft), ser);
		ReSerializaionCore(&((*pRoot)->pRight), ser);

	}
	else {
		if (hasException)
			return;
		//序列指针后移
		(*ser)++;
	}
	
}

39.1 字符串的排列

输入一个字符串,打印出该字符串中字符的所有排列

Testing case

• 功能测试(字符串有一个或多个字符，字符串中存在值相同的元素)
• 边界测试(nullptr,字符串为空)

Key

• 决策树 + 分治 + 穷举递归 无需额外的内存

  1. 使用pCurrntStart指针，从第一个位置开始逐个存放全排列后的元素
  2. 当决策好pCurrntStart位置的元素时，递归对pCurrntStart后其余位置进行元素决策
  3. 在进行下一次同位置(同层)决策前，需要还原字符串的排列顺序
  4. 直至每个全排列位置均已决策相应的元素，输出一次全排列结果
  5. 直至首位置水平决策全部作出且各决策均完成全排列输出，完成该字符串所有决策输出

  注意:

  1. pCurrntStart指针用于指向当前正作元素决策的全排列位置，初始为全排列后第一个位置开始，即字符串的首位置
  2. 决策的所有选择来自于当前字符串的所有元素，为保证能够作出所有同层决策，因此需要对当前剩余元素进行遍历
  3. 在2的决策作出之前，需要还原字符串状态，否则下一次决策将无意义
  4. 该方法直接使用原字符串内存作为排列后字符串的存储内存

• 决策树 + 分治 + 穷举递归 额外分配存储内存

  1. 遍历原字符串vector1，将第一个位置所有情况进行穷举决策
  2. 选择当前决策的元素压入到vector2，进行递归下一位置的穷举决策
  3. 在进行下一位置的穷举决策之前需要弹出已决策元素
  4. 在进行同层其他决策前，需要恢复已从vector1中弹出的元素以及对应的vector2的排列状态

  注意:

  1. 使用一个vector暂存目前排列状态，无需在原内存上通过指针的较复杂操作

Answer

1.

void Permutation(char* arr) {
	//异常判断
	if (arr == nullptr) {
		return;
	}
	PermutationCore(arr, arr);
}

void PermutationCore(char* pAllStart, char* pCurrntStart) {
	//base case
	if (*pCurrntStart == '\0') {
		cout << pAllStart << endl;
	}

	//遍历字符串的每个元素 -- 保证作出所有可能的水平决策
	for (char* pCur = pCurrntStart; *pCur != '\0'; pCur++) {

		//决策结果为 pCur元素位于pCurrntStart位置 --水平决策
		char pTemp = *pCur;
		*pCur = *pCurrntStart;
		*pCurrntStart = pTemp;

		//pCurrntStart位置之后位置递归进行决策 --垂直决策
		PermutationCore(pAllStart, pCurrntStart + 1);

		//还原字符串  --水平决策复原
		pTemp = *pCur;
		*pCur = *pCurrntStart;
		*pCurrntStart = pTemp;

	}

}

2.

void PermutationCore(vector<char>& ori, vector<char>& pmt) {
	//base case
	if (ori.empty()) {
		//输出当前的全排列结果
		for (auto i : pmt) {
			cout << i << " ";
		}

		cout << endl;
	}

	//遍历字符串的每个元素 -- 保证作出所有可能的水平决策
	for (int i = 0; i < ori.size(); i++) {

		//将当前决策结果存放于pmt数组中去 --水平决策
		pmt.push_back(ori[i]);

		//为了确保在剩余元素中作出下次垂直决策，需要将当前元素暂时弹出，因为需要恢复，因此先暂存
		char temp = ori[i];
		ori.erase(ori.begin() + i);

		//对已决策的下一个位置作出元素决策 --垂直决策
		PermutationCore(ori, pmt);

		//还原  --水平决策复原
		ori.insert(ori.begin() + i, temp);
		pmt.pop_back();
	
	}
}

39.2 字符串的组合

输入一个字符串,打印出该字符串中字符的所有组合

Testing case

• 功能测试(字符串有一个或多个字符，字符串中存在值相同的元素)
• 边界测试(nullptr,字符串为空)

Key

• 分治 + 决策树 + 递归

  1. 辅助接口函数完成n次子问题的循环，从求长度为1的组合开始一直至长度为n的组合
  2. 对当前指针指向的字符进行决策
  3. 若含当前元素，则将当前元素压入组合数组，并递归在剩余元素中求长度为 k-1 的元素组合
  4. 若不含当前元素，则递归在剩余元素中求长度为 k 的元素组合
  5. 在进行4之前需要对组合数组进行复原
  6. 直至组合数组中的元素达到要求的元素长度k，即k=0时，终止递归

  注意:

  1. n个字符串的左右组合问题可以拆解为n次 m个元素中找寻长度为k的元素组合 k=1,2,…,n
  2. 决策树的分支为2，两种选择分别为k长度的组合中含/不含当前元素
  3. 两种决策必须均作出，因此不可以使用if-else进行决策

Answer

void Combination(char* arr) {
	//异常判断
	if (arr == nullptr) {
		return;
	}

	//将n个元素的所有组合拆解为求n次 mlen个元素中长度为k的组合
	char *len = arr;
	int mlen = 0;
	vector<char> comb;

	for (; *len != '\0'; len++) {
		mlen++;
	}

	for (int k = 1; k <= mlen; k++) {
		CombinationCore(arr, k, comb);
	}
}

void CombinationCore(char* str, int k, vector<char>& comb) {
	//base case
	if (k == 0) {
		//输出组合结果
		for (auto i : comb) {
			cout << i << " ";
		}

		cout << endl;
		return;
	}

	if (*str == '\0') {
		return;
	}

	//对str中的每个元素进行决策 长度为k的组合是否含有当前元素
	//yes k个元素组合中含当前元素
	comb.push_back(*str);
	//在str剩余元素中取k-1个元素进行组合
	CombinationCore(str + 1, k - 1, comb);

	//在进行同层结果为no的决策前，需要恢复
	comb.pop_back();

	//no k个元素组合中不含当前元素
	//在str剩余元素中取k个元素进行组合
	CombinationCore(str + 1, k, comb);
}

39.3 8皇后摆法问题

在8x8的国际象棋上摆放8个皇后,使其不能相互攻击,即任意两,个皇后不得处在同一行、同一列或者同一条对角线上

请问总共有多少种符合条件的摆法？

Testing case

• 功能测试(整数数组长度为8)
• 边界测试(nullptr)

Key

• 全排列 + 筛选

  1. 使用长度为8的数组代表8个皇后的位置 (i,ColIndex[i]) 并为其初始化为0 - 7，角标 i 表示行，数组元素 ColIndex[i] 表示 i 列
  2. 对ColIndex数组各元素进行全排列，将各元素的所有列排列情况列出
  3. 选取不在同一行，同一列，同一对角线的排列进行输出并计数

  注意:

  1. 因为使用了不同的下标表示8个皇后的行数，因此8个皇后此条件下一定不在同一行
  2. 因为使用了不同的元素初始化ColIndex数组，因此8个皇后此条件下一定不在同一列
  3. 在同一对角线 i - j == ColIndex[i] - ColIndex[j] || j - i == ColIndex[i] - ColIndex[j]

Answer

//记录符合条件的摆法
int Num = 0;

bool SameCheck(int* str, int len) {

	//判断是否存在同行，同列，同对角线的元素
	//双重循环时i，j必然不会相同，因此在于判断两元素是否在同一个对角线上
	for (int i = 0; i < len; i++) {
		for (int j = i + 1; j < len; j++) {
			if (i - j == str[i] - str[j] || j - i == str[i] - str[j]) {
				return false;
			}
		}
	}

	return true;
}

void EightQueen(int* arr,int QueenNum) {
	//异常判断
	if (arr == nullptr) {
		return;
	}
	EightQueenCore(arr, arr, QueenNum);
}

void EightQueenCore(int* pAllStart, int* pCurrntStart, int len) {
	//base case
	//len为进行全排列的整数数目，当len减至0时，代表已将len长度的所有整数进行了全排列
	if (len == 0) {
		 
		if (SameCheck(pAllStart, pCurrntStart - pAllStart))
		{
			Num++;
			int* pStart = pAllStart;
			cout << Num << endl;
			for (; pStart < pCurrntStart; pStart++) {
				cout << *pStart << " ";
			}
			cout << endl;
		}
	}

	//遍历字符串的每个元素 -- 保证作出所有可能的水平决策
	int i = 0;
	for (int* pCur = pCurrntStart; i < len; pCur++, i++) {

		//决策结果为 pCur元素位于pCurrntStart位置 --水平决策

		int pTemp = *pCur;
		*pCur = *pCurrntStart;
		*pCurrntStart = pTemp;

		//pCurrntStart位置之后位置递归进行决策 --垂直决策
		EightQueenCore(pAllStart, pCurrntStart + 1, len - 1);

		//还原字符串  --水平决策复原
		pTemp = *pCur;
		*pCur = *pCurrntStart;
		*pCurrntStart = pTemp;

	}

}

39.4 正方体顶点数分布

输入一个含有8个数字的数组,判断有没有可能把这8个数字分别,放到正方体的8个顶点上

使得正方体上三组相对的面上的4个顶点的和都相等

Testing case

• 功能测试(整数数组长度为8)
• 边界测试(nullptr)

Key

• 全排列 + 筛选

  1. 对传入的数组元素进行全排列
  2. 对全排列的结果进行筛选，若满足条件，则对分布情况进行输出

  注意:

  1. 8个数字满足分布于正方体上的条件 a1+a2+a3+a4 == a5+a6+a7+a8 && a1+a3+a5+a7 == a2+a4+a6+a8 && a1+a2+a5+a6 == a3+a4+a7+a8

40 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字

若不存在此数字则视为异常

Testing case

• 功能测试(数组中 存在/不存在 次数超过一半的数字)
• 边界测试(nullptr，只有一个数字)

Key

• 排序后遍历计数 O(n) = nlogn

• 中位数 + 快排 O(n) = n

  1. 对数组进行快排划分，并记录返回的基数位置
  2. 若该基数位置不等于数组中位数位置 len >> 1(len / 2)，则继续在基数左/右继续划分记录基数位置
  3. 若基数位置大于数组中位数位置 len >> 1(len / 2)，则在基数左边的数字中寻找中位数位置
  4. 若基数位置小于数组中位数位置 len >> 1(len / 2)，则在基数右边的数字中寻找中位数位置
  5. 直至基数的位置等于数组中位数的位置，进一步判断该基数是否为要求数字

  注意:

  1. 若数组中存在出现次数超过一半的数字，则该数字一定是数组的中位数
  2. 1的逆命题并不成立，在得到数组的中位数后应进一步判断是否为要求数

• 打擂 可能数字 -> 确切数字 O(n) = n

  1. 设置result擂主与coefficient可能系数，遍历数组开始打擂
  2. 若下一个元素等于该result，则擂主可能系数加1，否则，擂主可能系数减一
  3. 若擂主系数减至0，则代表当前擂主不可能为要求数字，更换擂主并同时更新coefficient为1
  4. 最终得到最可能成为要求数字的擂主后进行最终遍历计数判断即可

  注意:

  1. 数组中出现次数超过一半的数字只能有一个
  2. coefficient可能系数并不代表result的出现次数，而是其成为要求数字的可能系数
  3. 若存在要求数字，则该数字一定是擂主并最终coefficient>=1，但是若擂主最终coefficient>=1，其不一定是要求数字，因此最后需要在此判断是否为要求数字

Answer

1.

int MedianMoreThanHalf(int* arr, int len) {
	//异常判断
	if (IsValidInput(arr, len)) {
		isExcption = true;
		return 0;
	}

	//记录数组的中位数位置
	int median = len >> 1;

	//获取当前快排划分得到的基数位置
	int start = 0;
	int end = len - 1;
	int pivot = Partition(arr, len, start, end);

	//若此基数位置不为中位数，则在划分后的数中进而求基数位置直到基数位置等于median
	while (median != pivot) {
		if (pivot > median) {
			//在基数左边的数字中寻找
			end = pivot - 1;
			pivot = Partition(arr, len, start, end);
		}
		else {
			//在基数右边的数字中寻找
			start = pivot + 1;
			pivot = Partition(arr, len, start, end);
		}
	}

	//此时基数位置即为中位数位置，该基数可能为要求数，进一步判断
	int result = arr[pivot];

	if (!IsMoreThanHalf(arr, len, result)) {
		isExcption = true;
		result = 0;
	}

	return result;
}

int Partition(int* arr, int len, int start, int end) {
	//异常判断
	if (arr == nullptr || len <= 0 || start < 0 || end >= len) {
		isExcption = true;
		return 0;
	}

	//设置small时刻指向当前最后一个比small小的元素
	int small = start - 1;
	//数组某位暂存pivot基数 默认取start元素，此处并未随机

	int pivot = arr[start];
		
	int temp = arr[start];
	arr[start] = arr[end];
	arr[end] = temp;	

	//遍历数组，以基数为基准进行划分
	for (int index = start; index < end; index++) {
		//若遍历元素比pivot基数小，则small后移，否则不作处理
		if (arr[index] < pivot) {

			small++;
			//若遇到比pivot大的元素后又遇到比pivot小的元素，则small++后交换这两个元素位置
			if (index != small) {
				int temp = arr[index];
				arr[index] = arr[small];
				arr[small] = temp;
			}
		
		}
	}

	//将small指针指向pivot基数应存放位置
	small++;

	//交换基数与第一个比其大的元素
	temp = arr[small];
	arr[small] = arr[end];
	arr[end] = temp;

	return small;
}

2.

>bool IsMoreThanHalf(int* arr, int len, int result) {

	//设置bool变量返回值
	bool isMoreThanHalf = false;

	//记录result在数组中的出现次数
	int num = 0;
	for (int i = 0; i < len; i++) {
		if (arr[i] == result) {
			num++;
		}
	}

	//设置全局异常判断变量初始为true
	isExcption = true;

	if (num > (len / 2)) {

		isExcption = false;
		isMoreThanHalf = true;
	}

	return isMoreThanHalf;
}

bool IsValidInput(int* arr, int len) {
	bool isExc = false;
	if (arr == nullptr || len <= 0) {
		isExc = true;
	}
	return isExc;
}

int LikelyMoreThanHalf(int* arr, int len) {
	//异常判断
	if (IsValidInput(arr, len)) {
		isExcption = true;
		return 0;
	}

	//设置变量记录可能数字
	int result = arr[0];
	//设置其可能系数
	int coefficient = 1;

	//挑选出数组中最可能成为result的数字
	for (int i = 0; i < len; i++) {
		if (coefficient == 0) {

			//若此系数减弱至0，则表示该数字不可能为终值，切换至下一个值		
			result = arr[i];
			//重新设置系数为1
			coefficient = 1;

		}
		else if (result == arr[i]) {
			//系数增强
			coefficient++;
		}
		else {
			//系数减弱
			coefficient--;
		}
	}

	//检查result是否为终值
	if (!IsMoreThanHalf(arr, len, result)) {
		isExcption = true;
		result = 0;
	}

	return result;
}

41 最小的k个数

输入n个整数,找出其中最小的k个数

Testing case

• 功能测试(数组中有相同数字，数组中无相同数字)
• 边界测试(nullptr，k<=1，k>=数组长度)

Key

• 快排划分 T(n) = O(n)

  1. 对数组进行快排划分，并记录返回的基数的位置
  2. 若该基数位置不等于 k - 1，则继续在基数左/右继续划分记录基数位置
  3. 若基数位置大于 k - 1，则在基数左边的数字中寻找划分后基准位置为 k - 1 的划分
  4. 若基数位置小于 k - 1，则在基数右边的数字中寻找划分后基准位置为 k - 1 的划分
  5. 直至基数的位置等于 k - 1，对该基准左边的数字(含该基准)进行输出

  注意:

  1. 若快排划分后的基准位置即第k位，则该基准左边的数字(含该基准)即为最小的k个数
  2. 划分将导致原数组被修改

• 红黑树 / 堆 T(n) = O(nlogk)

  1. 对于输入的元素，若容器大小小于k，则直接压入容器
  2. 否则判断当前输入元素与容器中最大元素的大小
  3. 若输入元素小，则替换当前容器最大元素，否则，跳过该输入元素
  4. 直至遍历完输入元素容器

  注意:

  1. 大顶堆或者红黑树结构可以O(1)复杂度取得最大元素，O(logn)复杂度插入删除元素
  2. 适合用于数据庞大或者无法一次载入内存的情形

Answer

1.

int Partition(int* arr, int len, int start, int end) {
	//异常判断
	if (arr == nullptr || len <= 0 || start < 0 || end >= len) {
		isExcption = true;
		return 0;
	}

	//设置small时刻指向当前最后一个比small小的元素
	int small = start - 1;
	//数组某位暂存pivot基数 默认取start元素，此处并未随机

	int pivot = arr[start];

	int temp = arr[start];
	arr[start] = arr[end];
	arr[end] = temp;

	//遍历数组，以基数为基准进行划分
	for (int index = start; index < end; index++) {
		//若遍历元素比pivot基数小，则small后移，否则不作处理
		if (arr[index] < pivot) {

			small++;
			//若遇到比pivot大的元素后又遇到比pivot小的元素，则small++后交换这两个元素位置
			if (index != small) {
				int temp = arr[index];
				arr[index] = arr[small];
				arr[small] = temp;
			}

		}
	}

	//将small指针指向pivot基数应存放位置
	small++;

	//交换基数与第一个比其大的元素
	temp = arr[small];
	arr[small] = arr[end];
	arr[end] = temp;

	return small;
}

void GetLeastNumbers(int* input, int len, int* output, int k) {
	//异常判断
	if (input == nullptr || len < 0 || k > len || k < 0) {
		isExcption = true;
		return;
	}

	//基于快排划分找到划分基准为 k-1 的划分结果
	int start = 0;
	int end = len - 1;
	int index = Partition(input, len, start, end);

	while (index != k - 1) {
		if (index > k - 1) {
			end = index - 1;
			index = Partition(input, len, start, end);
		}
		else {
			start = index + 1;
			index = Partition(input, len, start, end);
		}
	}

	//将划分后的前k个元素存入输出数组
	for (int i = 0; i < k; i++) {
		output[i] = input[i];
	}

}

2.

void GetLeastNumbersByRB(const vector<int>& data, SetType& store, int k) {
	//异常判断
	if (data.size() == 0 || k < 0 || k > data.size()) {
		isExcption = true;
		return;
	}

	//遍历输入数组，将前k大的元素存入到store容器中
	vector<int>::const_iterator ite = data.begin();
	for (; ite < data.end(); ite++) {
		//若容器元素未满k个，则直接插入
		if (store.size() < k) {
			store.insert(*ite);
		}
		else {
			//若满k个且当前输入元素小于红黑树根结点，则替换掉该根节点
			if (*ite < *store.begin()) {
				store.erase(*(store.begin()));
				store.insert(*ite);
			}
		}
	}
}

42 数据流中的中位数

如何得到一个数据流中的中位数

如果从数据流中读出奇数个数1值,那么中位数就是所有数值排序之后位于中间的数值

如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值

Testing case

• 功能测试(数据流中有奇数/偶数个数字)
• 边界测试(数据流中无数字)

Key

• 快排划分 O(1) 插入 O(n) 中位数

• 排序数组 O(n) 插入 O(1) 中位数

• 排序链表 O(n)插入 O(1) 中位数

• 二叉搜索树 O(logn) - O(n) 插入 O(logn) - O(n) 中位数

• AVL树 O(logn) 插入 O(1) 中位数

• 双堆 O(logn) 插入 O(1) 中位数

  1. 建立一个动态数组，动态数组底层为两个堆，一个是大顶堆，一个为小顶堆
  2. 每次向动态数组中压入数字时，若目前动态数组中的元素个数为偶数(0)，则压入到min堆，保证数据流中数字的均匀分配
  3. 若压入min堆时，max不为空，则应先于max堆顶元素比较，若小于max堆顶元素，则将max堆顶元素压入min堆，当前元素压入max堆
  4. 若目前动态数组中的元素个数为奇数，则压入到max堆
  5. 若压入max堆时，min不为空，则应先于min堆顶元素比较，若大于min堆顶元素，则将min堆顶元素压入max堆，当前元素压入min堆

  -

  1. 求中位数时若当前动态数组元素个数为奇数，则返回min堆堆顶
  2. 否则返回 ( max[0] + min[0] ) / 2

  Answer

  注意:

  1. 中位数将整个数组划分为两部分，这两部分有如下特点
     • 左边部分的数字均比右边部分的数字小
     • 左边部分数字个数与右边数字个数相差不超过1
     • 中位数为左边部分最大值/右边部分最小值/两者的平均值
  2. 如果压入时动态数组中元素个数为偶数，则压入到min堆，否则压入到max堆，保证数据流中数字的均匀分配
  3. 选择DynamicArray封装当前数据流中的数据
  4. push_heap,pop_heap 的操作对象必须为已经形成的堆
  5. push_heap应确保元素已经压入堆中
  6. pop_heap并不会弹出堆顶元素，只要将堆顶元素与堆尾元素交换，徐亚使用pop_back弹出

Answer

bool isExcption = false;

template <class T>
class DynamicArray {
public:
	DynamicArray() = default;
	~DynamicArray() = default;

	void Insert(T num);
	double GetMedian();
private:
	vector<T> max;
	vector<T> min;
};
	
template <class T>
void DynamicArray<T>::Insert(T num) {
	//如果压入时动态数组中元素个数为偶数，则压入到min堆，否则压入到max堆，保证数据流的均匀分配
	if (((max.size() + min.size()) & 1) == 0) {
		//若压入的元素比max堆中的最大元素大，则需要将该元素压入max堆并将max堆中最大元素压入min堆

		if (max.size() > 0 && num < max[0]) {

			//将当前元素压入到max堆中
			max.push_back(num);
			push_heap(max.begin(), max.end(), less<T>());
			num = max[0];

			pop_heap(max.begin(), max.end(), less<T>());
			max.pop_back();
		}

		min.push_back(num);
		push_heap(min.begin(), min.end(), greater<T>());
	}
	else {
		//如果压入时动态数组中元素个数为奇数，则压入到max堆
		//若压入的元素比min堆中的最小大，则需要将该元素压入min堆并将min堆中最小元素压入max堆
		if (min.size() > 0 && num > min[0]) {

			//将当前元素压入到max堆中
			min.push_back(num);
			push_heap(min.begin(), min.end(), greater<T>());

			num = min[0];

			pop_heap(min.begin(), min.end(), greater<T>());
			min.pop_back();
		}

		max.push_back(num);
		push_heap(max.begin(), max.end(), less<T>());
	}
}

template <class T>
double DynamicArray<T>::GetMedian() {

	//判断异常
	int size = max.size() + min.size();
	if (size == 0) {
		isExcption = true;
		return 0;
	}
	
	T median;

	if ((size & 1) == 0) {
		median = (max[0] + min[0]) / 2;
	}
	else {
		median = min[0];
	}

	return median;
}

—- 堆 —-

Interfaces

• make_heap(start_ite,end_ite,functor)

  对于给定的范围元素生成堆，默认为大顶堆

  start_ite: 指向开始元素的迭代器

  end_ite: 指向末尾元素的迭代器

  functor: greater< T >() - 小顶堆, less< T >() - 大顶堆

• push_heap(start_ite,end_ite,functor)

  在堆的基础上进行数据的插入，本身不会有数据插入操作，须确保数据已经插入后再作堆调整

  start_ite: 指向开始元素的迭代器

  end_ite: 指向末尾元素的迭代器

  functor: greater< T >() - 小顶堆, less< T >() - 大顶堆

• pop_heap(start_ite,end_ite,functor)

  在堆的基础上进行堆顶的弹出，本身不会有数据弹出操作，仅仅是将堆顶元素与堆尾元素进行了交换

  start_ite: 指向开始元素的迭代器

  end_ite: 指向末尾元素的迭代器

  functor: greater< T >() - 小顶堆, less< T >() - 大顶堆

43 连续子数组的最大和

输入一个整型数组,数组里有正数也有负数，数组中的一个或连续多个整数组成一个子数组

求所有子数组的和的最大值

要求时间复杂度为0(n)。

Testing case

• 功能测试(输入的数组有正数有负数，全是正数，全是负数)
• 边界测试(nullptr)

Key

• 动态规划 T(n) = O(n)

  1. 正向迭代计算由f(0)至f(len-1)，并记录当前元素作连续子数组末尾时的最大和currentSum
  2. 使用打擂法计算 len 个元素的数组中的连续子数组的最大和MaxNum

  注意:

  1. 连续子数组的最大和是数组某个元素作连续子数组末尾元素时的最大和
  2. 只需求出每个元素作连续子数组末尾元素时的最大和并记录最大值即可
  3. 递归分析可得第 i 个元素作连续子数组末尾元素时的最大和为，记为f(i)
     • a(i) — f(i - 1) <= 0 || i = 0
     • a(i) + f(i) — f(i - 1) > 0 && i > 0

Answer

int GetGreatestNum(int* arr, int len) {

	//异常判断
	if (arr == nullptr || len <= 0) {
		isExcption = true;
		return 0;
	}

	//记录第 i-1 元素为尾的最大子数组的和
	int currentSum = 0;
	//记录最大子数组的和
	int MaxNum = arr[0];
	//正向迭代 求i元素为尾的最大子数组和
	for (int i = 0; i < len; i++) {
		if (currentSum <= 0) {
			//如果第 i-1 元素为尾的最大子数组和小于等于0，则舍弃之前元素，当前元素构成的子数组和即为当前位置的最大和
			currentSum = arr[i];
		}
		else {
			//如果第 i-1 元素为尾的最大子数组和大于0，则累加
			currentSum += arr[i];
		}

		//打擂记录最大子数组和
		if (currentSum >= MaxNum) {
			MaxNum = currentSum;
		}

	}

	return MaxNum;
}

44 1-n 整数中1出现的次数 —跳过

Testing case

• 功能测试(输入的数组有正数有负数，全是正数，全是负数)
• 边界测试(nullptr)

Key

Answer

45 数字序列中的某一位数字

数字以0123456789101112131415 的格式序列化到一个字符序列中

在这个序列中,第5位(从0开始计数)是5,第13位是1,第19位是4,等等

请写一个函数,求任意第n位对应的数字

Testing case

• 功能测试(10,190,1000等)
• 边界测试(0,1)

Key

• 穷举遍历数字

  1. 从数字1开始向下遍历，每次记录当前位数总数并与输入n进行比较
  2. 若小于等于n，则说明第n位在此数字所在序列中的位数之后，向下遍历
  3. 若大于n，则说明第n位数字在序列中的位置位于此数字之间
  4. 进而在此数字中根据偏移量找到最终的某一位数字

• 跳级定位范围

  1. 从1位数开始判断第n位数字所在的位数范围，将n不断与m位数的所有数字包含的位数作比较
  2. 若n<m，则表示第n位数字所在的数为m位数，否则继续向后循环判断
  3. 锁定所在位数范围后，根据该m位数的首位数字与偏移量求得第n位数字所在的数字
  4. 进而在此数字中根据偏移量找到最终的某一位数字

  注意:

  1. 数字序列排列递增有序，依次为所有一位数，二位数……..
  2. 不再穷举遍历定位所在的数字，而是先定位其位于哪一个位数范围内，进而定位位于该位数范围内的那个数中，再根据偏移量的最终数字
  3. 由于是从0开始计数，因此范围定位时注意条件是否能等于
  4. 各子功能分模块，防止代码冗余

Answer

bool isExcption = false;

int GetNum(int);
int GetDiditNums(int);
int GetNumCore(int, int);
int GetHead(int);

int GetHead(int digit) {
	if (digit == 1) {
		return 0;
	}
	else {
		return (int)(pow(10, digit - 1));
	}
}

int GetNumCore(int index, int digit) {
	//获取digit位数的首位数字
	int NumHead = GetHead(digit);
	//判断index位数位于哪个数字子序列中
	int indexInNum = NumHead + index / digit;
	//判断index位数于indexInNum子序列中相对于右侧的偏移量
	int offSetRight = digit - index % digit - 1;
	//取终值index数
	for (int i = 0; i < offSetRight; i++) {
		indexInNum /= 10;
	}

	return indexInNum % 10;
}

int GetDiditNums(int digit) {
	if (digit == 1) {
		return 10;
	}
	else {
		return 9 * (int)(pow(10, digit - 1));
	}

}

int GetNum(int index) {
	//异常判断
	//多测试环境下需复原
	isExcption = false;

	if (index < 0) {
		isExcption = true;
		return 0;
	}

	//范围筛选位于某位数范围中
	int digit = 1;
	while (true) {
		//从1位数开始锁定n位数字所在的位数范围
		int digitNums = GetDiditNums(digit);
		if (index < digitNums * digit) {
			//锁定n位的数在digit位数范围内
			return GetNumCore(index, digit);
		}
		//n位的数不在digit位数的范围内，向下遍历
		index -= digitNums * digit;
		digit++;
	}
}

46 把数组排成最小的数

输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个

Testing case

• 功能测试(数组只有一个数字，含多个数字，数字相同，数字位数相同)
• 边界测试(nullptr)

Key

• 全排列筛选

  将整型数组中的元素进行全排列后求得最小的拼接数

  注意:

  1. n个数字的全排列数为 n!
  2. 元素在int型的范围内，但是拼接后的元素不一定在int范围内，隐含大数问题，需要使用字符串进行拼接运算并比较大小

• “排序”的二维字符数组

  1. 将整型数组中的数字元素转存至二维字符数组中
  2. 对二维字符数组一维度的每个数字字符串进行排序，按照自定义的字符串比较大小方法
  3. 对排序后的二维字符数组按序输出即可

  注意:

  1. 考虑到大数问题，由数字字符串的拼接代替整数拼接比较大小进而判断两个数字字符串的排序顺序
  2. sprintf(str, “%d”, intNum);将intNum整数打印成字符串保存于str字符串中
  3. void qsort( void *base, size_t nmemb, size_t size, int (compare)(const void *, const void *) ); 将元素大小为size，元素个数为nmemb的base按照compare规则进行排序 T(n) = O(nlogn)

Answer

bool isExcption = false;

//设置全局拼接数暂存字符串
int MaxLen = 10;
char* PlusOne = new char[MaxLen * 2 + 1];
char* PlusTwo = new char[MaxLen * 2 + 1];

int Compare(const void*, const void*);
void SortMinNum(int*, int);

//比较规则
int Compare(const void* strNum1, const void* strNum2) {
	//拼接后字符串PlusOne strNum1在前，strNum2在后																				//*(char**)strNum1为取字符串首部取整个字符串而非某个字符
	strcpy(PlusOne, *(char**)strNum1);
	strcat(PlusOne, *(char**)strNum2);

	//拼接后字符串PlusTwo strNum2在前，strNum1在后
	strcpy(PlusTwo, *(char**)strNum2);
	strcat(PlusTwo, *(char**)strNum1);

	//若返回值小于0 strNum1在前，大于0 strNum1在后，等于0 无法确定
	return strcmp(PlusOne, PlusTwo);
}

void SortMinNum(int* intNum, int len) {
	//异常判断
	if (intNum == nullptr || len <= 0) {
		isExcption = true;
		return;
	}

	//将整数数组元素存于二维字符数组中																							//动态创建二维字符数组									
	char** strNum = new char* [len];

	for (int i = 0; i < len; i++) {
		strNum[i] = new char[MaxLen + 1];
		//将整数输入到字符串中
		sprintf(strNum[i], "%d", intNum[i]);
	}

	//对该二维字符数组进行排序
	qsort(strNum, len, sizeof(char*), Compare);

	//输出拼接后的最小数字
	cout << "最小数字:" << endl;

	for (int i = 0; i < len; i++) {
		cout << strNum[i];
	}

	//内存回收
	for (int i = 0; i < len; i++) {
		delete[] strNum[i];
	}

	delete strNum;
}

47 把数字翻译成字符串

给定一个数字,我们按照如下规则把它翻译为字符串: 0翻译成“a”, 1翻译成”b”, …, 11翻译成”l”,…., 25翻译成“z”

一个数字可能有多个翻译,请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法

Testing case

• 功能测试()
• 边界测试(nullptr)

Key

• 自上而下递归

  1. 从首元素开始决策当前元素是否与后一个元素拼接
  2. 若不拼接，则 count += f(i + 1)
  3. 若拼接，则判断是否可拼接
  4. 若可拼接且不是倒数第二个元素，count += f(i + 2)，若是倒数第二个元素， count += 1
  5. 若不可拼接，则跳过
  6. 直至进行最后一个元素的决策，返回1

  注意:

  1. 记第i个位置可翻译的字符串数为f(i),则

     f(i) = 1 i元素为末尾元素

     f(i) = f(i + 1) i元素与i+1元素拼接结果不位于10-25之间

     f(i) = f(i + 1) + 1 i元素与i+1元素拼接结果位于10-25之间，但是为倒数第二个元素

     f(i) = f(i + 1) + f(i + 2) i元素与i+1元素拼接结果位于10-25之间

  2. 递归操作含多次重复操作

  3. 使用指针更方便拆分字符串

• 自下而上动态规划

  1. 从末尾元素计算可翻译的字符串数并记录当前结果
  2. 向前遍历，遍历同时计算当前元素作首元素可翻译的字符串数
  3. 直至遍历至首元素，得最终数字可翻译的字符串数

  注意:

  1. 使用数组记录结果，因为数组角标可对应当前正遍历的元素
  2. 判断涉及是否为末尾元素，是否可拼接，若可拼接则该元素是否为倒数第二个元素
  3. to_string(int) 可将一整数转换为字符串

Answer

1.

bool Concat(char cnum1, char cnum2) {

	bool result = false;

	int num1 = cnum1 - '0';
	int num2 = cnum2 - '0';

	int concat = num1 * 10 + num2;

	if (concat >= 10 && concat <= 25) {
		result = true;
	}

	return result;
}

int RecursiveTranslationNums(int num) {
	//异常判断
	if (num < 0) {
		isExcption = true;
		return 0;
	}
	char arr[10];
	sprintf(arr, "%d", num);
	return RecursiveTranslationNumsCore(arr);
}

int RecursiveTranslationNumsCore(char* num) {
	//base case
	if ((*(num + 1)) == '\0') {
		return 1;
	}

	int count = 0;
	//当前元素不与后一个元素组合
	count += RecursiveTranslationNumsCore(num + 1);
	//当前元素与后一个元素组合
	if (Concat(*num, *(num + 1))) {
		if ((*(num + 2)) != '\0')
			count += RecursiveTranslationNumsCore(num + 2);
		else
			count += 1;
	}

	return count;
}

2.

bool Concat(char cnum1, char cnum2) {

	bool result = false;

	int num1 = cnum1 - '0';
	int num2 = cnum2 - '0';

	int concat = num1 * 10 + num2;

	if (concat >= 10 && concat <= 25) {
		result = true;
	}

	return result;
}

int TranslationNums(int num) {
	//异常判断
	if (num < 0) {
		isExcption = true;
		return 0;
	}
	string n = to_string(num);
	return TranslationNumsCore(n);
}

int TranslationNumsCore(const string& num) {
	//设置记录各个位置起可翻译的字符串数结果，避免重复计算
	int* counts = new int[num.length()];
	//设置记录从当前位置元素开始的可翻译字符串数
	int count = 0;

	//从后向前遍历字符串，直至计算出第一个位置起的可翻译字符串数
	for (int i = num.length() - 1; i >= 0; i--) {
		//清零，计算当前位置作起始位置的可翻译字符串数
		count = 0;
		//若当前元素为末尾元素，则只能翻译1种字符串
		if (i == num.length() - 1) {
			count += 1;
		}
		else {
			//否则当前元素作起始位置的可翻译字符串数等于下一个位置的结果
			count += counts[i + 1];
		}

		if (i != num.length() - 1) {
			//若不为末尾元素，判断当前元素能否与后一个元素拼接
			if (Concat(num[i], num[i + 1])) {
				//若可拼接但是当前元素为倒数第二个元素，则可翻译字符串数增1
				if (i == num.length() - 2) {
					count += 1;
				}
				else {
					count += counts[i + 2];
				}
			}
		}

		counts[i] = count;
	}

	//释放内存
	delete[] counts;

	return count;
}

48 礼物的最大价值

在一个m×n的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于0),你可以从棋盘的左上角开始拿格子里的礼物,并每次向左或者向下移动一格,直到到达棋盘的右下角

给定一个棋盘及其上面的礼物,请计算你最多能拿到多少价值的礼物?

Testing case

• 功能测试(多行多列矩阵，一行/列矩阵，只有一个数字的矩阵)
• 边界测试(nullptr)

Key

• 决策树 + 递归

  1. 从首元素开始进行决策，向下or向右
  2. 先进行向下的决策后对下方元素继续递归决策
  3. 后进行向右的决策后对友方元素继续递归决策
  4. 在作另一决策之前需要将当前决策恢复后再进行决策，但是注意恢复的位置
  5. 直至进行右下角元素的决策

  注意:

  1. 从左上角开始，找寻所有至有右下角的路径，并记录路径上的礼物价值，打擂求解并使用全局变量记录
  2. 二维数组中的起点确定的各元素路径遍历的边界值问题，若边界选取不当并未作处理，将导致边界值的重复决策
  3. 注意对边界只能作一种决策的处理，此处统一处理，末尾元素单独处理
  4. 恢复的位置若位于2,3之间，则在作出另一决策前，当前正作出决策的结点将被弹出，因此应该置于3之后，仅弹出左决策结点而非本身

• 递归公式 + 递归

  1. 从右下角开始套用公式递归计算返回结果

  注意:

  1. 记(i,j)位置处礼物的最大价值为f(i,j),(i,j)位置处礼物的价值为gift(i,j)

     f(i,j) = max(f(i-1,j),f(i,j-1)) + gift(i,j) , i!=0 && j!=0

     f(i,j) = f(i-1,j)+ gift(i,j) , j=0

     f(i,j) = f(i,j-1)+ gift(i,j) , i=0

     f(i,j) = gift(i,j) , i=j=0

• 动态规划 + 迭代计算

  1. 自左上角开始遍历整个礼物矩阵，计算每个位置的礼物最大价值
  2. 分别使用left,up记录当前位置的左边与上边的礼物最大价值
  3. 取max(left,up) + gift(i,j) 作为当前位置处的礼物最大价值

  注意:

  1. 使用二维数组记录相应位置处的礼物最大价值
  2. left,up初始化为0，考虑边界情况，需每次判断是否位于某个边界

Answer

1.

bool isExcption = false;
int MaxGift = 0;

int MaxValueOfGift(int**, int, int);
void MaxValueOfGiftCore(int**, int, int, int, int, vector<int>&);

int MaxValueOfGift(int** arr, int rows, int cols) {
	//异常判断
	if (arr == nullptr || rows <= 0 || cols <= 0) {
		isExcption = true;
		return 0;
	}

	vector<int> Gift;

	MaxValueOfGiftCore(arr, 0, 0, rows, cols, Gift);

	return MaxGift;
}

void MaxValueOfGiftCore(int** gift, int row, int col, int rows, int cols, vector<int>& Gift) {
	//base case
	if (row == rows - 1 && col == cols - 1) {

		Gift.push_back(gift[row][col]);

		int sum = 0;
		for (auto i : Gift) {
			cout << i << " ";
			sum += i;
		}
		if (sum >= MaxGift) {
			MaxGift = sum;
		}
		cout << "max = " << MaxGift;
		cout << endl;

		if (Gift.size() != 0)
			Gift.pop_back();

		return;
	}

	//将从左上角至右下角的一条路径经过的所有礼物进行记录
	//防止边界元素的重复压入

	Gift.push_back(gift[row][col]);
	
	//向下移动
	if (row < rows - 1) {
		//down = false;
		MaxValueOfGiftCore(gift, row + 1, col, rows, cols, Gift);
	}

	//向右移动
	if (col < cols - 1) {
		//right = false;
		MaxValueOfGiftCore(gift, row, col + 1, rows, cols, Gift);
	}

	//恢复
	if (Gift.size() != 0)
		Gift.pop_back();

}

2.

int MaxValueOfGiftByFunc(int** arr, int rows, int cols) {
	//异常判断
	if (arr == nullptr || rows <= 0 || cols <= 0) {
		isExcption = true;
		return 0;
	}

	int max = MaxValueOfGiftCoreByFunc(arr, rows - 1, cols - 1);

	return max;
}

int MaxValueOfGiftCoreByFunc(int** gift, int row, int col) {
	//base case
	if (row == 0 && col == 0) {
		return gift[row][col];
	}
	else if (row == 0) {
		return MaxValueOfGiftCoreByFunc(gift, row, col - 1) + gift[row][col];
	}
	else if (col == 0) {
		return MaxValueOfGiftCoreByFunc(gift, row - 1, col) + gift[row][col];
	}
	else {
		return max(MaxValueOfGiftCoreByFunc(gift, row - 1, col), MaxValueOfGiftCoreByFunc(gift, row, col - 1)) + gift[row][col];
	}
}

3.

int MaxValueOfGift(int** gift, int rows, int cols) {
	//异常判断
	if (gift == nullptr || rows <= 0 || cols <= 0) {
		isExcption = true;
		return 0;
	}

	//辅助二维数组记录各个位置处的礼物最大价值
	int** MaxValue = new int*[rows];
	for (int i = 0; i < rows; i++) {
		MaxValue[i] = new int[cols];
	}

	//自左上角开始遍历，计算各个位置处的礼物最大价值
	for (int i = 0; i < rows; i++) {
		for (int j = 0; j < cols; j++) {
			
			//设置记录当前位置左边与上边礼物最大价值的变量
			int up = 0;
			int left = 0;

			if (i > 0)
				up = MaxValue[i - 1][j];
			if (j > 0)
				left = MaxValue[i][j - 1];

			//设置当前位置的礼物最大价值
			MaxValue[i][j] = max(up, left) + gift[i][j];

		}
	}

	int max = MaxValue[rows - 1][cols - 1];

	//释放内存
	for(int i = 0; i < rows; i++) {
		delete[] MaxValue[i];
	}

	delete[] MaxValue;

	return max;
}

49 最长不含重复字符的子字符串

请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度

假设字符串中只包含a~z的字符

Testing case

• 功能测试(字符串含多个字符，字符均相同，仅含一个字符)
• 边界测试(字符串为空)

Key

• 暴力求解 T(n) = O(n3)

  1. 求解字符串的所有连续的子字符串 O(n2)
  2. 在所有子字符串中找寻并记录最长不含重复字符的子字符串 O(n)

• 动态规划 + 正向迭代

  1. 自首部开始遍历字符串，计算以 i(0,1..str.length()) 处元素作尾部元素时的最长不含重复字符的子字符串
  2. 每次遍历记录当前以i为末尾不含重复字符的子字符串的长度，并记录当前元素本次在str中出现的位置
  3. 当currentSubLen发生截断前打擂判断maxSum
  4. 直至 i=str.length()，最后打擂判断maxSum

  注意:

  1. 最长不含重复字符的子字符串为连续的字符串

  2. 入手点在于分析i处元素作该连续字符串末尾时的最长长度，i取值由 0->str.length() 即可得出当前长度的字符串的最长不含重复字符的子字符串

  3. 记f(i)为i处元素作该连续字符串末尾时的最长长度，则

     f(i) = f(i-1) + 1 , f(i-1)对应的子字符串中不含i处元素(LastAppear[index] < 0 || distance > currentSubLen)

     f(i) = distance , 对应的子字符串中含i处元素

     distance为截断i处元素上一次出现位置到i所包含的所有元素

  4. 使用 currentSubLen 来记录 f(i-1)

Answer

bool isExcption = false;

int LongestSubstrWithoutDuplication(const string&);

int LongestSubstrWithoutDuplication(const string& str) {
	//异常判断
	if (str.length() == 0 ) {
		isExcption = true;
		return 0;
	}

	//设置LastAppear数组记录'a'-'z'字符上一次在字符串中出现的位置，若当前未出现，则为-1
	int* LastAppear = new int[26];
	for (int i = 0; i < 26; i++) {
		LastAppear[i] = -1;
	}

	//设置currentSum存储f(i-1)的值
	int currentSubLen = 0;
	//设置maxSum打擂存储最长字符串
	int maxSum = 0;

	//自前向后求得目前第i个元素作满足要求的子字符串末尾时的最长长度
	for (int i = 0; i < str.length(); i++) {
		//判断当前元素是否位于f(i-1)对应的子字符串中

		//获取当前遍历元素在LastAppear数组中的映射关系,从而获取当前元素上次在str中出现的位置
		int index = str[i] - 'a';
		//获取当前元素与上一次出现位置的差值
		int distance;

		if(LastAppear[index] >= 0)
			distance = i - LastAppear[index];

		if (LastAppear[index] < 0 || distance > currentSubLen) {
			//若之前最长子字符串中不含当前位置字符，则子字符串长度增1
			currentSubLen += 1;
		}
		else {
			//若之前最长子字符串中含当前位置字符，则存在重复，需要截断上一次出现位置以及之前的元素
			//此时maxSum才需要更新
			if (currentSubLen >= maxSum) {
				maxSum = currentSubLen;
			}
			currentSubLen = distance;
		}

		//记录当前元素本次在str出现的位置
		LastAppear[index] = i;

	}

	//最后更新maxSum，记录最长不含重复字符的子字符串
	if (currentSubLen >= maxSum) {
		maxSum = currentSubLen;
	}

	//清理内存
	delete[] LastAppear;

	return maxSum;
}

—- 动态规划 —-

• 求解某个问题的最优解(最大，最小，最多有…)
• 某个问题可划分为多个子问题
• 多个子问题有相互重叠的更小的子问题
• 自上而下递归分析问题，自下而上迭代解决问题(记录上次结果)

50 丑数

我们把只包含因子2、3和5的数称作丑数(Ugly Number)

求1按从小到大的顺序的第1500个丑数

我们把1当作第一个丑数。

Testing case

• 功能测试(2,3,4,5,6)
• 边界测试(1,0)
• 性能测试(1500)

Key

• 暴力遍历所有数

  1. 从1开始遍历所有正整数，并判断是否为丑数
  2. 若为丑数则丑数计数器增1
  3. 直至找到第1500个丑数

  注意:

  1. 若一个数为丑数，则其将2,3,5因子均除尽之后值为1.
  2. 需要遍历第1500个丑数之前的所有数字

• 使用数组仅记录所有丑数

  1. 使用一个数组递增有序记录前num个丑数
  2. 设置三个标志指针分别记录第一个 ×2，×3，×5 大于目前最大丑数的丑数元素，初始化为数组首元素
  3. 取min(*Multiply2 * 2, *Multiply3 * 3, *Multiply5 * 5),作为下一个丑数
  4. 更新三个标志指针指向
  5. 向下遍历，直至丑数数组元素满num个，即得出第num个丑数

  注意:

  1. 使用大小为num的数组递增有序存放所有丑数，最后一个元素即为第num个丑数
  2. 一个丑数一定由之前某丑数乘某个因子(2,3,5)得之,1除外
  3. 为使数组有序，需要三个指针分别记录第一个 ×2，×3，×5 大于目前最大丑数的丑数元素
  4. 使用丑数数组记录前num个丑数可省去记录其余无关整数，但是增加了空间消耗

Answer

1.

bool isUglyNum(int num) {
	//丑数只含有2,3,5因子，将每个因子除尽若为1则为丑数
	while (num % 2 == 0) {
		num /= 2;
	}
	while (num % 3 == 0) {
		num /= 3;
	}
	while (num % 5 == 0) {
		num /= 5;
	}

	if (num == 1) {
		return true;
	}
	else {
		return false;
	}
}

int getUglyNum(int num) {
	//异常判断
	if (num <= 0) {
		isExcption = true;
		return 0;
	}

	//记录当前数字与丑数
	int number = 0;
	int uglyNum = 0;

	while (uglyNum < num) {
		//遍历自1开始的数字
		number++;

		if (isUglyNum(number)) {
			uglyNum++;
		}		
	}

	return number;
}

2.

int getMin(int n1, int n2, int n3) {
	int min;
	if (n1 < n2) {
		min = n1;
	}
	else {
		min = n2;
	}
	if (n3 < min) {
		min = n3;
	}

	return min;
}

int getUglyNum2(int num) {
	//异常判断
	if (num <= 0) {
		isExcption = true;
		return 0;
	}

	//设置由小到大排序的丑数数组
	int* Ugly = new int[num];
	Ugly[0] = 1;

	//三个标志指针，分别指向第一个 ×2，×3，×5 大于目前最大丑数的丑数元素
	int* Multiply2 = Ugly;
	int* Multiply3 = Ugly;
	int* Multiply5 = Ugly;

	//设置指向下一个丑数的角标标志,用于遍历记录前num个丑数
	int pNextUgly = 1;

	while (pNextUgly < num) {
		//获取当前最大丑数
		int min = getMin(*Multiply2 * 2, *Multiply3 * 3, *Multiply5 * 5);
		Ugly[pNextUgly] = min;

		//重新定位三个标志指针,使分别指向第一个 ×2，×3，×5 大于目前最大丑数的丑数元素
		//分别×2，×3，×5 小于等于目前最大丑数的丑数元素一定已经位于丑数数组中
		while (*Multiply2 * 2 <= min) {
			Multiply2++;
		}
		while (*Multiply3 * 3 <= min) {
			Multiply3++;
		}
		while (*Multiply5 * 5 <= min) {
			Multiply5++;
		}

		//向下遍历，直至丑数数组元素满num个，即得出第num个丑数
		pNextUgly++;
	}

	int uglyNum = Ugly[pNextUgly - 1];

	//清理内存
	delete[] Ugly;
	Ugly = nullptr;
	Multiply2 = nullptr;
	Multiply3 = nullptr;
	Multiply5 = nullptr;

	return uglyNum;
}

51 第一次只出现一次的字符

字符串中第一个只出现一次的字符

Testing case

• 功能测试(字符串中有/无只出现一次的字符，字符串中所有字符均只出现一次)
• 边界测试(nullptr)

Key

• 哈希表 T(n) = O(n) S(n) = O(1) 1KB

  1. 第一遍历字符串根据字符串ascll码值在哈希表对应位置处记录其出现次数
  2. 恢复遍历字符串的指针，使其重新指向字符串首部
  3. 第二次遍历字符串根据哈希表中的出现次数返回第一次只出现一次的字符

  注意:

  1. 哈希表可使用map或者unordered_map形成 字符-次数 键值对,哈希表存256个元素，共占用256*4=1024 1KB内存
  2. 此处考虑 ascll码 映射其在数组中的存放位置，形成简易哈希表
  3. 两次遍历使用同一个遍历指针，注意第二次使用该指针时需要还原位置

Answer

bool isExcption = false;

char FirstNotRepeatChar(char*);

char FirstNotRepeatChar(char* str) {
	//异常判断
	if (str == nullptr) {
		isExcption = true;
		return '\0';
	}

	//字符1byte 8bit 256中状态 256中不同字符表示
	const unsigned int Allchar = 256;
	//设置大小为256的哈希表，使用取字符的ascll码值作哈希函数
	unsigned int hash[Allchar];
	//设置哈希表初值为0以便记录次数
	for (int i = 0; i < Allchar; i++) {
		hash[i] = 0;
	}
	//设置遍历字符串的指针
	char* pCur = str;
	//第一次遍历字符串记录各字符出现的次数并映射到哈希表的相应位置
	while (*pCur != '\0') {
		hash[*pCur]++;
		pCur++;
	}

	//第二次遍历前需要将遍历指针还原
	pCur = str;

	//第二次遍历字符串找寻第一个只出现一次的字符
	while (*pCur != '\0') {
		if (hash[*pCur] == 1) {
			return *pCur;
		}
		pCur++;
	}

	//若执行至此处说明无只出现一次的字符
	return '\0';
}

51.2 哈希表应用拓展

• 定义两个字符串，在第一个字符串中删除第二个字符串中出现过的所有元素

  1. 遍历第二个字符串，并建立一个哈希表记录第二个字符串中的元素出现状态 键值对为 字符-bool
  2. 遍历第一个字符串，根据字符映射对应哈希表判断当前字符是否应该删除

• 定义一个函数删除字符串中重复出现的字符

  1. 遍历该字符串，并建立哈希表记录元素的出现状态
  2. 若 字符-bool bool为fasle，则将该值设置为true
  3. 若 字符-bool bool为true，则表明该字符之前已经出现过，删除该字符

• 英语单词的变位词，两个词中出现的字母相同，且各字母的出现次数相同

  1. 遍历其中一个英语单词，并建立一个哈希表记录字符的出现次数 键值对为 字符-num
  2. 遍历另一个英语单词，并将相应的哈希表中的值减1
  3. 若遍历完后，哈希表中各值均为0，则表明这两个词互为变位词

51.3 字符流中只出现一次的字符

字符流中第一个只出现一次的字符

请实现一个函数,用来找出字符流中第一个只出现一次的字符

例如,当从字符流中只读出前两个字符”go”时,第一个只出现一次的字符是g:当从该字符流中读出前6个字符”google”时,第一个只出现一次的字符是1。

Testing case

• 功能测试(字符串中有/无只出现一次的字符，字符串中所有字符均只出现一次)
• 边界测试(nullptr)

Key

• 哈希表

  插入元素

  1. 每插(输)入一个字符，则根据字符ascll码值判断对应哈希表的值是否为-1
  2. 若为-1，表明该字符为首次出现，将该字符的在字符流中的位置index值写入哈希表对应位置,然后index++，表明下一个字符在字符流中的位置
  3. 若>=0，则表明该字符已经出现一次，将该字符的对应哈希表位置处的值设置为非法值-2，表明不可能为要求字符,然后index++，表明下一个字符在字符流中的位置
  4. 若为非法值，则仅需index++即可

  获取要求字符

  1. 从头遍历整个哈希表，判断键值对对应值的状态

     若>=0，则表明该字符在字符流中仅出现了一次，但是无法确保为第一个字符，进而通过打擂判断其index是否为最小的index

  2. 遍历完后，最小index对应的键标识的字符即为最小字符

  注意:

  1. 字符流区别于字符数组的点在于字符流无法遍历，因此需要有介质存放字符在字符流中的位置
  2. 仅仅通过遍历哈希表(记录字符出现次数)无法保证值为1的字符是第一次出现
  3. 因此哈希表中 键值对 值应存放字符在字符流中的位置索引，若重复出现，则值为非法值，标志该字符不可能为要求字符
  4. 对于流的操作考虑使用类来模拟流的输入并实时更新状态与获取状态
  5. numeric_limits::max() 可获取int类型中最大的int型数

Answer

class CharStatics {
public:
	CharStatics():index(0){
		for (int i = 0; i < Allchar; i++) {
			hash[i] = -1;
		}
	}

	void insert(char ch) {
		if (hash[ch] == -1) {
			//当前字符仅出现了一次，因此键值对值存放其在字符流中的位置
			hash[ch] = index;
		}
		else if (hash[ch] >= 0) {
			//当前字符已经在字符流中出现了一次，因此当前元素不可能为要求元素,将值设置为-2标识
			hash[ch] = -2;
		}

		//若当前字符已经重复出现了多次，则仅需更新index

		//index++用于标识下一个元素在字符流中的位置
		index++;
	}

	char getFirst() {
		//Front记录字符在字符流中出现的位置，初始化为int中的最大值
		int min = numeric_limits<int>::max();

		//minChar记录最小字符
		char minChar = '\0';

		for (int i = 0; i < Allchar; i++) {
			//因为哈希表中为元素顺序不代表在字符流中出现顺序，因此需要遍历整个哈希表，根据index记得位置判断是否靠前
			if (hash[i] >= 0 && hash[i] <= min) {
				minChar = (char)i;
				min = hash[i];
			}
		}

		return minChar;
	}

private:
	//哈希表，记录字符流中字符出现的次数
	int hash[Allchar];
	//记录当前字符流中字符在字符流中的位置
	int index;
};

52 数组中的逆序对

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对

输入一个数组,求出这个数组中的逆序对的总数

例如,在数组7, 5, 6, 4中,一共存在5个逆序对,分别是(7, 6)(7, 5), (7, 4), (6, 4)和(5, 4)

Testing case

• 功能测试(未经排序的数组，递增排序的数组，递减排序的数组，输入的数组包含重复数字)
• 边界测试(nullptr，只有两个数字，只有一个数字)

Key

• 暴力遍历 T(n) = O(n2)

  1. 从头遍历数组，将当前元素与后续O(n)元素进行比较计算含当前元素的逆序对数
  2. 直至遍历完数组，数组所有逆序数计算完毕

  注意:

  1. 暴力遍历，时间效率低

• 归并划分 T(n) = (nlogn) S(n) = O(n)

  1. 基于归并排序对数组进行划分

  2. 计算左子数组中的逆序数

  3. 计算右子数组中的逆序数

  4. 设置三个指针和一个暂存数组，在递增有序的基础上，自左右子数组末位开始判断

     若data[Lend] > data[Rend]，将大者写入暂存数组，并将相应指针前移，此时data[Lend]的逆序数为data[Rend]以及之前所有元素个数

     若data[Lend] <= data[Rend]，将大者写入暂存数组，并将相应指针前移，此时无逆序数产生

  5. 将剩余未存入暂存数组中的元素进行判断并存入

  注意:

  1. 在进行相邻子数组逆序数判断时，如何保证判断完逆序数后的两个子数组递增有序

     进行子数组逆序数计算时，copy与data参数不断对调，使下一次相邻子数组逆序数的计算基于两者中有序的一方

Answer

int InversePair(int* data, int len) {
		//判断异常
		if (data == nullptr || len <= 0) {
			isExcption = true;
			return 0;
		}

		//设置辅助暂存数组,并初始化为arr
		int* copy = new int[len];
		for (int i = 0; i < len; i++) {
			copy[i] = data[i];
		}

		int count = InversePairCore(data, copy, 0, len - 1);

		//清理内存
		delete[] copy;

		return count;
	}

	int InversePairCore(int* data, int* copy, int start, int end) {
		//base case
		if (start == end) {
			//递归终止条件为划分至仅有一个元素,此时子数组的逆序数为0																		//保证数组有序，将值存入暂存数组
			copy[start] = data[start];
			return 0;
		}

		//设置划分界限,对半划分
		int len = (end - start) / 2;

		//获取左子数组中的逆序数
		int left = InversePairCore(copy, data, start, start + len);
		//获取右子数组中的逆序数
		int right = InversePairCore(copy, data, start + len + 1, end);
		//获取左右子数组合并后的逆序数
		int inNum = 0;
		//设置三个指针，分别指向左右与合并后子数组的末位
		int Lend = start + len;
		int Rend = end;
		int Mend = end;
		//从后向前遍历左右子数组所有元素进行合并
		while (Lend >= start && Rend >= start + len + 1) {
			if (data[Lend] > data[Rend]) {
				//若左子数组的末位元素大于右子树组的末位元素，将大者写入暂存数组
				copy[Mend] = data[Lend];
				//并将相应指针前移
				Mend--;
				Lend--;
				//根据右子数组末位元素位置计算此时逆序数
				inNum += Rend - start - len;
			}else{
				//若左子数组的末位元素小于等于右子树组的末位元素，将大者写入暂存数组
				//此时不构成逆序数
				//并将相应指针前移			
				copy[Mend] = data[Rend];
				Mend--;
				Rend--;
			}
		}

		//定有一个子数组率先存入暂存数组，此时将另一数组元素按序存入暂存数组
		while (Lend >= start) {
			copy[Mend] = data[Lend];
			Mend--;
			Lend--;
		}

		while (Rend >= start + len + 1) {
			copy[Mend] = data[Rend];
			Mend--;
			Rend--;
		}

		return left + right + inNum;
	}

53 在排序数组中查找数字

统计一个数字在排序数组中出现的次数

Testing case

• 功能测试(数组中存在/不存在要查找的数字，要查找的数字出现多次/一次)
• 边界测试(nullptr，数组中只有一个数字，查找的值为数组最大/最小值)

Key

• 暴力遍历 T(n) = O(n)

  遍历数组，若当前元素与待查找数字相同，则计数变量增1

• 二分查找 T(n) = O(logn)

  获取基于二分查找的k第一次出现的位置

  1. 若mid值与待查找数字相同，则判断是否为第一次出现，若为第一次出现，返回该元素

     首元素 / 非首元素且该元素之前的元素不是待查找数字 mid == 0 || (mid > 0 && data[mid - 1] != k)

  2. 若mid值与待查找数字相同，但不是第一次出现，则在其前子数组中继续查找第一次出现的位置

  3. 若mid值与待查找数字不相同，则在子数组中继续查询(二分思路略)

  获取基于二分查找的k最后一次出现的位置

  4. 若mid值与待查找数字相同，则判断是否为最后一次出现，若为最后一次出现，返回该元素

     尾元素 / 非尾元素且该元素之后的元素不是待查找数字 mid == len - 1 || ((mid < (len - 1)) && data[mid + 1] != k)

  5. 若mid值与待查找数字相同，但不是最后一次出现，则在其后子数组中继续查找最后一次出现的位置

  6. 若mid值与待查找数字不相同，则在子数组中继续查询(二分思路略)

  7. 最后基于两个位置的差值返回数字在排序数组中出现的次数

  注意:

  1. 利用二分查找查找数字在数组中第一次和最后一次出现的位置，即可省去遍历所有数字，利用差值计算数字出现次数

Answer

int GetNumOfK(int* data, int length, int k) {
	//判断异常
	if (data == nullptr || length <= 0) {
		isExcption = true;
		return -1;
	}

	int num = 0;

	//获取基于二分查找的k第一次出现的位置
	int first = GetFirstK(data, length, k, 0, length - 1);
	int last = GetLastK(data, length, k, 0, length - 1);

	if (first != -1 && last != -1) {
		num = last - first + 1;
	}

	return num;

}

int GetFirstK(int* data, int len, int k, int start, int end) {
	//base case
	if (start > end) {
		return -1;
	}

	int mid = (start + end) / 2;
	if (data[mid] == k) {
		//若当前中值等于k，判断该值是否为第一个值为k的元素
		if (mid == 0 || (mid > 0 && data[mid - 1] != k)) {
			return mid;
		}
		//若不是，则继续在该元素之前的子数组中查找
		end = mid - 1;

	}
	else if (data[mid] < k) {
		start = mid + 1;
	}
	else {
		end = mid - 1;
	}

	//二分递归
	GetFirstK(data, len, k, start, end);
}

int GetLastK(int* data, int len, int k, int start, int end) {
	//base case
	if (start > end) {
		return -1;
	}

	int mid = (start + end) / 2;
	if (data[mid] == k) {
		//若当前中值等于k，判断该值是否为最后一个值为k的元素
		if (mid == len - 1 || ((mid < (len - 1)) && data[mid + 1] != k)) {
			return mid;
		}
		//若不是，则继续在该元素之后的子数组中查找
		start = mid + 1;

	}
	else if (data[mid] < k) {
		start = mid + 1;
	}
	else {
		end = mid - 1;
	}

	//二分递归
	GetLastK(data, len, k, start, end);
}

53.1 0-n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0-n-1之内

在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字

Testing case

• 功能测试(缺失的数字为数组首元素，尾元素，数组中某个元素)
• 边界测试(nullptr，数组中仅一个元素0)

Key

• 暴力遍历 T(n) = O(n)

  1. 通过公式 n(n-1) / 2，计算 0-n-1 数字的和
  2. 计算数组中所有数字元素的和
  3. 差值即为缺失的数字

• 二分查找 T(n) = O(logn)

  1. 二分查找，若data[mid] != mid，则进一步判断该元素是否为第一个下标不等于元素值的元素

     (mid == 0) && isSort，是数组首位元素且为缺失元素
     mid > 0 && data[mid - 1] == mid - 1，不是数组首位元素且为缺失元素

  2. 若该元素是第一个下标不等于元素值的元素，则返回其下标，否则，在左子数组中继续查找

  3. 若data[mid] == mid，则在右子数组中进一步查找

  注意:

  1. 数组长度为n-1且有序，若缺失数字为m，则数组中m位置之前的元素值均等于其下标，m以及m位置之后的元素均不等于其下标且差值为1
  2. 因此问题转换为求有序数组中第一个下标与元素不相等的下标值，缺失数字位置m处存放着元素m+1
  3. 注意代码鲁棒性，对于非法情况要有预防性处理

Answer

int GetMissingNum(int* data, int len) {
	//判断异常
	if (data == nullptr || len <= 0) {
		isExcption = true;
		return -1;
	}

	//二分查找第一个元素值不等于下标的元素
	int start = 0;
	int end = len - 1;

	while(start <= end) {
		int mid = (start + end) >> 1;
		if (data[mid] != mid) {
			//首先判断该元素是否为非法元素
			if (data[mid] >= len) {
				isExcption = true;
				return -1;
			}
			//进一步判断该元素是否为第一个下标不等于元素值的元素，两种可能
			//- 是首位元素且为缺失元素
			//- 不是首位元素且为缺失元素

			//若数组有序，则该元素与对应角标差值不超过1 --预防性处理
			bool isSort = data[mid] - mid == 1;
			//判断非首位的元素是否为第一个值不等于下标的元素
			bool isMFirst = mid > 0 && data[mid - 1] == mid - 1;
			//判断首位元素是否为第一个一个值不等于下标的元素 --预防性处理
			bool isFFirst = (mid == 0) && isSort;

			if (isFFirst || isMFirst) {
				return mid;
			}
			end = mid - 1;
		}
		else {
			start = mid + 1;
		}
	}

	//考虑仅一个元素0的情况返回1
	if (start == len) {
		return len;
	}

	//若二分遍历完都没有找到，则存在异常
	//非法数字，数组不是排序的
	isExcption = true;
	return -1;

}

53.2 数组中数值与下标相等的元素

假设一个单调递增的数组里的每个元素都是整数并且是唯一的

请编程实现一个函数,找出数组中任意一个数值等于其下标的元素

Testing case

• 功能测试(数组中含/不含数值与下标相等的元素)
• 边界测试(nullptr，数组中仅一个元素，要求元素位置数组首部/尾部)

Key

• 暴力遍历 T(n) = O(n)

  1. 遍历数组每个元素判断当前下标是否与对应元素相等

• 二分查找 T(n) = O(logn)

  1. 二分查找，若data[mid] != mid，则进一步缩小要求元素所在的范围

     若data[mid]<mid，由于数组单调递增，则mid左边的元素一定不存在值与下标相等的元素，在mid右边元素中继续查找

     若data[mid]>mid，由于数组单调递增，则mid右边的元素一定不存在值与下标相等的元素，在mid左边元素中继续查找

  2. 若data[mid] == mid，则返回mid

  3. 若数组中不存在要求元素，则返回-1

  注意:

  1. 数组为单调递增且元素唯一，基于二分查找，每次查找可将查找范围可缩小一半

     若mid对应元素与mid不等，若data[mid]<mid，由于数组单调递增，则mid左边的元素一定不存在值与下标相等的元素

     若data[mid]>mid，由于数组单调递增，则mid右边的元素一定不存在值与下标相等的元素

Answer

int GetNumberSameAsIndex(int* data, int len) {
	//判断异常
	if (data == nullptr || len <= 0) {
		isExcption = true;
		return -1;
	}

	int start = 0;
	int end = len - 1;

	while (start <= end) {

		int mid = (start + end) >> 1;
		if (data[mid] == mid) {
			return mid;
		}
		else if (data[mid] < mid) {
			start = mid + 1;
		}
		else {
			end = mid - 1;
		}		
	}

	return -1;
}

54 二叉搜索树的第k大结点

给定一棵二叉搜索树,请找出其中第k大的节点

Testing case

• 功能测试(各种不同形态的二叉搜索树)
• 边界测试(nullptr，k=0,1,len，或k>len len为二叉搜索树结点数)

Key

• 中序遍历

  1. 中序遍历二叉树搜索树，先判断左子树中是否存在第k大结点
  2. 若左子树中不存在，则判断当前根结点是否为第k大结点
  3. 若当前根结点不是，则判断其右子树中是否存在第k大结点
  4. 最终将pKthNode返回

  注意:

  1. 二叉搜索树的中序遍历序列为由小到大的有序排列
  2. 异常判断是除了入口异常判断，还需注意k>len时的越界处理

Answer

TreeNode* GetKthNodePtr(TreeNode* pHead, int k) {
	//判断异常
	if (pHead == nullptr || k <= 0) {
		isException = true;
		return nullptr;
	}

	TreeNode* pKthNode = GetKthNodePtrCore(pHead, k);

	//进行k越界的异常判断
	if (pKthNode == nullptr) {
		isException = true;
	}

	return pKthNode;
}

TreeNode* GetKthNodePtrCore(TreeNode* pHead, int& k) {

	TreeNode* pKthNode = nullptr;

	//左子树中找第k个结点
	if (pHead->pLeft != nullptr) {
		pKthNode = GetKthNodePtrCore(pHead->pLeft, k);
	}

	//若左子树未找到第k个结点，判断当前结点是否为第k个结点
	if (pKthNode == nullptr) {
		if (k == 1) {
			pKthNode = pHead;
		}
		k--;
	}

	//若当前结点不是第k个结点，则在当前结点的右子树中找第k个结点
	if (pKthNode == nullptr && pHead->pRight != nullptr) {
		GetKthNodePtrCore(pHead->pRight, k);
	}

	return pKthNode;
}

55 二叉树的深度

输入一棵二叉树的根节点,求该树的深度

从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度

Testing case

• 功能测试(普通二叉树，仅含左/右子树的二叉树)
• 边界测试(nullptr，二叉树仅含一个结点)

Key

• 先序遍历

  1. 先序遍历二叉树，对当前遍历的根节点进行计数
  2. 对于每一条路径，当到达叶子结点时打擂记录最大路径长度

  注意:

  1. 遍历每一条路径记录最长的路径长度作为二叉树的深度
  2. 使用辅助接口函数返回二叉树的深度

• 后序遍历

  1. 后序遍历二叉树，使用两个变量记录当前根节点的左子树和右子树的深度
  2. 取左子树与右子树中深度较大者+1作为当前子树的深度
  3. 若当前根节点为空，则深度为0

  注意:

  1. 每个子树的深度为其根节点左子树与右子树中深度较大者+1
  2. base case若是对叶子结点的判断，则在对左/右子树遍历前需要保证左/右子树不为空
  3. base case若是对nullptr的判断，则可放心递归获取左/右子树深度

Answer

1.

int TreeDepth(TreeNode* pHead) {
	//异常判断
	if (pHead == nullptr) {
		isException = true;
		return 0;
	}

	//记录深度的变量
	int Depth = 0;
	//记录最大深度的变量
	int MaxDepth = 0;

	TreeDepthCore(pHead, Depth, MaxDepth);
	
	return MaxDepth;
}

void TreeDepthCore(TreeNode* pHead, int Depth, int& MaxDepth) {
	//先序遍历
	Depth++;
	
	//到达叶子结点
	if (pHead->pLeft == nullptr && pHead->pRight == nullptr) {
		if (Depth >= MaxDepth) {
			MaxDepth = Depth;
		}
		return;
	}

	if (pHead->pLeft != nullptr) {
		TreeDepthCore(pHead->pLeft, Depth, MaxDepth);
	}

	if (pHead->pRight != nullptr) {
		TreeDepthCore(pHead->pRight, Depth, MaxDepth);
	}

}

2.

int TreeDepthByPost(TreeNode* pHead) {
	//异常判断
	if (pHead == nullptr) {
		isException = true;
		return 0;
	}

	return TreeDepthByPostCore(pHead);
}
int TreeDepthByPostCore(TreeNode* pHead) {
	//base case
    
	/*
	if (pHead == nullptr) {
		return 0;
	}

	int Left = TreeDepthByPostCore(pHead->pLeft);
	int Right = TreeDepthByPostCore(pHead->pRight);

	return (Left > Right) ? Left + 1 : Right + 1;
	*/

	if (pHead->pLeft == nullptr && pHead->pRight == nullptr) {
		return 1;
	}
	
	int Left = 0;
	if (pHead->pLeft != nullptr) {
		Left = TreeDepthByPostCore(pHead->pLeft);
	}
	int Right = 0;
	if (pHead->pRight != nullptr) {
		Right = TreeDepthByPostCore(pHead->pRight);
	}

	return (Left > Right) ? Left + 1 : Right + 1;
}

55.1 平衡二叉树

输入一棵二叉树的根节点,判断该树是不是平衡二叉树

如果某二叉树中任意节点的左、右子树的深度相差不超过1,那么它就是一棵平衡二叉树

Testing case

• 功能测试(普通二叉树/平衡二叉树，仅含左/右子树的平衡二叉树)
• 边界测试(nullptr，二叉树仅含一个结点)

Key

• 先序遍历

  1. 先序遍历二叉树的每一个结点
  2. 对于当前根结点基于TreeDepth求得当前结点的左右子树深度并判断当前结点的平衡因子是否满足要求
  3. 进而判断左右子树中的各结点是否满足要求

  注意:

  1. 求解结点的平衡因子时存在大量的重复计算
  2. 设置两个全局异常判断变量，防止不同类型的异常混乱

• 后序遍历

  1. 后序遍历二叉树，在左右子树均满足平衡二叉树的条件下
  2. 根据两个子树的深度记录参数，判断当前根节点的平衡因子是否满足要求，并计算当前结点为根节点的子树的深度
  3. 直至根节点为nullptr返回true，深度记录为0

  注意:

  1. 后序遍历二叉树，在左右子树均满足平衡二叉树的条件下，再判断当前根节点的平衡因子是否满足要求
  2. 当前根节点的平衡因子判断需要在遍历左右子树时实时记录左右子树的深度，增加一个记录深度的输出参数即可
  3. 对所有结点仅遍历了一次

Answer

1.

bool isBalancedTreeByPre(TreeNode* pHead) {
	//判断异常
	if (pHead == nullptr) {
		isBalancedException = true;
		return false;
	}

	return isBalancedTreeByPreCore(pHead);
}

bool isBalancedTreeByPreCore(TreeNode* pHead) {
	//base case
	if (pHead == nullptr) {
		return true;
	}

	//获取当前结点的左右子树深度
	int left = TreeDepthByPost(pHead->pLeft);
	int Right = TreeDepthByPost(pHead->pRight);

	//判断当前结点的平衡因子是否满足要求
	int diff = left - Right;
	if (diff < -1 || diff > 1) {
		return false;
	}

	//若当前结点平衡因子满足要求，则进而判断其左右子树中各结点是否满足要求
	return isBalancedTreeByPreCore(pHead->pLeft) && isBalancedTreeByPreCore(pHead->pRight);
}

2.

bool isBalancedTreeByPostCore(TreeNode* pHead, int& Depth) {
	//base case
	if (pHead == nullptr) {
		return true;
		Depth = 0;
	}

	//设置记录左右子树深度的输出参数
	int Left;
	int Right;

	if (isBalancedTreeByPostCore(pHead->pLeft, Left) && isBalancedTreeByPostCore(pHead->pRight, Right)) {
		int diff = Left - Right;
		if (diff >= -1 && diff <= 1) {

			//记录当前结点作根结点的子树的深度
			Depth = 1 + (Left > Right ? Left : Right);
			return true;			
		}
	}

	//若当前结点平衡因子不满足要求，则无需记录深度，直接返回false即可
	return false;

}

56 数组中只出现一次的两个数字

一个整型数组里除两个数字之外,其他数字都出现了两次

请写程序找出这两个只出现一次的数字

要求时间复杂度是0(n),空间复杂度是0(1)

Testing case

• 功能测试(数组中有多对重复数字，数组中无重复数字)
• 边界测试(nullptr)

Key

• 位运算 - 异或 T(n) = O(n) S(n) = O(1)

  1. 遍历整个数组求所有元素的异或结果

  2. 根据1自低位起出现的出现的位置作为划分依据，将数组划分为分别包含一个只出现一次数字的两个子数组

     FirstIndex位为1的为1组，FirstIndex位为0的为1组

  3. 分别计算两个子数组中只出现一次的数字

  注意:

  1. 先分析数组中只出现一次的一个数字的求法，将数组每个元素进行异或运算，结果即为只出现一次的数字，因为重复的数字异或结果为0
  2. 而两个数字的求法基于方法1，可以想办法将这两个数字分于两个子数组中，分别求两个子数组中只出现一次的数字即可
  3. 因为返回值有两个，因此使用输出参数返回结果

Answer

bool isOneInIndex(int Num, int index) {
	//右移index次到达index位
	Num >> index;
	//判断该位是否为1
	return Num & 1;
}

int GetIndexOfNum1(int Num) {
	int index = 0;
	//自低位开始判断是否为1，若不是则右移，但注意防止溢出，注意边界判断，共 8*sizeof(int) 位
	while (((Num & 1) == 0) && (index < 8 * sizeof(int))) {
		Num >>= 1;
		index++;
	}

	return index;
}

void FindNumsAppearOnce(int* data, int len, int& Num1, int& Num2) {
	//判断异常
	if (data == nullptr || len <= 0) {
		isExcption = true;
		return;
	}

	//首次遍历数组，求得所有数字的异或结果
	int ExclusiveOr = 0;
	for (int i = 0; i < len; i++) {
		ExclusiveOr ^= data[i];
	}

	//求得异或结果从低位记起 1 第一次出现的位置
	int FirstIndex = GetIndexOfNum1(ExclusiveOr);

	//将数组分成两组 一组FirstIndex位为0 一组FirstIndex位为1
	//分别计算两组的异或结果，结果即为两个出现次数为1的数字

	Num1 = 0;
	Num2 = 0;

	for (int i = 0; i < len; i++) {
		if (isOneInIndex(data[i], FirstIndex)) {
			Num1 ^= data[i];
		}
		else {
			Num2 ^= data[i];
		}
	}
}

56.1 数组中唯一只出现一次的数字

在一个数组中除一个数字只出现一次之外,其他数字都出现了三次

请找出那个只出现一次的数字

Testing case

• 功能测试(只出现一次的数字为0，正数，负数，重复出现的数字为0，正数，负数)
• 边界测试(nullptr)

Key

• 位运算 T(n) = O(n) S(n) = O(1)

  1. 遍历数组，由低位起，将数组元素每一位的值累加到indexSum数组的对应位上
  2. 由indexSum的每一位累加和求得只出现一次的数字的每一位的值并作移位累加
  3. 将移位累加和返回

  注意:

  1. 其他数字都出现了三次，数组各元素异或结果重复数字仍为原数字，异或不可取
  2. 但是若对数组各元素的每一位求和，并记录每一位的和，若该位求和结果可被3整除，则只出现一次的数字该位为0，否则为1
  3. 对int型数字的每一位均记录求和结果，可使用大小为32的int型数组，indexSum数组
  4. 选取更新掩码的方法来由低到高遍历整数的每一位

Answer

int FindNumAppearOnce(int* data, int len) {
	//判断异常
	if (data == nullptr || len <= 0) {
		isExcption = true;
		return 0;
	}

	//遍历数组每一个元素，累加计算每个元素每一位上的和
	int indexSum[32] = { 0 };

	for (int i = 0; i < len; i++) {
		//累加当前元素的各位上的和，整型元素共32位

		//各位遍历时不希望右移数据元素更改数据，而选择移动掩码来进行下一位的累加和计算
		int indexMask = 1;

		for (int j = 31; j >= 0; j--) {
			//低位起记录当前位上的值
			int result = data[i] & indexMask;

			if (result != 0) {
				//若当前位值为1，则累加1，而非累加result，是该位的累加和不再考虑低位
				indexSum[j] += 1;
			}

			//进行下一位的判断
			indexMask <<= 1;
		}

	}

	//计算只出现一次数字的值，以位为单位计算最终得到Num值
	int Num = 0;

	for (int i = 0; i < 32; i++) {
		Num <<= 1;
		Num += indexSum[i] % 3;
	}

	return Num;

}

57 和为s的数字

输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得它们的和正好是S

如果有多对数字的和等于S,则输出任意一对即可

Testing case

• 功能测试(数组中存在/不存在和为s的两个数字)
• 边界测试(nullptr)

Key

• 暴力遍历 T(n) = O(n2)

  1. 遍历数组，同时固定当前数字，计算当前数字与其后数字的和是否满足和为S

• 双指针遍历 T(n) = O(n)

  1. 设置两个遍历指针，分别初始化为指向数组最小值与最大值

  2. 计算两个指针指向位置的和s，判断与S的大小关系，若与s=S，则设置传出参数返回

     若 s<S,则将指向较小元素的指针后移，增大s

     若 s>S,则将指向较大元素的指针前移，缩小s

  注意:

  1. 数组为排序数组，因此当选择两个数计算和后，通过判断与s的大小关系可以缩小查找范围
  2. 设置双指针，一个指向较小的元素，一个指向较大的元素，通过指针的交替移动完成查找
  3. 涉及多个结果的返回，通过传出参数返回结果

Answer

bool FindNumWithSum(int* data, int length, int Sum, int& Num1, int& Num2) {
	//判断异常
	if (data == nullptr || length <= 0) {
		isExcption = true;
		return false;
	}

	//设置返回值
	bool find = false;

	//设置两个指针分别用于指向Num1与Num2，初始化为排序数组最大值与最小值
	int maxIndex = length - 1;
	int minIndex = 0;

	while (minIndex < maxIndex) {
		int sum = data[maxIndex] + data[minIndex];
		if (sum == Sum) {
			find = true;
			Num2 = data[maxIndex];
			Num1 = data[minIndex];
			break;
		}
		else if (sum < Sum) {
			//若此时指针指向的两个元素和小于Sum,则将指向较小元素的指针后移(数组由小到大排序)
			minIndex++;
		}
		else {
			//若此时指针指向的两个元素和大于Sum,则将指向较大元素的指针后移(数组由小到大排序)
			maxIndex--;
		}
	}

	return find;
}

57.1 和为s的连续正数序列

输入一个正数s,打印出所有和为s的连续正数序列(至少含有两个数)

例如,输入T5,由于1+2+3+4+5=4+5+6=7+8=15,所以打印出3个连续序列15,46和7~8

Testing case

• 功能测试(存在/不存在和为s的序列,例如4)
• 边界测试(3)

Key

• 范围指针对

  1. 设置一对范围遍历指针，并使用curSum记录当前范围序列的累加和
  2. 移动指针对自1开始的正数序列进行遍历，若curSum == Sum ,则对当前序列进行输出，并进一步扩大范围，先对end++，后对curSum累加
  3. 若 curSum > Sum，则一直缩小序列范围，curSum 剔除start当前指向的元素，并将start后移，直到curSum == Sum or curSum < Sum
  4. 若 curSum < Sum，则一直扩大序列范围，先对end++，后对curSum累加，直到curSum == Sum or curSum > Sum
  5. 最终直至start >= (sum + 1) / 2

  注意:

  1. curSum记录当前范围序列的累加和

     缩小序列范围时，应先将curSum剔除掉start对应的数，后对start++

     扩大序列范围时，应先对end++，后对curSum累加

  2. 范围遍历指针时刻指向正数序列的两个边界

  3. 由于需要找到所有的正数序列，因此即使输出了一个正数序列之后，也应再次扩大范围，进行查找

Answer

void printSequene(int start, int end) {
	for (int i = start; i <= end; i++) {
		cout << i << " ";
	}
	cout << endl;
}

void FindContinuousSequene(int sum) {
	//判断异常
	if (sum < 3) {
		isExcption = true;
		return;
	}
	//设置序列范围指针
	int start = 1;
	int end = 2;

	//记录序列范围中所有数字的和
	int curSum = start + end;

	//遍历找寻满足条件的序列
	while (start < (sum + 1) / 2) {
		//简化版
        
		if (curSum == sum) {
			printSequene(start, end);
		}

		while (curSum > sum && start < (sum + 1) / 2) {
			//剔除序列中最小的正数，先累减后++
			curSum -= start;
			start++;

			if (curSum == sum) {
				printSequene(start, end);
			}
		}

		//扩大序列的范围，先++后累加
		end++;
		curSum += end;		

		//冗余版
		//if (curSum == sum) {
		//	printSequene(start, end);

		//	end++;
		//	curSum += end;
		//}
		//else if (curSum > sum) {
		//	curSum -= start;
		//	start++;

		//	if (curSum == sum) {
		//		printSequene(start, end);

		//		end++;
		//		curSum += end;
		//	}
		//}
		//else {
		//	//扩大序列的范围，先++后累加
		//	end++;
		//	curSum += end;
		//}
	}
}

58 翻转字符串

输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变

为简单起见,标点符号和普通字母一样处理

例如输入字符串”I am a student.”,则输出”student. a am I”

Testing case

• 功能测试(句子中有多个单词，句子中只有一个单词)
• 边界测试(nullptr，空字符串，只有空格)

Key

• 范围指针对 + 整体与局部

  1. 设置范围指针对分别指向字符串首尾
  2. 根据范围指针对，先将整个字符串进行翻转
  3. 由范围指针对，对单个单词进行翻转，pEnd后移找寻单词末尾(‘ ‘ or ‘\0’ )，pStart进行遍历并时刻指向单词首部
  4. 直至 pStart == ‘\0’ ，字符串翻转完毕

  注意:

  1. 对单词进行翻转判断时，注意pEnd后移找到单词末尾时，需要翻转不包含 ‘ ‘ or ‘\0’ 的子字符串,传参时注意指针的前移

Answer

char* ReverseSentence(char* pSen) {
	//判断异常
	if (pSen == nullptr) {
		isExcption = true;
		return nullptr;
	}

	char* pStart = pSen;
	char* pEnd = pStart;

	//设置范围指针对的范围，使pEnd指向字符串尾部
	while (*pEnd != '\0') {
		pEnd++;
	}

	pEnd--;

	//翻转整个字符串
	ReverseWords(pStart, pEnd);

	//翻转每个单词
	//重置范围指针对指向范围
	pStart = pEnd = pSen;

	while (*pStart != '\0') {
		if (*pStart == ' ' && *pEnd == ' ') {
			pStart++;
			pEnd++;
		}
		else if (*pEnd == ' ' || *pEnd == '\0') {
			//翻转单词
			ReverseWords(pStart, --pEnd);
			pStart = ++pEnd;
		}
		else {
			pEnd++;
		}
	}

	return pSen;
}

void ReverseWords(char* pStart, char* pEnd) {
	//判断异常
	if (pStart == nullptr || pEnd == nullptr) {
		isExcption = true;
		return;
	}

	while (pStart < pEnd) {
		char temp = *pStart;
		*pStart = *pEnd;
		*pEnd = temp;

		//缩小范围
		pStart++;
		pEnd--;
	}
}

58.1 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部

请定义一个函数实现字符串左旋转操作的功能

比如,输入字符串”abcdefg”和数字2,该函数将返回左旋转两位得到的结果”cdefgab”

Testing case

• 功能测试(长度为n的字符串左旋0,1,2,n,n-1,n+1个字符)
• 边界测试(nullptr)

Key

• 范围指针对 + 整体与局部

  1. 设置范围指针对分别指向字符串首尾
  2. 根据范围指针对，先将整个字符串进行翻转
  3. 由范围指针对,根据左旋的字符数确定待翻转的子串范围，并将该范围子串翻转
  4. 将不需要左旋的字符串进行翻转恢复
  5. 将两个子字符串翻转完毕后，字符串左旋完毕

  注意:

  1. 注意空串，待旋转子串长度越界问题，代码鲁棒性检查

Answer

void ReverseWords(char* pStart, char* pEnd) {
	//判断异常
	if (pStart == nullptr || pEnd == nullptr) {
		isExcption = true;
		return;
	}

	while (pStart < pEnd) {
		char temp = *pStart;
		*pStart = *pEnd;
		*pEnd = temp;

		//缩小范围
		pStart++;
		pEnd--;
	}
}

char* LeftRotateString(char* pStr, int n) {
	//判断异常
	if (pStr == nullptr || *pStr == '\0') {
		isExcption = true;
		return nullptr;
	}

	char* pStart = pStr;
	char* pEnd = pStart;

	//设置范围指针对的范围，使pEnd指向字符串尾部
	int num = 0;

	while (*pEnd != '\0') {
		pEnd++;
		num++;
	}

	if (n > num) {
		isExcption = true;
		return nullptr;
	}

	pEnd--;

	//翻转整个字符串
	ReverseWords(pStart, pEnd);

	//对指定范围进行翻转
	//将需要左旋子字符串进行翻转
	ReverseWords(pEnd - n + 1, pEnd);
	//将不需要左旋的字符串进行恢复
	ReverseWords(pStart, pEnd - n);

	return pStr;

}

59 滑动窗口的最大值

给定一个数组和滑动窗口的大小,请找出所有滑动窗口里的最大值

例如,如果输入数组(2,3,4,2,6,2,5,1)及滑动窗口的大小3,那么一共存在6个滑动窗口,它们的最大值分别为4,4,6,6,6,5

Testing case

• 功能测试(输入的数组无序/单调递增/单调递减)
• 边界测试(数组为空，滑动窗口的大小为0，1，等于/大于 输入数组的大小)

Key

• 双向队列

  1. 设置一个双向队列Window以及待返回的存放各窗口最大值的maxInWindows数组
  2. 在窗口元素未满WinSize前，先遍历数组data的前WinSize个元素，若Window非空，则从队尾开始循环判断，将小于等于当前数组元素的Window元素(下标)从队尾弹出(将不可能成为当前滑动窗口的元素由Window队尾开始逐个弹出)，最终将当前元素下标压入
  3. 在窗口元素未满WinSize后，对数组剩余元素进行遍历，先将WinSize队首元素(当前滑动窗口的最大值元素在data中的下标)进行记录，进而将不可能成为当前滑动窗口的元素由Window队尾开始逐个弹出，再将已不在当前窗口内的队首元素逐个弹出，最终将当前元素下标压入
  4. 将最后一个滑动窗口的最大值元素下标记录后，返回maxInWindows数组

  注意:

  1. 使用一个双向队列，仅存放当前滑动窗口中的最大值元素以及可能成为其后滑动窗口最大值的元素，队首始终为当前滑动窗口的最大值元素 -下标
  2. 为了确保队列滑动时此队列能排除窗口之外的元素，队列中存放数组元素下标而非元素，通过下标根据窗口大小判断队首元素是否已不在此窗口中
  3. 在窗口元素未满WinSize前，当前队列队首元素并不是最大值元素的下标，因此单独处理
  4. 在窗口元已满WinSize后，每遍历一个元素后，队首元素即为当前滑动窗口最大值元素的下标，记录该最大值元素
  5. deque同时允许队首队尾删除元素，在非最值元素时队尾弹出，在超出窗口范围时队首弹出

Answer

vector<int> MaxInWindows(const vector<int>& data, int WinSize) {

	//设置返回各窗口最大值的数组
	vector<int> maxInWindows;
	//判断异常
	if (data.size() < WinSize || WinSize <= 0) {
		isExcption = true;
		return maxInWindows;
	}

	//设置窗口队列，仅存可能为窗口最大值的元素
	deque<int> Window;

	//遍历数组元素，并对窗口状态进行更新，弹出不可能为窗口最大值的元素

	//先对数组前WinSize进行遍历，因为此时并未填满窗口
	for (int i = 0; i < WinSize; i++) {
		//根据当前元素值判断，弹出不可能为当前窗口最大值的元素
		while (!Window.empty() && data[i] >= data[Window.back()]) {
			Window.pop_back();
		}

		//将当前元素数组下标压入窗口
		Window.push_back(i);
	}

	for (int i = WinSize; i < data.size(); i++) {
		//将窗口队列队首元素压入maxInWindows，记录窗口最大值
		maxInWindows.push_back(data[Window.front()]);

		//根据当前元素值判断，弹出不可能为当前窗口最大值的元素
		while (!Window.empty() && data[i] >= data[Window.back()]) {
			Window.pop_back();
		}

		//根据当前元素的下标判断，弹出当前窗口之外的的元素
		while (!Window.empty() && (i - Window.front() >= WinSize)) {
			Window.pop_front();
		}

		//将当前元素数组下标压入窗口
		Window.push_back(i);
	}

	//将窗口队列队首元素压入maxInWindows，记录窗口最大值
	maxInWindows.push_back(data[Window.front()]);

	return maxInWindows;
}

59.1 队列的最大值

请定义一个队列并实现函数max得到队列里的最大值,要求函数max,push_back和pop_front的时间复杂度都是0(1)

Testing case

• 功能测试(对队列进行 插入/删除 操作后求最大值)
• 边界测试(队列为空)

Key

• 队列特性

  队列的特性与栈不同，队列为先进先出

  若当前压入的元素成为了队列的最大值，那么在该元素弹出之前(未压入新元素)，队列的最大值始终为该元素

• 双向队列

  使用一个双向队列max来记录队列data不同状态下的最大值

  max队列仅存放当前data队列最大值以及该最大值弹出后剩余状态的可能最大值，队首为当前data队列状态对应的最大值

• 数据内部封装

  在弹出元素时需要根据data队列弹出的元素来更新当前最大值状态，通过index与相应元素的绑定封装可以标识当前弹出的元素是否为当前data队列的最大值，从而更新max队列相应的最大值状态

• push_back压入元素

  1. 将压入的元素封装为内部数据压入data队列

  2. 更新相应的max队列最大值状态，剔除max队列自队尾开始比当前压入元素小的元素，将当前元素压入max队列

     由于队列特性，只要压入元素，那么该元素就可能成为data队列某一状态的最大值

  3. 更新currentIndex索引绑定下一个元素

• pop_front弹出元素

  1. 先判断当前弹出元素是否会影响max队列状态，若当前弹出元素绑定的currentIndex索引与max队首currentIndex索引相同，则需弹出max队首
  2. 在将该元素从data队首弹出
  3. 若 data 队列 or max队列 为空，则弹异常

• getMax取最大值

  1. 取max队列队首元素
  2. 若 data队列 or max队列 为空，则弹异常

Answer

template<class T>
class QueueWithMax {

public:

	QueueWithMax() :currentIndex(0) {}

	void push_back(T val) {
		//将数据封装为内部数据
		InternalData internalData;
		internalData.number = val;
		internalData.index = currentIndex;

		//将内部数据压入到data队列中
		data.push_back(internalData);

		//更新目前data队列的最大值，目前data队列的最大值位于max队首
		//先将已不可能成为data队列剩余状态的最大值的元素弹出
		while (!max.empty() && val >= max.back().number) {
			max.pop_back();
		}
		
		//剔除掉不可能元素后，剩余元素即为可能成为队列某一状态下的最大值，当前最大值为max队首元素
		//当前元素可能作为data队列某一状态下的最大值，压入
		max.push_back(internalData);

		//将索引更新指向下一个元素
		currentIndex++;
	}

	void pop_front() {
		if (!data.empty() && !max.empty()) {

			if (data.front().index == max.front().index) {
				max.pop_front();
			}
			data.pop_front();
		}
		else {
			throw new exception("异常");
		}
	}

	T getMax() const {
		if (!max.empty()) {
			return max.front().number;
		}
		else {
			throw new exception("异常");
		}
	}

private:

	struct InternalData {
		T number;
		int index;
	};

	deque<InternalData> data;
	deque<InternalData> max;

	int currentIndex;
};

60 n个骰子的点数

把n个骰子扔在地上,所有骰子朝上一面的点数之和为s

输入n,打印出s的所有可能的值出现的概率

Testing case

• 功能测试(1,2,3,4)
• 边界测试(0)
• 性能测试(11)

Key

• 穷举递归

  1. base case 剩余骰子数为0时记录骰子点数之和于数组中，对应存放位置累加计数
  2. explore 向下递归，对剩余骰子点数之和进行记录
  3. backtracking 在进行本骰子下一结果决策之前，先恢复骰子点数和，剔除上一次的结果
  4. 根据骰子各点数和与所有可能结果(6^n)计算某骰子和出现的概率

  注意:

  1. 使用一个数组对n个骰子朝上一面点数之和的出现次数进行记录，无需使用maxSum大小的数组直接使用点数和映射位置，而是仅存minSum - maxSum之间的maxSum - minSum + 1 个元素，使用 点数和 - minSum 映射存放位置
  2. 递归含多次重复计算

• 自下而上 + 迭代计算 + 哈希表

  1. 计算并记录一个骰子的所有点数和出现次数，使用数组记录，角标对应点数和，元素值对应该点数和出现的次数

  2. 根据一个骰子的结果，计算两个骰子的结果，基于第一个数组结果在第二个数组中记录结果

     f(n,sum) = f(n-1,sum-1) + f(n-1,sum-2) + … + f(n-1,sum-6)，(n>1,n <= sum <= n*6)

  3. 根据两个骰子的结果，计算三个骰子的结果，基于第二个数组结果在第一个数组中记录结果

  4. 直至计算出n个骰子的结果，进而计算各结果出现的概率

  注意:

  1. 记 f(n,sum) 为n个骰子时，和为sum的出现次数，则

     f(n,sum) = f(n-1,sum-1) + f(n-1,sum-2) + … + f(n-1,sum-6)，(n>1,n <= sum <= n*6)

     f(n,sum) = 1，(n=1,1 <= sum <= 6)

  2. n个骰子时各点数和的出现次数与且仅与n-1个骰子时的各点数和的出现次数有关

  3. 使用两个数组交替记录n个骰子时各点数和的出现次数与n-1个骰子时的各点数和的出现次数，自n=1时记录，直至计算至n=num，并使用flag标志位来交替记录

  4. 数组角标对应n个骰子的某点数和，元素值为其出现次数

  5. 注意在交替记录本次骰子各点数和时需要清零数组，因为仅使用两个数组记录，若不清零，会使计算混乱

  6. 注意边界值的考量，代码鲁棒性，条件的判断

Answer

1.

void ProbabilityCore(int minSum, int remainingDice, int curSum, int* countSum) {
	//base case 
	if (remainingDice == 0) {
		countSum[curSum - minSum]++;
	}
	else {
		for (int i = 1; i <= 6; i++) {
			//记录当前骰子点数
			curSum += i;
			//向下递归，求剩余骰子的点数
			ProbabilityCore(minSum, remainingDice - 1, curSum, countSum);
			//在进行下一种决策前回退
			curSum -= i;
		}
	}

}

void Probability(int n, int* countSum) {
	ProbabilityCore(n, n, 0, countSum);
}

void PrintProbability(int n) {
	//判断异常
	if (n < 1) {
		isExcption = true;
		return;
	}

	//记录骰子和的最大值与最小值
	int maxNum = 6;
	int maxSum = maxNum * n;
	int minSum = n;

	//设置记录骰子和出现次数的数组，和为 0 - (minSum-1) 的无需记录，因此无需maxSum长度，只需记录 minSum - maxSum 之间的数
	int* countSum = new int[maxSum - minSum + 1];
	//计数数组的初始化
	for (int i = n; i <= maxSum; i++) {
		countSum[i - minSum] = 0;
	}

	//递归计算各种骰子和出现的次数
	Probability(n, countSum);

	//设置概率分母
	int countMax = pow(maxNum, n);
	//计算各骰子和出现的概率
	for (int i = n; i <= maxSum; i++) {
		cout << i << endl;
		cout << "概率: ";
		cout << countSum[i - minSum] << "/" << countMax << " ≈ ";
		cout << ((double)(countSum[i - minSum])) / countMax << endl;
	}
	
    //清理内存
	delete[] countSum;
    
}

2.

void PrintProbabilityNR(int n) {
	//判断异常
	if (n < 1) {
		isExcption = true;
		return;
	}

	//记录n个骰子和的最大值与最小值以及单个骰子的最大值
	int maxNum = 6;
	int maxSum = maxNum * n;
	int minSum = n;

	//开辟暂存n个骰子点数和所有结果出现次数的数组
	//使用两个数组交替存放n-1个骰子的点数和所有结果出现次数 与 当前n个骰子的点数和所有结果出现次数
	//下标对应点数和，元素值为该点数和出现的次数
	int** curSum = new int*[2];
	curSum[0] = new int[maxSum + 1];
	curSum[1] = new int[maxSum + 1];

	//初始化
	for (int i = 0; i <= maxSum; i++) {
		curSum[0][i] = 0;
		curSum[1][i] = 0;
	}

	//设置交替时的标志位
	int flag = 0;

	//记录一个骰子点数和的所有结果出现的次数
	for (int i = 1; i <= maxNum; i++) {
		curSum[flag][i] = 1;
	}

	//自下而上计算两个，三个，...，n个骰子的点数和结果的出现次数
	for (int Dicenum = 2; Dicenum <= n; Dicenum++) {
		//借用上次Dicenum - 1个骰子的点数和次数结果计算本次Dicenum个骰子的点数和出现结果

		//先清空记录本次Dicenum个骰子的点数和出现结果的数组
		for (int i = 0; i <= maxSum; i++) {
			curSum[1 - flag][i] = 0;
		}

		//记录Dicenum个骰子的每种点数和出现的次数，最小为Dicenum，最大为 maxNum * Dicenum
		for (int curDiceSum = Dicenum; curDiceSum <= maxNum * Dicenum; curDiceSum++) {
			//累加记录之前先清零
			curSum[1 - flag][curDiceSum] = 0;
			//n个骰子时的和curDiceSum出现次数等于n-1个骰子时 f(curDiceSum-1) + f(curDiceSum-2) + ... + f(curDiceSum-6)
			for (int presum = 1; presum <= curDiceSum && presum <= maxNum; presum++) {
				curSum[1 - flag][curDiceSum] += curSum[flag][curDiceSum - presum];
			}
		}
		
		//交替数组，使用本次结果计算++Dicenum的结果
		flag = 1 - flag;
	}

	//设置概率分母
	int countMax = pow(maxNum, n);
	//计算各骰子和出现的概率
	for (int i = n; i <= maxSum; i++) {
		cout << i << endl;
		cout << "概率: ";
		cout << curSum[flag][i] << "/" << countMax << " ≈ ";
		cout << ((double)(curSum[flag][i])) / countMax << endl;
	}

	//清理内存
	delete[] curSum[0];
	delete[] curSum[1];
	delete[] curSum;

}

61 扑克牌中的顺子

从扑克牌中随机抽5张牌,判断是不是一个顺子,即这5张牌是不是连续的

2~10为数字本身, A为1,J为11, Q为12, K为13,而大,小王可以看成任意数字

Testing case

• 功能测试(有一个/多个大小王，无大小王，有对子)
• 边界测试(nullptr)

Key

• 抽象建模 + 双指针

  1. 先对整型数组中的数字进行排序
  2. 对排序后的数组计算0:大小王的出现次数
  3. 从第一个不是0:大小王的位置起求各相邻数字的间隙数，并排除对子
  4. 通过判断大小王出现次数与相邻数字的间隙数大小，来判断是否大小王的张数能够填补非连续空隙，从而判断是否是顺子

  注意:

  1. 扑克牌中的顺子可抽象为计算机中的整型数组中的连续数字，大小王用0表示
  2. 相邻元素的比较判断可使用间隔为1的双指针遍历
  3. 相邻数字的间隙数 = data[big] - data[small] - 1
  4. 使用T(n) = O(nlogn) 的qsort排序，因为扑克牌只有13种牌，而时间复杂度仅当n足够大时才有意义

Answer

int Compare(const void* data1, const void* data2) {
	int d1 = *((int*)data1);
	int d2 = *((int*)data2);
	return d1 - d2;
}


bool IsContinuous(int* data, int length) {
	//判断异常
	if (data == nullptr || length <= 0) {
		isExcption = true;
		return false;
	}

	//设置记录扑克牌中记录 0:大小王，相邻数字间隙的变量
	int NumOfZero = 0;
	int NumOfGap = 0;

	//对数组进行排序
	qsort(data, length, sizeof(int), Compare);

	//记录数组中0出现的次数
	for (int i = 0; i < length; i++) {
		if (data[i] == 0) {
			NumOfZero++;
			if (NumOfZero > 2) {
				isExcption = true;
				return false;
			}
		}
	}	

	//记录数组中所有数字的相邻数字的间隙大小
	int small = NumOfZero;
	int big = small + 1;

	while (big != length) {
		//排除对子
		if (data[small] == data[big]) {
			return false;
		}
		//累加计算间隙数
		NumOfGap += data[big] - data[small] - 1;
		//向下遍历，移动游标
		small = big++;
	}

	//通过判断0:大小王是否能够填补空隙来判断是否为顺子
	return NumOfZero >= NumOfGap ? true : false;

}

62 圆圈中最后剩下的数字

0,1,..-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字

求出这个圆圈里剩下的最后一个数字

Testing case

• 功能测试(m<n或m>=n)
• 边界测试(0)
• 性能测试(n=4000,m=997)

Key

• 环形链表 T(n) = O(mn) S(n) = O(n)

  1. 使用双向链表模拟环状链表并将0至n-1的元素压入到链表中
  2. 剔除自0起的第m个元素，首先将迭代器自当前元素起移动至第m个元素(向后移动m-1次)，记录第m个元素的下一个元素，剔除第m个元素
  3. 自第m个元素在环状链表中的下一个元素起重复2，直至环状链表中的元素仅有一个

  注意:

  1. 使用双向链表list模拟环形链表，注意遍历至end()迭代器时需要重置与链表首部

• 数学分析 + 递归or循环 T(n) = O(n) S(n) = O(1)

  有点顶，先不作要求

Answer

bool isExcption = false;

int LastRemaining(int n, int m) {
	//判断异常
	if (n <= 0 || m <= 0) {
		isExcption = true;
		return -1;
	}

	//使用双向链表模拟环状链表
	list<int> RingList;

	//将0至n-1的元素压入到链表中
	for (int i = 0; i < n; i++) {
		RingList.push_back(i);
	}

	//设置遍历迭代器
	auto currentIte = RingList.begin();

	//剔除自0起的第m个元素,直至仅剩一个元素
	while (RingList.size() > 1) {
		//定位迭代器于自当前元素起的第m个元素
		for (int i = 1; i < m; i++) {
			currentIte++;
			if (currentIte == RingList.end()) {
				//通过手动设置来模拟环形链表
				currentIte = RingList.begin();
			}
		}

		//记录环状链表中当前元素的下一个元素
		auto nextIte = ++currentIte;
		if (nextIte == RingList.end()) {
			nextIte = RingList.begin();
		}

		//恢复currentIte迭代器指向元素
		currentIte--;

		//剔除元素
		RingList.erase(currentIte);

		//向下遍历
		currentIte = nextIte;
	}

	return *currentIte;

}

63 股票的最大利润

假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少?

例如,一只股票在某些时间节点的价格为{9,11,8,5,7,12,16,14},如果我们能在价格为5的时候买入并在价格为16时卖出,则能收获最大的利润11

Testing case

• 功能测试(数组无序/单调递增/单调递减)
• 边界测试(nullptr，数组只有两个数字)

Key

• 蛮力尾部遍历 + 打擂 T(n) = S(n2)

  1. 自数组尾部开始，逐个元素作卖出点，向前遍历元素组成(卖出,买入)数对打擂计算最大利润
  2. 直至卖出点为数组第二个元素

  注意:

  1. 暴力遍历，含多次重复计算，可进一步优化记录最小买入点并自首部遍历

• 最小买入 + 三指针 + 打擂 T(n) = S(n)

  1. 自首部遍历数组，通过curSell遍历数组，计算每一个元素(自第二个元素起)作卖出点时的最大利润
  2. 在进行本次利润计算前，先根据上次卖出点的值与最小买入点的值比较，更新最小买入点
  3. 计算本次最大利润并打擂记录至目前为止的最大利润
  4. 进行下一利润计算前，先更新preSell，curSell的状态

  注意:

  1. 设置三个指针分别记录最小买入点smallestBuy，当前卖出点curSell与上一次卖出点preSell
  2. curDiff = data[curSell] - data[smallestBuy] ，当前卖出点的最大利润为当前卖出值 - 之前最小买入值

Answer

bool isExcption = false;

//股票的最大利润
int MaxDiff(const int*, int);

int MaxDiff(const int* data, int length) {
	//判断异常
	if (data == nullptr || length < 2) {
		isExcption = true;
		return 0;
	}

	//设置记录股票最小买入点与当前卖出点的指针
	int smallestBuy = 0;
	int curSell = 1;

	//打擂记录big指向的元素作卖出点的最大利润
	int maxDiff = data[curSell] - data[smallestBuy];

	//记录上一次卖出点的价格并向下遍历
	int preSell = curSell++;

	//遍历剩余元素，记录剩余元素作卖出点的最大利润
	while (curSell < length) {
		//若上一次卖出点的值小于最小买入点的值，则应在上一点买入，更新最小买入点
		if (data[preSell] < data[smallestBuy]) {
			smallestBuy = preSell;
		}

		//计算当前最大利润
		int curDiff = data[curSell] - data[smallestBuy];
		//打擂记录到目前为止的最大利润
		if (curDiff >= maxDiff) {
			maxDiff = curDiff;
		}

		//向后遍历
		preSell = curSell;
		curSell++;
	}

	return maxDiff;

}

64 求 1+2+…+n

要求不能使用乘除法,for,while,if else,switch,case等关键字及条件判断语句(A?B:C)

Testing case

• 功能测试(5,10)
• 边界测试(0，1)

Key

• 围绕循环与递归展开

  1. 创造循环实现累加
  2. 无法在一个函数中通过if完成递归，则设置两个函数，一个函数作递归函数使用，一个函数作bacecase终止递归使用
  3. 通过类似bool类型的变量选择调用的函数，!!n , n>0时 !!n = true(1)，n=0时 !!n = false(0)

• 基于循环 - 构造函数 + 静态成员

  1. 创建一个类含两个静态成员变量，一个为N，一个为Sum，并初始化为0
  2. 设置相应的静态获取函数GetSum，用于返回静态成员变量Sum
  3. 在类的构造函数处对N进行累加，并使用Sum记录N的累加和
  4. 创建N个对象后，直接类名::GetSum()获取累加和

• 基于递归 - 函数指针

  1. 在递归函数中设置函数指针数组，并通过!!n来区分下标选择函数进行调用
  2. 当n=0时，!!0 = 0 ，选择arr[0]函数终止递归

  注意:

  1. 设置一个静态函数指针数组存放两个函数地址，静态数组只会初始化一次

• 基于递归 - 虚函数

  1. 父类的待重写虚函数作终止递归函数
  2. 子类的重写函数中，根据!!n选择 父类/子类重写 函数进行绑定，调用GetSum方法
  3. 子类设置一个基类指针数组，并在构造函数中使用相应的指针参数完成初始化

  注意:

  1. 通过虚函数的动态绑定完成对递归函数的选择

• 基于递归 - 非类型模板参数 + 模板特化

  1. 使用非类型模板类并基于枚举常量元素完成递归累加
  2. 递归终止时的枚举元素值由特化模板确定

  注意:

  1. 当一个模板的参数非类型而是一个编译期间可确定的常量时，在模板中可直接使用该常量
  2. 递归编译时的递归深度受限，n不能太大
  3. n必须能够在编译时确定，不能动态输入
  4. 使用枚举常量元素的值完成累加
  5. 编译时的递归
  6. ::作用域运算符 若运算符前无类/命名空间/结构体，则默认为全局作用域，可通过该运算符取对应作用域中共有的成员

Answer

1.

//基于循环 - 构造函数
class GSum;
int GetSumFrom1TonByClass(int);

class GSum {

public:

	GSum() {
		//记录当前数字
		N++;
		//记录累加和
		Sum += N;
	}

	static void ResetSum() {
		N = Sum = 0;
	}

	static int GetSum() {
		return Sum;
	}

private:
	static int N;
	static int Sum;
};

//成员初始化
int GSum::N = 0;
int GSum::Sum = 0;

int GetSumFrom1TonByClass(int n) {
    
	//重置
	GSum::ResetSum();

	//创建n个GSum对象，进而累加1-n的和
	GSum* arr = new GSum[n];
	//清理内存
	delete[] arr;
	arr = nullptr;

	return GSum::GetSum();
}

2.

//基于递归 - 函数指针
typedef int(*func) (int);

int GetSumByPointerBaseCase(int);
int GetSumByPointer(int);

int GetSumByPointer(int n) {
	static func arr[2] = { GetSumByPointerBaseCase,GetSumByPointer };
	return arr[!!n](n - 1) + n;
}

int GetSumByPointerBaseCase(int n) {
	return 0;
}

3.

//基于递归 - 虚函数
class GSumByVirtualBase {

public:
	virtual int GetSum(int n) {
		return 0;
	}
};

class GSumByVirtual : public GSumByVirtualBase {

public:
	GSumByVirtual(GSumByVirtualBase* GBS) :GSumByVirtualBase() {
		arr[0] = GBS;
		arr[1] = this;
	}

	int GetSum(int n) override{
		return n + arr[!!n]->GetSum(n - 1);
	}
private:
	GSumByVirtualBase* arr[2];
};

int GetSumByVirtual(int);

int GetSumByVirtual(int n) {

	GSumByVirtualBase* GBS = new GSumByVirtualBase();
	GSumByVirtual* GS = new GSumByVirtual(GBS);

	return GS->GetSum(n);

}

4.

//基于递归 - 非类型模板参数

template<const int n>
struct GetSumByTem
{
	enum value { N = GetSumByTem<n - 1>::N + n };
};

template<>
struct GetSumByTem<1>
{
	enum value { N = 1 };
};

65 不用加减乘除做加法

写一个函数,求两个整数之和,要求在函数体内不得使用”+”,”-“,”×”,”÷”四则运算符号

Testing case

• 功能测试(整数，负数)
• 边界测试(0)

Key

• 异或运算 + 与运算 + 移位运算 - 递归

  1. 通过异或运算，计算两数不产生进位的和
  2. 通过与运算后左移一位，计算两数产生的进位值
  3. 递归向下计算1,2结果的和，直至无进位产生，即进位值为0，则返回最终结果

  注意:

  1. 可使用底层的位运算模拟加减乘除运算
  2. 加法的运算法则
     • 计算两数不产生进位的和
     • 计算两数产生的进位值
     • 计算上述两个结果的和
  3. 二进制下的进位，逢2进1，若某位产生进位，则应左移一位(乘基数2)，才为进位值

• 异或运算 + 与运算 + 移位运算 - 循环

  1. 通过异或运算，计算两数不产生进位的和
  2. 通过与运算后左移一位，计算两数产生的进位值
  3. 循环计算1,2结果的和，但是在进行下次计算之前需要记录本次计算的结果作下次的加数
  4. 直至第二个加数(进位值)为0终止循环
  

Answer

1.

bool isExcption = false;

//加法计算 - 递归

int PlusByRecursive(int num1, int num2) {

	//base case 
	if (num2 == 0) {
		return num1;
	}

	//记录两数不产生进位的和 异或运算结果
	int NoCarrySum = num1 ^ num2;
	//记录两数产生进位的和 与运算结果后左移一位
	int Carry = (num1 & num2) << 1;
	//计算上述两个结果的和
	return PlusByRecursive(NoCarrySum, Carry);
}

2.

bool isExcption = false;

//加法计算 - 循环

int PlusNotByRecursive(int num1, int num2) {

	do {

		//a 记录两数不产生进位的和 异或运算结果
		int NoCarrySum = num1 ^ num2;
		//b 记录两数产生进位的和 与运算结果后左移一位
		int Carry = (num1 & num2) << 1;
		//下次循环计算a+b，但是在进行下次计算之前需要记录本次计算的结果作下次的加数
		num1 = NoCarrySum;
		num2 = Carry;

	} while (num2 != 0);

	return num1;
}

65.1 不使用新的变量交换两个变量的值

不使用新的变量交换两个变量的值

Key

• 异或运算

  注意:

  1. a0,b0为初始值，a1,b1为交换后的值
  2. 第一次异或结果含a0,b0
  3. 第二次异或将 (a0^b0) ^ b0，剔除结果中的b0，留下a0存于b1中，此时b1已交换为a0
  4. 第三次异或将 (a0^b0) ^ b1，剔除结果中的a0，留下b0存于a1中，此时完成交换

• 加减法运算

  注意:

  1. a0,b0为初始值，a1,b1为交换后的值
  2. 第一次加法结果为 a0 + b0
  3. 第二次减法将 (a0+b0) - b0，剔除结果中的b0，留下a0存于b1中，此时b1已交换为a0
  4. 第三次减法将 (a0+b0) - b1，剔除结果中的a0，留下b0存于a1中，此时完成交换

Anwser

1.

a = a ^ b;
b = a ^ b;
a = a ^ b;

2.

a = a + b;
b = a - b;
a = a - b;

66 构建乘积数组

暂略

67 把字符串转换为整数

写一个函数，完成函数库中atoi函数的功能，把字符串转换为整数

Testing case

• 功能测试(正数，负数，0)
• 边界测试(最大正整数，最小负整数)
• 特殊输入测试(nullptr,””,含非数字字符)

Key

• 基本 字符串 -> 整数 方法

  1. 设置累加各位数字的long long变量num，并初始化为0

  2. 自首部遍历字符串，先根据首位判断数字正负情况，设置isNegative值

  3. 若2含+/-号，设置isNegative值后结束本次子循环，向下遍历

  4. 若当前判断字符是数字字符，则记录各位数字(数字+位)于num中，num = num * 10 + (*p - ‘0’)

  5. 进行下次记录前，先判断是否发生溢出

  6. 重复4,5直至遍历至字符串尾部，此时完成对整数绝对值的记录

  7. 根据isNegative返回正/负整数num

• 非法字符的考量

  isNumber完成是否为数字字符的考量，排除空字符串，非法字符串

• 整数的三种情况

  1. 带+号的正数
  2. 不带+号的正数
  3. 带-号的负数

  注意:

  1. 在对字符串各位进行判断并累加时，注意首位的字符情况
  2. 若为+号，更新状态，结束本次循环，继续向下遍历
  3. 若为-号，更新状态，结束本次循环，继续向下遍历
  4. 若为数字，则需要记录，然后向下遍历

• 异常处理

  设置全局变量作异常判断

  若出现异常，在设置返回值为0并设置全局变量，最后通过全局变量值完成异常判断

  注意:

  1. 数字字符0与发生异常返回值相同，切记不要忘记对全局变量的判断来区分这两种返回情况

• 溢出判断

  1. 无法通过int型变量完成溢出的判断，借助范围更大的long long型完成溢出判断

     int型最大值 = numeric_limits::max() = 0x7FFFFFFF
     int型最小值 = numeric_limits::min() = (signed int)0x80000000

  2. 进行溢出判断时，不能仅根据绝对值的大小完成溢出判断，而需要结合整数的正负情况来完成最大正整数与最小负整数的溢出判断

• 一元减运算符

  作用于单个操作数以产生新值

  注意:

  1. 当一元减运算符作用于无符号整数时，返回值不是其取反值，而是该无符号整数本身
  2. -2147483648表达式分两阶段进行
     • 判断2147483648作为int型已溢出，因此将其当做unsigned int处理
     • -2147483648结果为2147483648
  3. -2147483648 != (signed int)2147483648

Answer

//字符串转换为整数
bool isExcption = false;

bool isNumber(char* str) {

	bool isNum = true;

	int len = strlen(str);

	//判断空串
	if (len == 0) {
		isNum = false;
	}

	//判断是否为数字字符串，含空格判断，以及正负号判断
	for (int i = 0; i < len; i++) {

		//判断首字符是否为+,-号，若均不是，则进而判断是否为数字字符
		if (i == 0 && str[i] == '+' || i == 0 && str[i] == '-') {
			continue;
		}
		//判断剩余字符是否为数字字符
		if (str[i]<'0' || str[i]>'9') {
			isNum = false;
			break;
		}
	}

	return isNum;
}

int StrToInt(char* str) {
	//边界异常判断
	if (str == nullptr || !isNumber(str)) {
		isExcption = true;
		return 0;
	}

	//转换字符串
	char*p = str;

	long long num = 0;

	//判断是否为首位
	bool isFirst = true;
	bool isNegative = false;

	while (*p != '\0') {
		//判断正负号
		if (isFirst && (*p) == '-') {
			isNegative = true;

			//向下遍历
			p++;
			//更新首位判断遍历状态
			isFirst = false;

			continue;
		}
		else if (isFirst && (*p) == '+') {
			//向下遍历
			p++;
			//更新首位判断遍历状态
			isFirst = false;

			continue;
		}

		//累加转换为数字
		num = num * 10 + (*p - '0');

		//进行下次前先判断当前是否产生越界溢出,正数判断最大正整数溢出，负数判断最小负整数溢出
		if ((!isNegative && num > 0x7fffffff) || (isNegative && num < (signed int)0x80000000)) {
			isExcption = true;
			return 0;
		}
	
		//向下遍历
		p++;
		//更新首位判断遍历状态
		isFirst = false;
	}

	return isNegative ? -num : num;

}

68 链表的第一个公共结点

输入两个链表,找出它们的第一个公共节点

Testing case

• 功能测试(两个链表 有/无 公共结点，两个链表的公共结点位于首部/尾部/中部)
• 边界测试(nullptr)

Key

• 两个链表组合型

  含公共结点的两个链表组合型可以为Y型(公共结点位于链表中间)，V型(公共结点位于链表末尾)，l型(公共结点位于链表首部)

  上为链表首部，下为链表尾部

• 蛮力首部遍历 T(n) = O(mn)

• 尾部遍历 + 辅助栈 T(n) = O(m+n) S(n) = O(m+n)

  1. 将两个链表元素分别压入两个栈，设置pCommonNode指针指向公共结点，初始为nullptr
  2. 判断两个栈的栈顶结点是否为公共结点
  3. 若是公共结点，则使用pCommonNode指针记录当前公共结点，弹出栈顶结点后继续2，直至某一栈为空
  4. 若不是公共结点，则跳出循环，返回pCommonNode

  注意:

  1. 单链表无法完成尾部遍历，因此使用辅助栈完成结点的尾部遍历
  2. 自尾部开始查找第一个产生分叉的结点(两链表自该结点后的下一个结点值不同)，该结点即为第一个公共结点

• 同步移动 T(n) = O(m+n) S(n) = O(1)

  1. 设置较长链表的遍历指针pLongerHead，默认为pHead1
  2. 计算两个链表的表长并计算偏移量pOffset，初始为pLen1-pLen2
  3. 根据两链表表长判断使pLongerHead指向较长链表的表头
  4. 先将pLongerHead后移|pOffset|个单位
  5. 同步移动pShorterHead，pLongerHead，使用pCommonNode记录第一次值相同的结点，直至表尾
  6. 返回pCommonNode

  注意:

  1. 将较长链表先向后偏移pOffset(两链表长度之差的绝对值)，因为确保两个链表遍历指针同时到达尾部
  2. 若两个表长不同的链表含公共结点，则该公共结点一定不存在于较长链表的前pOffset个结点中
  3. 取代蛮力法中固定一链表结点遍历另一个链表的方法，时间效率更高

Answer

1.

ListNode* GetFirstCommonNodeByStack(ListNode* pHead1, ListNode* pHead2) {
	//异常判断
	if (pHead1 == nullptr || pHead2 == nullptr) {
		isExcption = true;
		return nullptr;
	}

	//设置两个辅助栈分别存放两个链表的结点
	stack<ListNode*> pStack1;
	stack<ListNode*> pStack2;

	//遍历两个链表并分别将结点压栈
	ListNode* pNode1 = pHead1;
	ListNode* pNode2 = pHead2;

	while (pNode1 != nullptr) {
		pStack1.push(pNode1);
		pNode1 = pNode1->pNext;
	}

	while (pNode2 != nullptr) {
		pStack2.push(pNode2);
		pNode2 = pNode2->pNext;
	}

	//根据栈中结点从尾结点开始向前比较是否存在 Y or V 型公共链表结点
	//设置指针存放公共结点的地址
	ListNode* pCommonNode = nullptr;

	while (pStack1.size() != 0 && pStack2.size() != 0) {

		if (pStack1.top()->pValue == pStack2.top()->pValue) {
			pCommonNode = pStack1.top();
		}
		else {
			break;
		}

		pStack1.pop();
		pStack2.pop();
	}

	return pCommonNode;

}

2.

int GetListLength(ListNode* pHead) {

	ListNode* pNode = pHead;

	int len = 0;
	while (pNode != nullptr) {
		len++;
		pNode = pNode->pNext;
	}

	return len;
}

ListNode* GetFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
	//异常判断
	if (pHead1 == nullptr || pHead2 == nullptr) {
		isExcption = true;
		return nullptr;
	}

	//设置两个指针分别指向较长的链表头和较短的链表头
	ListNode* pLongerHead = pHead1;
	ListNode* pShorterHead = pHead2;

	//取两个链表的长度，并获取两链表长度之差
	int pLen1 = GetListLength(pHead1);
	int pLen2 = GetListLength(pHead2);
	int pOffset = pLen1 - pLen2;

	//使两个指针分别指向较长的链表头和较短的链表头
	if (pLen2 > pLen1) {
		pLongerHead = pHead2;
		pShorterHead = pHead1;
		//使差值取正
		pOffset = -pOffset;
	}

	//先将指向长度较长链表的指针后移pOffset，使两个指针同步移动
	for (int i = 0; i < pOffset; i++) {
		pLongerHead = pLongerHead->pNext;
	}

	//向后遍历，直至找到第一个公共结点或至末尾
	while (pLongerHead != nullptr && pShorterHead != nullptr && pLongerHead->pValue != pShorterHead->pValue) {
		pLongerHead = pLongerHead->pNext;
		pShorterHead = pShorterHead->pNext;
	}

	ListNode* pCommonNode = pLongerHead;

	return pCommonNode;

}

69 树中两个结点的最低公共祖先

输入两个树节点,求它们的最低公共祖先

二叉搜索树，含/不含 指向父结点指针的普通树

Testing case

• 功能测试(普通二叉树，退化为链表的树)
• 边界测试(nullptr)

Key

• 最低公共祖先

  若两个结点为同一个结点，则返回其本身

  若两个结点在同一条路径上，则返回更靠近根结点的结点

• 二叉搜索树

  1. 由根结点开始作判断，若当前结点比两结点值都大，则在此根结点的左子树中查找
  2. 若当前结点比两结点值都小，则在此根结点的右子树中查找
  3. 若当前结点值介于两结点值之间或等于其中一者，则返回该根结点

  注意:

  1. 由于二叉搜索树性质，所以最低公共祖先一定是值介于两者之间的的结点(含等于某一结点)
  2. 注意若结点不在树结构中，本方法无法作出异常判断，需要先判断结点是否位于树结构中

• 含指向父结点指针的普通树

  1. 自两个结点开始，分别依据pParent指针向上遍历，直接将遍历的结点分别压入栈
  2. 设置记录最低公共祖先的指针pCommon，初始为nullptr
  3. 自两个栈的栈顶开始找寻(自两链表尾部开始)第一个不相等结点，若两栈顶结点值相同，则记录该结点并弹出向下找寻，直至某一个栈为空
  4. 返回pCommon

  注意:

  1. 转换为两个链表的第一个公共结点，两个链表的表头分别为pNode1，pNode2，表尾均为pHead
  2. 注意若结点不在树结构中，本方法返回nullptr
  3. 栈由栈顶->栈底 存放 链表尾部->链表首部

• 不含指向父结点指针的普通树

  获取根节点 -> 要求结点 的路径链表

  1. 基于先序遍历，使用两个双向链表List，分别记录到两个结点的路径上的所有结点
  2. 先将记录当前遍历结点，并判断当前路径是否为要求路径，即当前压入结点是否等于给定结点value值
  3. 若当前压入结点等于给定结点value值，则已找到要求路径，设置返回值，返回结果
  4. 若不等，则进而在该结点的左子树中继续查找路径
  5. 当左子树中仍不存在要求路径时，进而在该根结点的右子树中查找路径
  6. 最后若hasPath仍等于false，表明要求路径不含当前结点，剔除已记录的当前结点
  7. 返回判断结果

  根据路径链表找寻最低公共祖先

  1. 正向遍历两个路径链表，若遍历的两个结点值相同，则表明该结点可能为其公共祖先，记录于pCommon指针中
  2. 若遍历的两个结点值不相同，则上一次pCommon指针记录结点即为最低公共祖先

  注意:

  1. 普通树的递归遍历只能是基于前序/中序/后序遍历，对先序遍历进行改良，添加遍历左右子树的条件
  2. 对左右子树遍历的先决条件是当前仍为找到要求路径(hasPath==false)
  3. 注意若要求路径不含当前结点，需要回溯剔除
  4. 对路径链表的正向遍历，即从尾部遍历(根节点)找寻两链表的的第一个公共结点

Answer

1. 二叉搜索树

TreeNode* GetLastCommonNodeCore(TreeNode* pHead, TreeNode* pNode1, TreeNode* pNode2) {

	//base case
	if (pHead == nullptr) {
		return nullptr;
	}

	//若当前结点比两个结点值都大，根据二叉搜索树性质，在其左子树中继续查找
	if (pHead->pValue > pNode1->pValue && pHead->pValue > pNode2->pValue) {
		return GetLastCommonNodeCore(pHead->pLeft, pNode1, pNode2);
	}

	//若当前结点比两个结点值都小，根据二叉搜索树性质，在其右子树中继续查找
	else if (pHead->pValue < pNode1->pValue && pHead->pValue < pNode2->pValue) {
		return GetLastCommonNodeCore(pHead->pRight, pNode1, pNode2);
	}

	//此时pHead结点值要么介于两结点之间，要么等于其中一者的值
	else
		return pHead;
}

TreeNode* GetLastCommonNode(TreeNode* pHead, TreeNode* pNode1, TreeNode* pNode2) {
	//判断异常
	if (pHead == nullptr || pNode1 == nullptr || pNode2 == nullptr) {
		isException = true;
		return nullptr;
	}																													//应添加判断两结点是否位于树结构中的异常判断
	return GetLastCommonNodeCore(pHead, pNode1, pNode2);

}

2. 含指向父结点指针的普通树

struct TreeNode
{
	int pValue;
	TreeNode* pLeft;
	TreeNode* pRight;
	TreeNode* pParent;
};

TreeNode* GetLastCommonNodeCoreByStack(TreeNode* pNode1, TreeNode* pNode2) {

	//设置两个辅助栈
	stack<TreeNode*> List1;
	stack<TreeNode*> List2;

	//将两个链表结点分别压栈
	while (pNode1 != nullptr) {
		List1.push(pNode1);
		pNode1 = pNode1->pParent;
	}

	while (pNode2 != nullptr) {
		List2.push(pNode2);
		pNode2 = pNode2->pParent;
	}

	//设置记录公共祖先的指针
	TreeNode* pCommon = nullptr;

	//自链表尾部开始找寻第一次产生分叉的结点
	while (!List1.empty() && !List2.empty() && List1.top() == List2.top()) {
		
		pCommon = List1.top();
		List1.pop();
		List2.pop();
	}		

	return pCommon;
}

TreeNode* GetLastCommonNode(TreeNode* pNode1, TreeNode* pNode2) {
	//判断异常
	if (pNode1 == nullptr || pNode2 == nullptr) {
		isException = true;
		return nullptr;
	}

	return GetLastCommonNodeCoreByStack(pNode1, pNode2);

}

3. 不含指向父结点指针的普通树

//普通树中两个结点的最低公共祖先

TreeNode* GetLastCommonNodeCore(list<TreeNode*>& PathList1, list<TreeNode*>& PathList2) {

	//设置记录公共结点的指针
	TreeNode* pCommon = nullptr;

	//正向遍历两个链表(根节点为头结点)，找寻第一个产生分叉的结点
	auto ite1 = PathList1.begin();
	auto ite2 = PathList2.begin();

	while (ite1 != PathList1.end() && ite2 != PathList2.end()) {
		
		if ((*ite1)->pValue == (*ite2)->pValue) {

			//记录当前公共结点
			pCommon = *ite1;
			//向后遍历
			ite1++;
			ite2++;
		}
		else {
			break;
		}

	}
	return pCommon;
}


bool GetLastCommonNodePath(TreeNode* pHead, TreeNode* pNode, list<TreeNode*>& PathList) {

	if (pHead == nullptr) {
		return false;
	}

	//设置返回值记录变量
	bool hasPath = false;
	
	//路径链表中记录当前遍历结点
	PathList.push_back(pHead);	

	//判断当前压入结点构成的路径是否为要求的路径
	if (pHead->pValue == pNode->pValue) {
		hasPath = true;
	}

	//若当前压入结点构成的路径不满足要求，则在当前结点的左子树中继续找寻路径
	if (!hasPath && pHead->pLeft != nullptr)
		hasPath = GetLastCommonNodePath(pHead->pLeft, pNode, PathList);
	//若左子树中未找寻到路径，则在当前结点的右子树中继续找寻路径
	if (!hasPath && pHead->pRight != nullptr)
		hasPath = GetLastCommonNodePath(pHead->pRight, pNode, PathList);

	//回溯
	if(!hasPath)
		PathList.pop_back();

	return hasPath;

}

TreeNode* GetLastCommonNode(TreeNode* pHead, TreeNode* pNode1, TreeNode* pNode2) {
	//判断异常
	if (pHead == nullptr || pNode1 == nullptr || pNode2 == nullptr) {
		isException = true;
		return nullptr;
	}

	//创建存储路径的辅助空间
	list<TreeNode*> PathList1;
	list<TreeNode*> PathList2;

	//设置返回值
	TreeNode* pCommonNode = nullptr;

	//获取根结点到两个结点的路径，若有一条路径不存在，则无公共结点
	if (GetLastCommonNodePath(pHead, pNode1, PathList1) && GetLastCommonNodePath(pHead, pNode2, PathList2)) {
		pCommonNode = GetLastCommonNodeCore(PathList1, PathList2);
	}

	return pCommonNode;
}