首页 > 今天小米笔试的两道编程题
头像
KK没有问题
编辑于 2020-09-15 22:18
+ 关注

今天小米笔试的两道编程题

感觉自己还是做题不够,临场的时候很难想到很好的办法。
结束之后和朋友讨论了一下,很快思路就变得清晰了,其实就是很简单的两道题。
第一题我用了两个循环,时间复杂度太高了;
第二题是个动态规划,当时没想到好的方法,后来抽象成了01背包问题就感觉很简单了。
新写的代码不知道是不是完全对的,仅供参考吧。

第一题:
题干很长,但是抽象一下其实就是,求每个数组元素后距离其最近的比他大的数与他的距离,有则输出距离,无则输出0;

我用了一个堆栈存,用结构体记录数据和他的编号,感觉还是算两个循坏吧,不知道是不是准确的解法,欢迎指正。
#include <iostream>
#include<stack>
#include<vector>
using namespace std;
struct pNum {
	int p;
	int num;
};
int main()
{
	stack<pNum> price;
	int n;
	cin >> n;
	vector<int> res;
	for (int i = 0; i < n; i++)
	{
		res.push_back(0);
	}
	for (int i = 0; i < n; i++)
	{
		int m;
		cin >> m;

		while (!price.empty())//循环直到栈为空或者遇到比当前输入大的数字。
		{
			if (m > price.top().p)
			{
				res[price.top().num] = i - price.top().num; //比栈顶的数字大则计算距离并出栈
				price.pop();			
			}
			else
			{
				break;
			}
		}
		pNum a;
		a.num = i;
		a.p = m;
		price.push(a);
	}
	for (int i = 0; i < n; i++)
	{
		cout << res[i] << endl;
		
	}
	return 0;
}


第二题:
题目大概意思是,有一堆绳子,把这堆绳子分成两份,求这两份绳子能组成的最大的长方形的面积。

这个题目一看就是动态规划了,但是刚开始真的没有什么好的思路,就只是想着,要想等周长面积最大,那肯定就是越接近正方形了,就是线能组成越接近周长一半。
后来同学说了一句感觉有点向简化的背包问题,然后豁然开朗想到一个肯定能解决的方法,但是感觉空间复杂度是很高的。
大概就是建立一个容量为总长一半的背包,然后找能装的最多的就好了。
但是就是由于空间用得太多了,就觉得这个方法可能还是错的。。。
#include <iostream>
#include <vector>
#include<algorithm>

using namespace std;

int main() {

	int n;
	cin >> n;
	vector<int> li;
	int al = 0;
	for (int i = 0; i < n; i++)
	{
		int l;
		cin >> l;
		al += l;
		li.push_back(l);
	}
	vector<vector<int>> dp;
	vector<int> d;
	int hal = al / 2;
	for (int j = 0; j < hal+1; j++)//就是这里,感觉空间用的太多了,感觉这里可能就过不了了
	{
		d.push_back(0);
	}
	for (int i = 0; i < n+1; i++)
	{
		
		dp.push_back(d);
	}
	for (int i = 1; i < n+1; i++)
	{
		for (int j = 1; j < hal+1; j++)
		{
			if (li[i - 1] > j)
			{
				dp[i][j] = dp[i - 1][j];
			}
			else
			{
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - li[i - 1]]+li[i-1]);
			}
	
		}

	}
	cout << (al - dp[n][hal])*dp[n][hal];
	return 0;

}




全部评论

(2) 回帖
加载中...
话题 回帖
历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐