剑指offer，见过的最靠谱的分析，c++（21~30）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了剑指offer，见过的最靠谱的分析，c++（21~30），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5339字，纯文字阅读大概需要8分钟。

内容图文

21、顺时针打印矩形
https://blog.csdn.net/malele4th/article/details/79321607

class Solution {
public:
	vector<int> printMatrix(vector<vector<int> > matrix) {
		vector<int>out;
		out.clear();
		int row = matrix.size();
		int col = matrix[0].size();
		int circle = ((row < col ? row : col) - 1) / 2 + 1;
		for (int i = 0; i < circle; i++)
		{
			for (int j = i; j < col  - i; j++) out.push_back(matrix[i][j]);
			for (int k = i + 1; k < row - i; k++) out.push_back(matrix[k][col - 1-i]);
			for (int m = col - 2 - i; (m >= i) && (row - 1 - i != i); m--) out.push_back(matrix[row -1- i][m]);
			for (int n = row - 2 - i; (n > i) && (col - 1 - i != i); n--) out.push_back(matrix[n][i]);
		}
		return out;
	}
};

22、包含min函数的栈
https://blog.csdn.net/malele4th/article/details/79322056

class Solution {
public:
	stack<int>datastack, minstack;
	void push(int value) {
		datastack.push(value);
		int min = minstack.top();
		if (minstack.empty()) minstack.push(value);
		else if(value>=min) minstack.push(min);
		else minstack.push(value);
	}
	void pop() {
		datastack.pop();
		minstack.pop();
	}
	int top() {
		return datastack.top();
	}
	int min() {
		return minstack.top();
	}
};

23、从上往下打印二叉树
https://blog.csdn.net/malele4th/article/details/79322859

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

using namespace std;

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

class Solution {
public:
	vector<int> PrintFromTopToBottom(TreeNode* root) {
		vector<int>vec;
		if (root == nullptr) return vec;
		queue<TreeNode*>tree;
		tree.push(root);
		while (!tree.empty())
		{
			TreeNode* temp = tree.front();
			vec.push_back(temp->val);
			tree.pop();
			if (temp->left) tree.push(temp->left);
			if (temp->right) tree.push(temp->right);
		}
		return vec;
	}
};

24、二叉搜索树的后序遍历序列
https://blog.csdn.net/malele4th/article/details/79323648
（作者的例子应该有误）

class Solution {
public:
	bool VerifySquenceOfBST(vector<int> sequence) {
		if (sequence.size() == 0)return false;
		return judge(sequence, 0, sequence.size() - 1);
	}

private:
	bool judge(vector<int>& array,int left,int right)
	{
		if (left >= right) return true;
		int mid = right;
		while (mid > left && array[mid-1] > array[right]) mid--;
		for (int j = mid - 1; j >= left; j--)
			if (array[j] > array[right]) 
				return false;
		return judge(array, left, mid) && judge(array, mid+1, right-1);//import
	}
};

25、二叉树中和为某一值的路径
https://blog.csdn.net/malele4th/article/details/79323661

class Solution {
public:
	vector<vector<int> > FindPath(TreeNode* root, int expectNumber) {
		vector<vector<int>> ret;
		vector<int>trace;
		if(root) DFS(root, expectNumber, ret, trace);
		return ret;
	}
private:
	void DFS(TreeNode* root, int num, vector<vector<int>> &ret, vector<int> &trace)
	{
		trace.push_back(root->val);
		if (!root->left && !root->right)
			if (root->val == num) ret.push_back(trace);
		if (root->left)
			DFS(root->left, num - root->val, ret, trace);
		if (root->right)
			DFS(root->right, num - root->val, ret, trace);
		trace.pop_back();//路没走通，所以得回退
	}
};

26、复杂链表的复制
https://blog.csdn.net/malele4th/article/details/79325200

class Solution {
public:
	RandomListNode* Clone(RandomListNode* pHead)
	{
		CloneNodes(pHead);
		ConnectRandomNodes(pHead);
		return ReConnectNodes(pHead);
	}
private:
	void CloneNodes(RandomListNode *pHead)
	{
		RandomListNode* node = pHead;
		while (node!=nullptr)
		{
			RandomListNode* clone = new RandomListNode(0);
			clone->label = node->label;
			clone->next = node->next;
			clone->random = NULL;
			node->next = clone;
			node = clone->next;
		}
	}
	void ConnectRandomNodes(RandomListNode* pHead)
	{
		while (!pHead)
		{
			RandomListNode* pNode = pHead;
			while (pNode != NULL)
			{
				RandomListNode* pCloned = pNode->next;
				if (pNode->random != NULL)
					pCloned->random = pNode->random->next;
				pNode = pCloned->next;
			}
		}
	}
	RandomListNode* ReConnectNodes(RandomListNode* pHead)
	{
		RandomListNode* node = pHead;
		RandomListNode* head = nullptr;
		RandomListNode* clone = nullptr;
		if (pHead != NULL)
		{
			head = clone = node->next;
			node->next = clone->next;
			node = clone->next;
		}
		while (node != nullptr)
		{
			clone->next = node->next;
			clone = clone->next;
			node->next = clone->next;
			node = node->next;
		}
		return head;
	}
};

27、二叉搜索树和双向链表
https://blog.csdn.net/malele4th/article/details/79325332

class Solution {
public:
	TreeNode* Convert(TreeNode* pRootOfTree)
	{
		if (pRootOfTree == nullptr) return nullptr;
		TreeNode* res = pRootOfTree;
		TreeNode* pre = nullptr;
		change(res, pre);
		while (res->left)
			res = res->left;
		return res;
	}
private:
	void change(TreeNode* res, TreeNode*& pre)//注意函数参数的引入格式
	{
		if (res == nullptr) return;
		change(res->left, pre);
		res->left = pre;
		if (pre) pre->right = res;
		pre = res;
		change(res->right, pre);

	}
};

28、字符串的排列
https://blog.csdn.net/qq_27022241/article/details/80999255

#include<queue>
#include<vector>
#include<string>

using namespace std;

class Solution {
public:
	vector<string> Permutation(string str) {
		vector<string> a;
		if (str.empty()) return a;
		per(a, str, 0);
		return a;
	}

private:
	void per(vector<string>& array, string str, int begin)
	{
		if (begin == str.size() - 1) 
			array.push_back(str);
		for (int i = begin; i < str.size(); i++)
		{
			if (i != begin && str[i] == str[begin])
				continue;
			swap(str[i], str[begin]);
			per(array, str, begin + 1);
		}
	}
};

29、数组中出现次数超过一半的数字
https://blog.csdn.net/malele4th/article/details/79325882
不知道最优解法的解释是什么，没有论证显得很突兀。

30、最小的K个数
https://blog.csdn.net/malele4th/article/details/79325899 快排
https://blog.csdn.net/weixin_38111819/article/details/79935060 构建最大堆

内容总结

以上是互联网集市为您收集整理的剑指offer，见过的最靠谱的分析，c++（21~30）全部内容，希望文章能够帮你解决剑指offer，见过的最靠谱的分析，c++（21~30）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端