C++Lambda递归的特殊实现
本文最后更新于 1067 天前,其中的信息可能已经有所发展或是发生改变。

先贴一段代码:

#include<iostream>
#include<vector>
#include<functional>
using namespace std;
int main()
{
	//input
	int N;
	cin >> N;
	vector<int> vec, tp;
	for (int i = 0; i < N; i++)
	{
		int temp;
		cin >> temp;
		vec.push_back(temp);
	}

	//handle
	vector<vector<int>> ans;

	function<void(int, vector<int>)> f1 = [&](int now, vector<int> v)
	{
		v.push_back(vec[now]);
		if (2 * now + 1 >= N)
			ans.push_back(v);
		else
		{
			if (2 * now + 2 < N)
				f1(2 * now + 2, v);
			if (2 * now + 1 < N)
				f1(2 * now + 1, v);
		}
	};

	f1(0, tp);

	//handle2
	bool minH = true, maxH = true;
	for (int i = 1; i < N; i++)
	{
		vec[i] > vec[(i - 1) / 2] ? maxH = false : minH = false;
	}

	//output
	for (auto i : ans)
	{
		for (auto& j : i)
		{
			cout << j;
			if (j != i.back())
				cout << " ";
		}
		cout << endl;
	}

	if (!maxH && !minH)
		cout << "Not Heap";
	else
		maxH ? cout << "Max Heap" : cout << "Min Heap";

	return 0;
}

题目是PAT-1155[链接],题目本身很简单,但最近想多试试Lambda,而Lambda递归常见的三种形式中,封装的有一定的代价,而Y组合子的C++实现形式搞不太懂,于是我写出了如上所示的代码,而这种写法我目前不曾经在任何文章中看到,先作记录。

试运行了一下柳婼大佬的代码,时间和空间花费大致接近,每个CASE各有高低,但毕竟每次运行的环境有所差异,所以仅供参考。至少这种写法不存在太大的开销问题。

上一篇
下一篇