剑指 Offer 45. 把数组排成最小的数 剑指 Offer 61. 扑克牌中的顺子 剑指 Offer 40. 最小的k个数

• 前言
• 一、示例
• • 1.剑指 Offer 45. 把数组排成最小的数
  • 2.剑指 Offer 61. 扑克牌中的顺子
  • 3.剑指 Offer 40. 最小的k个数
• 二、代码解析
• • 1.新建.cpp文件
  • • 代码如下（示例）：
• 三，测试

剑指 Offer 45. 把数组排成最小的数
剑指 Offer 61. 扑克牌中的顺子
剑指 Offer 40. 最小的k个数

#include
#include
#include
#include
#include 
using namespace std;



string minNumber(vector& nums)
{
	int len = nums.size();
	string res = "";
	if (len == 0)return res;
	vector tmpStr;
	for (int i = 0; i < len; ++i)
	{
		tmpStr.push_back(to_string(nums[i]));
	}
	sort(tmpStr.begin(), tmpStr.end(), [](string& x, string& y) {return x + y < y + x; });
	for (int i = 0; i < len; ++i)
	{
		res.append(tmpStr[i]);
	}

	return res;
}

bool isStraight1(vector& nums)
{
	sort(nums.begin(), nums.end());

	int k = 0;
	for (int i = 0; i < nums.size() - 1; ++i)
	{
		if (nums[i] == 0)
		{
			++k;
			continue;
		}
		if (nums[i] == nums[i + 1])
		{
			return false;
		}
		if (nums[i] + 1 == nums[i + 1])
		{
			continue;
		}
		if (nums[i] + 1 < nums[i + 1])
		{
			k -= nums[i + 1] - nums[i] - 1;
			if (k < 0)
			{
				return false;
			}
		}
	}
	return true;
}


vector getLeastNumbers1(vector& arr, int k)
{
	vector nums;
	sort(arr.begin(), arr.end());
	for (int i = 0; i < k; ++i)
	{
		nums.push_back(arr[i]);
	}
	return nums;
}

vector getLeastNumbers2(vector& arr, int k)
{
	vector res(k, 0);
	if (k == 0) return res;
	priority_queue, less> Q;
	for (int i = 0; i < k; ++i)
	{
		Q.push(arr[i]);
	}

	for (int i = k; i < arr.size(); ++i)
	{
		if (Q.top() > arr[i])
		{
			Q.pop();
			Q.push(arr[i]);
		}
	}

	for (int i = 0; i < k; ++i)
	{
		res[i] = Q.top();
		Q.pop();
	}

	return res;
}


int main(void)
{
	cout << "剑指 Offer 45. 把数组排成最小的数" << endl;
	vector nums = { 1,2,3,4,5 };
	cout << "法一----->" << minNumber(nums) << endl << endl;

	cout << "剑指 Offer 61. 扑克牌中的顺子" << endl;
	cout << "法一----->" << isStraight1(nums) << endl << endl;

	cout << "剑指 Offer 40. 最小的k个数" << endl;
	vector arr = { 1,2,3,4,5,1,3,6,9 };
	vector res1 = getLeastNumbers1(arr, 2);
	vector res2 = getLeastNumbers2(arr, 2);

	cout << "法一--数组排序--->" << endl;
	for (int i = 0; i < res1.size(); ++i)
	{
		cout << res1[i] << " ";
	}
	cout << endl;
	cout << "法二--堆降序--->" << endl;
	for (int i = 0; i < res2.size(); ++i)
	{
		cout << res2[i] << " ";
	}
	return 0;
}