LeetCode 2020 力扣杯全国春季编程大赛（1644/4093，前40.2%）

Michael阿明

发布于 2020-07-13 16:03:45

4390

发布于 2020-07-13 16:03:45

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

1. 比赛结果

前两题比较顺利，24分钟做出来了，第3，4两题试了好久，都显示超时，第5题没心思看，想着第3，4题应该能做出来的。

2. 题目解析

2.1 拿硬币 Easy

题目链接桌上有 n 堆力扣币，每堆的数量保存在数组 coins 中。我们每次可以选择任意一堆，拿走其中的一枚或者两枚，求拿完所有力扣币的最少次数。

示例 1：
输入：[4,2,1]
输出：4
解释：第一堆力扣币最少需要拿 2 次，
第二堆最少需要拿 1 次，
第三堆最少需要拿 1 次，
总共 4 次即可拿完。

示例 2：
输入：[2,3,10]
输出：8

限制：
1 <= n <= 4
1 <= coins[i] <= 10

解答：

除以2，向上取整即可

class Solution {
public:
    int minCount(vector<int>& coins) {
    	int i, sum = 0;
    	for(i = 0; i < coins.size(); ++i)
    		sum += ceil(coins[i]/2.0);
    	return sum;
    }
};

执行用时：4 ms 内存消耗：8.4 MB

2.2 传递信息 Esay

题目链接小朋友 A 在和 ta 的小伙伴们玩传信息游戏，游戏规则如下：

有 n 名玩家，所有玩家编号分别为 0 ～ n-1，其中小朋友 A 的编号为 0
每个玩家都有固定的若干个可传信息的其他玩家（也可能没有）。
传信息的关系是单向的（比如 A 可以向 B 传信息，但 B 不能向 A 传信息）。
每轮信息必须需要传递给另一个人，且信息可重复经过同一个人

给定总玩家数 n，以及按 [玩家编号,对应可传递玩家编号] 关系组成的二维数组 relation。返回信息从小 A (编号 0 ) 经过 k 轮传递到编号为 n-1 的小伙伴处的方案数；若不能到达，返回 0。

示例 1：
输入：n = 5, relation = [[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]], k = 3
输出：3
解释：信息从小 A 编号 0 处开始，经 3 轮传递，到达编号 4。
共有 3 种方案，分别是 0->2->0->4， 0->2->1->4， 0->2->3->4。

示例 2：
输入：n = 3, relation = [[0,2],[2,1]], k = 2
输出：0
解释：信息不能从小 A 处经过 2 轮传递到编号 2

限制：
2 <= n <= 10
1 <= k <= 5
1 <= relation.length <= 90, 且 relation[i].length == 2
0 <= relation[i][0],relation[i][1] < n 
且 relation[i][0] != relation[i][1]

解答：

把路径的边插入set，方便后面快速查找
dp[i][j] 表示第i次传递到j的方案数

class Solution {
public:
    int numWays(int n, vector<vector<int>>& relation, int k) {
    	set<vector<int>> s;
    	for(auto re : relation)
			s.insert(re);

		vector<vector<int>> dp(k+1,vector<int>(n,0));
		dp[0][0] = 1;//初始状态
		for(int i = 1; i <= k; ++i)//k次传递
		{
			for(int j = 0; j < n; ++j)
			{	//n个人，如果存在传递到这的情况
				if(dp[i-1][j]!=0)
				{
					for(int k = 0; k < n; ++k)
					{	//传给下一个人，可以传给跟自己有关系的
						if(s.count({j,k}))//有关系
							dp[i][k] += dp[i-1][j];
					}
				}
			}
		}
		return dp[k][n-1];
	}	
};

执行用时：8 ms 内存消耗：7.6 MB

class Solution {	//更简洁的版本
public:
    int numWays(int n, vector<vector<int>>& relation, int k) {
        int dp[6][10]= {0};
        dp[0][0]=1;
        for(int i=0;i<k;i++)
            for(auto ss:relation)
                dp[i+1][ss[1]] += dp[i][ss[0]];
        return dp[k][n-1];
    }
    //参看作者：xunh
};

2.3 剧情触发时间 Medium

题目链接在战略游戏中，玩家往往需要发展自己的势力来触发各种新的剧情。一个势力的主要属性有三种，分别是文明等级（C），资源储备（R）以及人口数量（H）。在游戏开始时（第 0 天），三种属性的值均为 0。

随着游戏进程的进行，每一天玩家的三种属性都会对应增加，我们用一个二维数组 increase 来表示每天的增加情况。这个二维数组的每个元素是一个长度为 3 的一维数组，例如 [[1,2,1],[3,4,2]] 表示第一天三种属性分别增加 1,2,1 而第二天分别增加 3,4,2。

所有剧情的触发条件也用一个二维数组 requirements 表示。这个二维数组的每个元素是一个长度为 3 的一维数组，对于某个剧情的触发条件 c[i], r[i], h[i]，如果当前 C >= c[i] 且 R >= r[i] 且 H >= h[i] ，则剧情会被触发。

根据所给信息，请计算每个剧情的触发时间，并以一个数组返回。如果某个剧情不会被触发，则该剧情对应的触发时间为 -1 。

示例 1：
输入： increase = [[2,8,4],[2,5,0],[10,9,8]] 
requirements = [[2,11,3],[15,10,7],[9,17,12],[8,1,14]]
输出: [2,-1,3,-1]
解释：
初始时，C = 0，R = 0，H = 0
第 1 天，C = 2，R = 8，H = 4
第 2 天，C = 4，R = 13，H = 4，此时触发剧情 0
第 3 天，C = 14，R = 22，H = 12，此时触发剧情 2
剧情 1 和 3 无法触发。

示例 2：
输入： increase = [[0,4,5],[4,8,8],[8,6,1],[10,10,0]] 
requirements = [[12,11,16],[20,2,6],[9,2,6],[10,18,3],[8,14,9]]
输出: [-1,4,3,3,3]

示例 3：
输入： increase = [[1,1,1]] requirements = [[0,0,0]]
输出: [0]

限制：
1 <= increase.length <= 10000
1 <= requirements.length <= 100000
0 <= increase[i] <= 10
0 <= requirements[i] <= 100000

我的比赛错误解：（1、有重复元素没考虑，2、erase 迭代器后，迭代器失效！！）

struct cmp1
{
	bool operator()(const vector<int>& a, const vector<int>& b)const
	{
		if(a[0]==b[0])
		{
			if(a[1]==b[1])
				return a[2] < b[2];
			return a[1] < b[1];
		}
		return a[0] < b[0];
	}
};

class Solution {
public:
    vector<int> getTriggerTime(vector<vector<int>>& inc, vector<vector<int>>& req) {
    	int t = 0, n = req.size(), a = 0, b = 0, c =0;
    	vector<int> ans(n,-1);
    	map<vector<int>, int> m;
    	set<vector<int>,cmp1> set1;
    	for(int i = 0; i < n; ++i)
    	{
    		m[req[i]]=i;
    		set1.insert(req[i]);
    	}

    	vector<int> tp;
    	auto end1 = set1.upper_bound({a,b,c});
		for(auto it = set1.begin(); it != end1; ++it)
		{
			tp = *it;
			if(a>=tp[0] && b>=tp[1] && c>=tp[2])
			{
    			ans[m[tp]] = t;
    			set1.erase(tp);
    		}
		}
    	for(int i = 0; i < inc.size(); ++i)
    	{
    		t = i+1;
    		a += inc[i][0];
    		b += inc[i][1];
    		c += inc[i][2];
    		auto end = set1.upper_bound({a,b,c});
    		for(auto it = set1.begin(); it != end; ++it)
    		{
    			tp = *it;
    			if(a>=tp[0] && b>=tp[1] && c>=tp[2])
    			{
	    			ans[m[tp]] = t;
	    			set1.erase(tp);
	    		}
    		}
    	}
    	return ans;
    }
};

我的赛后正确解：m.erase(it++);//这样做迭代器不会失效
利用multimap（平衡搜索树）有序，可以进行二分查找

struct cmp1	//自定义排序规则
{
	bool operator()(const vector<int>& a, const vector<int>& b)const
	{
		if(a[0]==b[0])
		{
			if(a[1]==b[1])
				return a[2] < b[2];
			return a[1] < b[1];
		}
		return a[0] < b[0];
	}
};

class Solution {
public:
    vector<int> getTriggerTime(vector<vector<int>>& inc, vector<vector<int>>& req) {
    	int t = 0, n = req.size(), a = 0, b = 0, c =0;
    	vector<int> ans(n,-1);
    	multimap<vector<int>, int, cmp1> m;
    	for(int i = 0; i < n; ++i)
    		m.insert(make_pair(req[i],i));

    	vector<int> tp;
    	for(int i = -1; i < int(inc.size()); ++i)//注意坑，int -1 跟 size_t 比较，循环进不去
    	{
    		t = i+1;
            if(i >=0)
    		{
                a += inc[i][0];
    		    b += inc[i][1];
    		    c += inc[i][2];
            }
    		auto end = m.upper_bound({a,b,c});
    		for(auto it = m.begin(); it != end; )
    		{
    			tp = it->first;
                if(a>=tp[0] && b>=tp[1] && c>=tp[2])
                {
                    ans[it->second] = t;
                    m.erase(it++);//这样做迭代器不会失效
                }
                else
                    it++;
    		}
    	}
    	return ans;
    }
};

2.4 最小跳跃次数 Hard

题目链接

为了给刷题的同学一些奖励，力扣团队引入了一个弹簧游戏机。游戏机由 N 个特殊弹簧排成一排，编号为 0 到 N-1。初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹簧处，通过按动弹簧，可以选择把小球向右弹射 jump[i] 的距离，或者向左弹射到任意左侧弹簧的位置。也就是说，在编号为 i 弹簧处按动弹簧，小球可以弹向 0 到 i-1 中任意弹簧或者 i+jump[i] 的弹簧（若 i+jump[i]>=N ，则表示小球弹出了机器）。小球位于编号 0 处的弹簧时不能再向左弹。

为了获得奖励，你需要将小球弹出机器。请求出最少需要按动多少次弹簧，可以将小球从编号 0 弹簧弹出整个机器，即向右越过编号 N-1 的弹簧。

示例 1：
输入：jump = [2, 5, 1, 1, 1, 1]
输出：3
解释：小 Z 最少需要按动 3 次弹簧，
小球依次到达的顺序为 0 -> 2 -> 1 -> 6，最终小球弹出了机器。

限制：
1 <= jump.length <= 10^6
1 <= jump[i] <= 10000

我的BFS超时解：超时的例子

class Solution {
public:
    int minJump(vector<int>& jump) {
    	int i, j, n = jump.size(), t = 0, size,tp;
    	set<int> set;
    	for(i = 0; i < n; ++i)
    		set.insert(i);
    	queue<int> q;
    	q.push(0);
    	set.erase(0);
    	while(!q.empty())
    	{
    		size = q.size();
    		t++;
    		while(size--)
    		{
    			tp = q.front();
    			q.pop();
    			if(tp+jump[tp] >= n)
    				return t;
    			if(set.count(tp+jump[tp]))
    			{
    				q.push(tp+jump[tp]);
    				set.erase(tp+jump[tp]);
    			}
    			auto end = set.upper_bound(tp);//这个地方多了lgn的查找，用数组降到O(1)
    			for(auto it = set.begin(); it != end; ++it)
    			{
    				q.push(*it);
    				set.erase(*it);
    			}
    		}
    	}
    	return t;
    }
};

改进的BFS

class Solution {
public:
    int minJump(vector<int>& jump) {
    	int i, n = jump.size(), t = 0, size, tp, prevPos = 0;
    	vector<bool> vis(n,false);
    	vis[0] = true;
    	queue<int> q;
    	q.push(0);
    	while(!q.empty())
    	{
    		size = q.size();
    		t++;
    		while(size--)
    		{
    			tp = q.front();
    			q.pop();
    			if(tp+jump[tp] >= n)
    				return t;
                if(!vis[tp+jump[tp]])
    			{   //向右跳过来
    				q.push(tp+jump[tp]);
    				vis[tp+jump[tp]] = true;
    			}
    			for(i = prevPos+1; tp >0 && i < tp; ++i)
    			{   //向左位置跳
                    if(!vis[i])
    				{
                        q.push(i);
    				    vis[i] = true;
                    }
    			}
                prevPos = max(prevPos,tp);//没有这句会超时
                //避免重复检查某些位置
    		}
    	}
    	return t;
    }
};