左神算法中级班第七课[C++代码]

• 第一题：纯code问题
• • 代码
• 第二题：找到数组中没出现的数字
• • 代码
• 第三题：3的倍数的另一种思路
• 第四题：大哥打赏问题
• • 代码
• 第五题：求完全二叉树的节点个数
• • 代码
• 第六题：图的问题==大魔王问题，很难==
• • 代码

声明：博客根据左神在毕站的讲课视频整理，代码是根据左神的java代码版本改写为c++版本
代码为自己动手改写，未经应用不能转载

github代码链接：
https://github.com/hjfenghj/zuoshen_middlecalss

技巧：goto语句的使用，注意continue，break和goto的区别

• code

#include
#include
#include

using namespace std;

class PROBLEM01
{
public:
	//求得数字的长度
	vector S{ "W","Q","B","S","L" };
	vector S_19 = { "One ", "Two ", "Three ", "Four ", "Five ", "Six ",
							"Seven ", "Eight ", "Nine ", "Ten ", "Eleven ", "Twelve ",
							"Thirteen ", "Fourteen ", "Fifteen ", "Sixteen ", "Seventeen ",
							"Eighteen ", "Nineteen " };

	vector S_0 = { "Twenty ", "Thirty ", "Forty ", "Fifty ",
							"Sixty ", "Seventy ", "Eighty ", "Ninety " };

	string str_res = "";

	int pown(int N, int L)
	{
		int res = 1;
		int temp = N;
		while (L != 0)
		{
			
			if (L & 1 == 1)
			{
				res *= temp;
				temp = temp * temp;
			}
			else
				temp = temp * temp;
			L = L >> 1;
		}
		return res;
	}
	//求出每位的数字,并添加单位变成字符串
	string get_string(int N)
	{
		if (N <= 19)
			return S_19[N-1];
		else if (N / 10 / 10 == 0)
			return S_0[N / 10 % 10 - 2];

		//其他情况
		int idx = 4;
		int L = 0;//数字的长度
		while (N / pown(10, idx) == 0)
		{
			idx--;
		}
		L = idx;

		while (L >= 0)
		{
			int cur = N / pown(10, L);
			char flag = 'L';

			if (cur == 0 && str_res[str_res.size() - 1] == flag)
				goto FFF;
			else if (cur == N)
				str_res += to_string(cur);
			else if(cur==0)
				str_res +=  S[4];
			else
				str_res += to_string(cur) + S[4 - L];

			FFF:
			N = N % pown(10,L);
			L = L - 1;
		}
		return str_res;
	}
};

int main()
{
	int  N = 19120;
	PROBLEM01 P;
	string str = P.get_string(N);
	string new_str(str.begin(), str.end() - 1);
	cout << ((str[str.size()-1] == '0') ? new_str : str )<< endl;;
	return 0;
}

• 思路

1. 哈希表解法，时间复杂度和空间复杂度都为O(n)
2. 时间复杂度O(n),空间复杂度O(1)
   遍历数组元素，将元素i放在第i-1个位置；之后没有地方放法元素就是结果

• code

class PROBLEM02
{
public:

	void get_res(vector& Arr)
	{
		for (int i = 0; i < Arr.size(); i++)
		{
			process(Arr[i], Arr);
		}
		for (int i = 0; i < Arr.size(); i++)
		{
			if (Arr[i] != i + 1)
				cout << i+1 << " ";
		}
		return;
	}
	void process(int val, vector& Arr)
	{
		while (Arr[val - 1] != val)
		{
			int temp = Arr[val - 1];
			Arr[val - 1] = val;
			val = temp;
		}
	}
};

技巧：一个整数每个位置上的数相加如果是3的倍数，那么这个整数就是3的倍数；

1+12+137=150是3的倍数，所以112137也是3的倍数，137112和137121也是3的倍数；

递归边界条件的寻找
平凡解作为终止条件

题目添加一个条件：start和end都是偶数=

• 思路
  递归解题的时候，需要一个终止条件来终止递归的套娃；就是为了防止无限套用，比如说下图：
  
  所以需要选择完备的终止条件；
• 思路
  使用平凡解作为终止条件
  平凡终止条件1：全部使用点赞的方式到达目标积分需要花费的C币
  平凡终止条件2：当前的积分不可能是目标积分的两倍

注意：这里的终止条件都是通过业务分析得到到，而且远不止一个，但是只要终止条件选的对，只需要一个就可以得到结果；终止条件越多剪枝越充分，跳出循环越快，可以节省无效的递归操作

• code

class TreeNode
{
public:
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int v)
	{
		val = v;
	}
};

class PROBLEM05
{
public:
	int get_depth(TreeNode* node){
		int depth = 0;
		while (node){
			depth++ ;
			node = node->left;
		}
		return depth;
	}
	//N的L次方
	int pown(int N, int L){
		int res = 1;
		int temp = N;
		while (L != 0){
			if (L & 1 == 1){
				res *= temp;
				temp = temp * temp;
			}
			else
				temp = temp * temp;
			L = L >> 1;
		}
		return res;
	}

	int process(TreeNode* node, int depth){
		int ans = 0;
		if (node->left == nullptr && node->right==nullptr)
			return 1;
		//右数的最大深度到达最大深度
		if (get_depth(node->right) == depth - 1){
			node = node->right;
			ans = pown(2, depth - 1) + process(node,depth-1);
		}
		//右树没有到达最大高度，那么这是右树的右树满树
		else if (get_depth(node->right) < depth - 1){
			int L = get_depth(node->right);
			node = node->left;
			ans = pown(2, L) + process(node, depth - 1);
		}
		return ans;
	}

	int get_res(TreeNode* node){
		int d = get_depth(node);//最大深度,全文贯穿
		cout << d << endl;
		int ans = process(node, d);
		return ans;
	}
};

技巧：完全二叉树某节点A如果A的右节点的最大深度达到了树A的最大深度，那么A的左子树是满树；图A的右节点的最大深度没有达到最大深度，那么A的右节点的右节点是满树

• 思路1
  遍历二叉树，计算节点数

• 思路2
  完全二叉树某节点A如果A的右节点的最大深度达到了树A的最大深度，那么A的左子树是满树；图A的右节点的最大深度没有达到最大深度，那么A的右节点的右节点是满树；

  代码

• code

#include
#include

using namespace std;

class TreeNode
{
public:
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int v)
	{
		val = v;
	}
};

class PROBLEM05
{
public:
	int get_depth(TreeNode* node){
		int depth = 0;
		while (node){
			depth++ ;
			node = node->left;
		}
		return depth;
	}
	//N的L次方
	int pown(int N, int L){
		int res = 1;
		int temp = N;
		while (L != 0){
			if (L & 1 == 1){
				res *= temp;
				temp = temp * temp;
			}
			else
				temp = temp * temp;
			L = L >> 1;
		}
		return res;
	}

	int process(TreeNode* node, int depth){
		int ans = 0;
		if (node->left == nullptr && node->right==nullptr)
			return 1;
		//右数的最大深度到达最大深度
		if (get_depth(node->right) == depth - 1){
			node = node->right;
			ans = pown(2, depth - 1) + process(node,depth-1);
		}
		//右树没有到达最大高度，那么这是右树的右树满树
		else if (get_depth(node->right) < depth - 1){
			int L = get_depth(node->right);
			node = node->left;
			ans = pown(2, L) + process(node, depth - 1);
		}
		return ans;
	}

	int get_res(TreeNode* node){
		int d = get_depth(node);//最大深度,全文贯穿
		cout << d << endl;
		int ans = process(node, d);
		return ans;
	}
};
int main()
{
	TreeNode* root = new TreeNode(1);
	root->left = new TreeNode(2);
	root->right = new TreeNode(3);
	root->left->left = new TreeNode(4);
	root->left->right = new TreeNode(5);
	root->right->left = new TreeNode(6);
	//root->right->right = new TreeNode(7);

	PROBLEM05 P;
	int ans = P.get_res(root);
	cout << ans << endl;
	return 0;
}

堆的应用，图的数据结构；使用map存储节点的父节点

• 思路：
  1） 根据给出的矩阵，得到一个map映射，记录节点与节点的父节点，得到图中的出度为1的一个节点
  2）建立一个新的map映射，>,记录第i个节点到到达最后一个节点的信息，表示从第i个任务开始，到最后一个任务花费的时间和获得的钱数，因为第i个节点出度可能大于1，所以节点i到最后一个节点的路径也可能大于1，所以使用map记录路径上所有节点信息之和；3）map中存的数据进行清洗，存在一个优先队列中，同样的时间只保留得到回报多的路径；然后按时间建立小根堆
  4）将第三步第一次清洗后的小根堆中的数据，整合到一个map；只保留时间增加，积分也增加的；
  5） 在大map中找到第一个小于等于 规定时间内得数据；

• code

#include
#include
#include