26 - 47

26.树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构，即 A中有出现和B相同的结构和节点值。

输入：

解：

方法：

只要主树A有这一部分，B就是他的子树。DFS深度遍历

bool isSubStructure(TreeNode* father, TreeNode* son) {
	if (father == NULL || son == NULL)//空树不是任意一个树的子结构
		return false;

	return dfs(father, son) ||
		isSubStructure(father->left, son) || isSubStructure(father->right, son);
}
bool dfs(TreeNode* father, TreeNode* son) {
	if (son == NULL) //当不能有相同剩余节点，(son == NULL && father == NULL)
		return true;
	if (father == NULL)
		return false;
	if (son->val != father->val)
		return false;
	return dfs(father->left, son->left) && dfs(father->right, son->right);
}

27.二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。
输入：
方法：

层序遍历后，reserve
dfs递归

TreeNode* mirrorTree(TreeNode* root) {
	// if(root==NULL)
	//     return NULL;
	// queue<TreeNode*>q;
	// q.push(root);
	// while(!q.empty()){
	//     TreeNode* tmp = q.front();
	//     q.pop();
	//     swap(tmp->left,tmp->right);
	//     if(tmp->left) q.push(tmp->left);
	//     if(tmp->right) q.push(tmp->right);
	// }
	// return root;
	if (root == NULL)
		return NULL;

	//第一个节点交换
	TreeNode* tmp = root->left;
	root->left = root->right;
	root->right = tmp;

	//接下来的节点交换
	mirrorTree(root->left);
	mirrorTree(root->right);
	return root;
}

28.对称的二叉树

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
输入：

方法：

dsf遍历看是否满足要求，左对右，右对左

bool isSymmetric(TreeNode* root) {
	if (root == NULL)return true;

	return dfs(root->left, root->right);
}
bool dfs(TreeNode* left, TreeNode* right) {
	if (left == NULL && right == NULL)//两边为空，真
		return true;
	if (left == NULL || right == NULL)//一边为空，假
		return false;
	if (left->val != right->val)
		return false;
	return dfs(left->right, right->left) && dfs(right->right, left->left);
}

29.顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
输入：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
方法：

边界判断：上下左右，逐渐缩小范围

vector<int> spiralOrder(vector<vector<int>>& matrix) {
	vector<int>res;
	if (matrix.empty())
		return res;

	int up = 0;
	int down = matrix.size() - 1;
	int left = 0;
	int right = matrix[0].size() - 1;
	while (1) {
		//左往右
		for (int i = left; i <= right; i++)
			res.push_back(matrix[up][i]);
		if (up == down)return res;
		up++;
		//上往下
		for (int i = up; i <= down; i++)
			res.push_back(matrix[i][right]);
		if (left == right)return res;
		right--;
		//右往左
		for (int i = right; i >= left; i--)
			res.push_back(matrix[down][i]);
		if (up == down)return res;
		down--;
		//下往上
		for (int i = down; i >= up; i--)
			res.push_back(matrix[i][left]);
		if (left == right)return res;
		left++;
	}
	return res;
}

30.包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
输入：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); –> 返回 -3.
minStack.pop();
minStack.top(); –> 返回 0.
minStack.min(); –> 返回 -2.

方法：

空间换时间，入栈两个数

stack<int>arr;

void push(int x) {
	if (arr.empty()) {
		arr.push(x);
		arr.push(x);
	}
	else {
		if (x < arr.top()) {
			arr.push(x);
			arr.push(x);
		}
		else {
			int temp = arr.top();
			arr.push(x);
			arr.push(temp);
		}

	}
}
void pop() {
	arr.pop();
	arr.pop();
}

int top() {
	int temp = arr.top();
	arr.pop();
	int temp1 = arr.top();
	arr.push(temp);

	return temp1;
}

int min() {
	return arr.top();
}

31.栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

输入：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。

方法：

利用辅助栈

bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
	stack<int>vis;
	int index = 0;
	for (int i = 0; i < pushed.size(); i++) {
		vis.push(pushed[i]);
		while (!vis.empty() && vis.top() == popped[index]) {
			vis.pop();
			index++;
		}
	}
	return vis.empty() ? true : false;
}

32-1.从上到下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
输入：
方法：

利用队列层序遍历
关键点：int size = q.size() 然后for(int i =0;i<size;i++)
初始化可以vector(arr.rbegin().arr.rend());

vector<int> levelOrder(TreeNode* root) {
	//利用队列层序遍历
	if (root == NULL)
		return {};
	queue<TreeNode*>q;
	q.push(root);

	vector<int>res;
	while (!q.empty()) {
		int size = q.size();
		for (int i = 0; i < size; i++) {
			TreeNode* temp = q.front();
			int num = temp->val;
			res.push_back(num);
			q.pop();

			if (temp->left)q.push(temp->left);
			if (temp->right)q.push(temp->right);
		}
        
        
	}
	return res;
}
//如果需要保存节点
//index = !index;
//if(index)        
//    res.push_back(vector<int>(arr.rbegin(), arr.rend()));      
//else
	  res.push_back(arr);

32-2.从上到下打印二叉树 II

32-3.从上到下打印二叉树 III

33.二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
输入：
方法：

二叉搜索树：左 > 中 > 右
后序遍历：左右中
根据输入的数组是后序遍历，区分区间来判断数的值是不是对的上

bool verifyPostorder(vector<int>& postorder) {
	if (postorder.size() < 2)return true;
	return dfs(postorder, 0, postorder.size() - 1);
}
//左右中
//根节点大于左子树任意节点，小于右子树任意节点
bool dfs(vector<int>& postorder, int left, int root) {
	if (left >= root)//只剩一个节点时候，之前已经满足了搜索二叉树的条件
		return true;//所以还是满足，返回true

	int rootValue = postorder[root];

	//区分左右区间，先找左右区间的区分节点位置
	int i = left;
	while (i < root && postorder[i] < rootValue)
		i++;
	//此时i已经是第一个右节点位置
	for (int j = i; j < root; j++)
		if (postorder[j] < rootValue)return false;

	//当前树没问题，检查左树和右树
	return dfs(postorder, left, i - 1) && dfs(postorder, i, root - 1);
}

34.二叉树中和为某一值的路径Sum = 一条路径的和

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

输入：
方法：

回溯法 + dfs

//找到所有路
vector<vector<int>>res;
vector<vector<int>> pathSum(TreeNode* root, int sum) {
	vector<int>temp;
	backtrack(root, sum, temp);
	return res;
}
void backtrack(TreeNode* root, int sum, vector<int>& arr) {
	//终止条件
	if (root == NULL)
		return;
	//做出选择
	arr.push_back(root->val);
	sum -= root->val;

	if (sum == 0 && root->left == NULL && root->right == NULL) {
		res.push_back(arr);
	}
	else {
		backtrack(root->left, sum, arr);
		backtrack(root->right, sum, arr);
	}
	//撤销选择
	arr.pop_back();
}

35.复杂链表的深拷贝

方法：

哈希表拷贝节点
原地节点的变化：
- 1.复制原指针A -> B -> C 变 A -> A’-> B -> B’-> C-> C’
- 2.改变random指针指向，上一步复制的节点包含了random节点
- 3.断开链表，同时复原

Node(int _val) {
	val = _val;
	next = NULL;
	random = NULL;
}
//深拷贝：复制对象 浅拷贝：复制对象的指针
Node* copyRandomList(Node* head) {
	if (head == NULL)return NULL;
	//原地复制链表,且仅将next指针连接起来，例如A->B->C变成A->A'->B->B'->C->C'
	Node* cur = head;
	while (cur) {
		Node* newNode = new Node(cur->val);
		newNode->next = cur->next;
		cur->next = newNode;
		cur = newNode->next;
	}
	cur = head;//cur指针复位
	//第二步复制random指针，A'、B'、C'指到对应的位置
	while (cur) {
		if (cur->random) cur->next->random = cur->random->next;
		cur = cur->next->next;
	}
	//第三步将链表断开，例如A->A'->B->B'->C->C'变为A'->B'->C',且注意这一步应当将原链表复原。
	Node* returnhead = head->next;//A',返回的节点

	Node* copycur = head->next;   //A'
	cur = head; //A
	while (cur) {
		cur->next = cur->next->next;
		cur = cur->next;
		if (copycur->next) {
			copycur->next = copycur->next->next;
			copycur = copycur->next;
		}
	}
	return returnhead;
}

36.二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。
要求不能创建任何新的节点，只能调整树中节点指针的指向。

为了让您更好地理解问题，以下面的二叉搜索树为例：

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

输入：
方法：

二叉搜索树——左中右形式存储——利用中序将节点截取下来
辅助指针逐渐将节点串联起来

Node* treeToDoublyList(Node* root) {
	if (root == NULL)
		return NULL;
	vector<Node*>arr;
	//左中右
	Inorder(root, arr);

	Node* head = arr[0];
	Node* pre = arr[0];
	for (int i = 1; i < arr.size(); i++) {
		Node* temp = arr[i];
		pre->right = temp;
		temp->left = pre;
		pre = temp;
	}
	pre->right = head;
	head->left = pre;

	return head;
}
void Inorder(Node* root, vector<Node*>& arr) {
	if (root->left)
		Inorder(root->left, arr);

	arr.push_back(root);

	if (root->right)
		Inorder(root->right, arr);
}

37.序列化二叉树 —— 重要

方法：

利用getline截取数值
前序、中序、后续、层序都是可以的。对应的反序列化即可。
这次使用前序遍历

//序列化,利用先序遍历——中左右
string serialize(TreeNode* root) {
	if (root == NULL)
		return "#,";
	string res = to_string(root->val) + ",";
	res += serialize(root->left);
	res += serialize(root->right);

	return res;
}

//反序列化
TreeNode* deserialize(string data) {
	//利用getline来截取string
	stringstream arr(data);
	string temp;

	queue<string>q;
	while (getline(arr, temp, ',')) {
		q.push(temp);
	}

	return helper(q);
}
TreeNode* helper(queue<string>&q) {
	string temp = q.front();
	q.pop();
	if (temp == "#")
		return NULL;

	TreeNode* node = new TreeNode(stoi(temp));
	node->left = helper(q);
	node->right = helper(q);
	return node;
}

//序列化,层序构建二叉树
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

string serialize(TreeNode* root) {
	string out;
	queue<TreeNode*> q;
	q.push(root);
    
	while (!q.empty()) {
		TreeNode* tmp = q.front();
		q.pop();
		if (tmp) {
			out += to_string(tmp->val) + " ";
			q.push(tmp->left);
			q.push(tmp->right);
		}
		else {
			out += "# ";
		}
	}
	return out;
}

TreeNode* deserialize(string data) {
	stringstream input(data);
	string val;
	vector<TreeNode*> vec;

	while (input >> val) {
		if (val == "#") {
			vec.push_back(NULL);
		}
		else {
			vec.push_back(new TreeNode(stoi(val)));
		}
	}

	int j = 1;                                          // i每往后移动一位，j移动两位，j始终是当前i的左子下标
	for (int i = 0; j < vec.size(); ++i) {              // 肯定是j先到达边界，所以这里判断j < vec.size()
		if (vec[i] == NULL) continue;                   // vec[i]为null时跳过。
		if (j < vec.size()) vec[i]->left = vec[j++];    // 当前j位置为i的左子树
		if (j < vec.size()) vec[i]->right = vec[j++];   // 当前j位置为i的右子树
	}
	return vec[0];
}

38.字符串的排列

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

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

输入：
输入：s = “abc”
输出：[“abc”,”acb”,”bac”,”bca”,”cab”,”cba”]
方法：

回溯法 + 剪枝叶

vector<string> res;
vector<string> permutation(string s) {

	unordered_map<char, int>vis;
	for (auto it : s)
		vis[it]++;

	backtrace(s, "", vis);
	return res;
}
void backtrace(string s, string tmp, unordered_map<char, int>&vis) {
	if (tmp.size() == s.size()) {
		res.push_back(tmp);
		return;
	}

	for (auto &it : vis) {
		if (it.second == 0)
			continue;

		it.second--;
		tmp += it.first;

		backtrace(s, tmp, vis);

		it.second++;
		tmp.pop_back();
	}
}

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

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

你可以假设数组是非空的，并且给定的数组总是存在多数元素。
输入：
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

方法：

哈希表
摩尔投票法
sorted，return中间元素

//摩尔投票法
int majorityElement(vector<int>& nums) {
	int res = 0;
	int count = 0;
	for (int i = 0; i < nums.size(); i++) {
		if (count == 0) {
			res = nums[i];
			count++;
		}
		else {
			if (nums[i] != res)
				count--;
			else
				count++;
		}
	}
	return res;
}

40. 最小的k个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
输入：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
输入：arr = [0,1,2,1], k = 1
输出：[0]
方法：

各种排序
快排
归并排序等

vector<int> getLeastNumbers(vector<int>& arr, int k) {
	vector<int>res(k, 0);
	sort(arr.begin(), arr.end());
	for (int i = 0; i != k; i++) {
		res[i] = arr[i];

	}
	return res;
}

41.数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
输入：
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
方法：

利用优先队列
大根堆保存小于中位数部分，小根堆保存大于中位数部分

//头文件 / #include <functional>
priority_queue<int, vector<int>, std::less<int>> maxStack;
priority_queue<int, vector<int>, std::greater<int>> minStack;
//小顶堆多放一个数字
//小顶堆存放大于中位数的数
//大顶堆存放小于中位数的数

void addNum(int num) {
	//小顶堆元素+1
	if (maxStack.size() == minStack.size()) {
		maxStack.push(num);
		num = maxStack.top();
		maxStack.pop();
		minStack.push(num);
	}//大顶堆元素+1
	else {
		minStack.push(num);
		num = minStack.top();
		minStack.pop();
		maxStack.push(num);
	}
}

double findMedian() {
	return maxStack.size() == minStack.size() ?
		(double)(minStack.top() + maxStack.top()) / 2 : minStack.top();
}

42.连续子数组的最大和

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

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

输入：
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
方法：

dp动态规划
贪心算法

int maxSubArray(vector<int>& nums) {
	//贪心算法
	// int res = nums[0];
	// int sum = 0;
	// for(auto it:nums){
	//     if(sum > 0)
	//         sum +=it;
	//     else{
	//         sum = it;
	//     }
	//     res = max(sum ,res);    
	// }
	//return res;
	//动态规划
	int res = nums[0];
	int len = nums.size();
	vector<int>dp(len + 1, 0);
	for (int i = 1; i <= len; i++) {
		dp[i] = max(dp[i - 1] + nums[i - 1], nums[i - 1]);
		res = max(dp[i], res);
	}
	return res;
}

43.1～n整数中1出现的次数

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

输入：
输入：n = 12
输出：5
输入：n = 13
输出：6
方法：

找规律
区分低位、高位、当前位、位因子

int countDigitOne(int n) {
	long digit = 1;
	int res = 0;
	int high = n / 10, cur = n % 10, low = 0; //1234 high_123 cur_4 low_0
	while (high != 0 || cur != 0) {
		// 高位 * 低位为1的个数
		// 然后通过对当前位进行判断，找真实的为1的个数
		if (cur == 0) res += high * digit;
		else if (cur == 1) res += high * digit + low + 1;
		else res += (high + 1) * digit;

		low += cur * digit;
		cur = high % 10;
		high /= 10;
		digit *= 10;
	}
	return res;
}

44. 数字序列中某一位的数字

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

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

输入：
输入：n = 3
输出：3
输入：n = 11
输出：0
方法：

找规律
范围 / 数量 / 位数 / 占位
1-9 / 9 / 1 / 9
10-99 / 90 / 2 / 180
100-999 / 900 / 3 / 2700
区分数量、位数、占多少位

方法：
n = 2901
2901 = 9 + 180 + 2700 + 12
数据：= 1000 + （12-1） / 4 = 1002
具体定位：（12 - 1） % 4 = 3；
1002[3] = 2

int findNthDigit(int n) {
	int digit = 1;   // n所在数字的位数
	long start = 1;  // 数字范围开始的第一个数
	long count = 9;  // 占多少位
	//找到所在位数的区间
	while (n > count) {
		n -= count;
		digit++;
		start *= 10;
		count = digit * start * 9;
	}

	long num = start + (n - 1) / digit; //数据
	string temp = to_string(num);   //具体定位(n - 1) % digit
	return temp[(n - 1) % digit] - '0';
}

45.把数组排成最小的数

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
输入：
输入: [10,2]
输出: “102”
输入: [3,30,34,5,9]
输出: “3033459”
方法：

利用sort排序
自定义compare比较函数

string minNumber(vector<int>& nums) {
	vector<string> strs;
	string res;
	for (auto num : nums)
		strs.push_back(to_string(num));

	sort(strs.begin(), strs.end(), compare);

	for (auto str : strs)
		res += str;
	return res;
}
static bool compare(const string &a, const string &b) {
	return a + b < b + a;
}

46.把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

输入：
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是”bccfi”, “bwfi”, “bczi”, “mcfi”和”mzi”
方法：

substr(i,len)/截取字符串
找规律
dp动态方程 dp[i] = dp[i - 1] / dp[i] = dp[i - 1] + p[i - 2];
‘10’ <= temp <= ‘25’:为什么是’10’，因为00：0、0，10：10和1、0.考虑拆分

int translateNum(int num) {
	string t = to_string(num);

	int n = t.size();
	vector<int> dp(n + 1, 0);
	dp[0] = 1;
	dp[1] = 1;
	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1];
		auto temp = t.substr(i - 2, 2);
		if (temp >= "10"  && temp <= "25") {
			dp[i] += dp[i - 2];
		}
	}
	return dp[n];
}

47.礼物的最大价值

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

输入：
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
方法：

初始化
dp动态方程

int maxValue(vector<vector<int>>& grid) {
	//dp[i][j]=max(dp[i-1][j],dp[i][j-1])
	int n = grid.size();
	int m = grid[0].size();
	vector<vector<int>>dp(n, vector<int>(m, 0));

	dp[0][0] = grid[0][0];
	for (int i = 1; i < n; i++) {
		dp[i][0] = dp[i - 1][0] + grid[i][0];
	}
	for (int i = 1; i < m; i++) {
		dp[0][i] = dp[0][i - 1] + grid[0][i];
	}
	for (int i = 1; i < n; i++) {
		for (int j = 1; j < m; j++) {
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
		}
	}
	return dp[n - 1][m - 1];
}