leetcode——第 230 场周赛

题目地址

统计匹配检索规则的物品数量

leetcode——第 230 场周赛
水题,模拟即可。

 class Solution {
 private:
	 bool check(vector<string>& s, string ruleKey, string ruleValue)
	 {
		 if (ruleKey == "type")
		 {
			 return s[0] == ruleValue;
		 }
		 else if (ruleKey == "color")
		 {
			 return s[1] == ruleValue;
		 }
		 return s[2] == ruleValue;
	 }
 public:
	 int countMatches(vector<vector<string>>& items, string ruleKey, string ruleValue) {
		 int res = 0;
		 for (int i = 0; i < items.size(); i++)
		 {
			 if (check(items[i], ruleKey, ruleValue))
				 res++;
		 }
		 return res;
	 }
 };

最接近目标价格的甜点成本

leetcode——第 230 场周赛
简单来说,你必须选一个冰激凌基料,配料可以有多种,每种配料可以加的数量为0,1,2。数据范围均为10,这就提示我们用递归。

更新数据时,如果与目标差值相等,选小的。否则选差值小的那个数。

 class Solution {
 private:
	 int res = 0;
	 int update(int res, int k, int target)
	 {
		 if (res == 0) return k;
		 if (abs(target - res) == abs(target - k))
			 return res > k ? k : res;
		 return abs(target - res) > abs(target - k) ? k : res;
	 }
	 void dfs(int sum, int index, vector<int>& t,int target)
	 {
		 res = update(res, sum, target);
         if (index == t.size())return;
		 for (int i = 0; i < 3; i++)
		 {
			 dfs(sum + i * t[index], index + 1, t, target);
		 }
	 }
 public:
	 int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
		 for (int i = 0; i < baseCosts.size(); i++)
		 {
			 dfs(baseCosts[i], 0, toppingCosts, target);
		 }
		 return this->res;
	 }
 };

通过最少操作次数使数组的和相等

leetcode——第 230 场周赛
两个有序数组,a,b,从小到大排序。假设a的和较小。

双指针分别从 数组 a 左侧(较小侧) 和 数组 b 右侧(较大侧)开始移动;

为了让两数组和相等,每次操作可以使较大数变小(最小变为 1),或较小数变大(最大变为 6),贪心的选择变化差值最大的一边修改。如果有一个数组已无法修改,此时只能修改另一个数组。

修改终止条件,suma>=sumb。

当出现suma>=sumb时,一定可以修改到正好两者之和相等。

 class Solution {
 public:
	 int minOperations(vector<int>& nums1, vector<int>& nums2) {
		 int suma = 0, sumb = 0;
		 sort(nums1.begin(), nums1.end());
		 sort(nums2.begin(), nums2.end());
		 for (auto& t : nums1)suma += t;
		 for (auto& t : nums2)sumb += t;
		 if (suma > sumb)
		 {
			 swap(suma, sumb);
			 swap(nums1, nums2);
		 }
		 //左边小,右边大
		 int res = 0;
		 int size1 = nums1.size(), size2 = nums2.size();
		 int i = 0, j = size2-1;
		 while (i < size1 && j >= 0 && suma < sumb)
		 {
			 if (6 - nums1[i] > nums2[j] - 1)//选择变化差值大的地方
				 suma += 6 - nums1[i++];
			 else
				 sumb -= nums2[j--] - 1;
			 res++;
		 }
		 //已经有一个地方变化完毕
		 while (i<size1 && suma>sumb)
		 {
			 suma += 6 - nums1[i++];
			 res++;
		 }
		 while (j >= 0 && suma < sumb)
		 {
			 sumb -= nums2[j--] - 1;
			 res++;
		 }
		 return suma >= sumb ? res : -1;
	 }
 };

车队 II

leetcode——第 230 场周赛

最右侧的车的答案一定是 −1。每个车都需要追最右边的车,设i辆车为Ci位置为Pi,速度为Si。

对于右边的车来说,如果

Si<=Si+1,则不会追到。反之,则追到的时间为 (Pi+1-P)/(Si-Si+1)。

但是实际情况更复杂一点。如果在当前车Ci 追到Ci+1时,Ci+1追到了Ci+2,那么就要用Ci+2的时间来计算。

所以我们要用栈的思路来作:

如果当前车Ci 追到Ci+1时,Ci+1追到了Ci+2,那么Ci+1可以删除,继续判断仍然执行上一步判断;如果仍可去除,则去除。

如果经过(0次或多次)去除之后,栈为空,则表明当前车不会追上任何车,答案是 −1。

如果经过去除之后,栈不为空,则表明当前车会追上当前栈顶的车Ctop。

 class Solution {
 private:
	 double get_time(vector<int>& front, vector<int>& back)
	 //计算时间
	 {
		 return (double)(front[0] - back[0]) / (back[1] - front[1]);
	 }
 public:
	 vector<double> getCollisionTimes(vector<vector<int>>& cars) {
		 int size = cars.size();
		 vector<double>res(size);
		 res[size - 1] = -1;
		 stack<int> s;
		 s.push(size - 1);
		 for (int i = size - 2; i >= 0; i--)
		 {
			 while (s.size())
			 {
			 //追不上的条件,要么速度没超过,要么再追到时他已经和前面的车合并
				 if (cars[i][1] <=cars[s.top()][1] ||
					 (res[s.top()] >= 1e-5 && get_time(cars[s.top()], cars[i])>res[s.top()]))
					 s.pop();
				 else//追得上,退出,此时栈顶为追到的车
					 break;
			 }
			 if (s.size())
				 res[i] = get_time(cars[s.top()], cars[i]);
			 else
				 res[i] = -1;
			 s.push(i);
		 }
		 return res;
	 }
 };
上一篇:[可能有用科技]最小直径生成树


下一篇:[leetCode]888. 公平的糖果棒交换