leetcode contest 121 writeup

概要

第121周的leetcode周赛共有4题

leetcode第121周周赛

题目	难度	知识点
不含AAA或BBB的字符串	简单	没有/贪心
基于时间的键值存储	中等	数据结构
最低票价	中等	动态规划
按位与为零的三元组	困难	数学

不含AAA或BBB的字符串

题目

题目

思路

有两种思路

• 普通思路
  1. 因为必然存在解
  2. 所以用数量少的字母隔开多的字母，使多的一方尽量均匀分配。
     • 例如：A = m B = n (m > n)
     • ((m / (n + 1)) * A B)*n (m / (n + 1)) * A
  3. 因为整数除法可能出现小数，就将小数聚拢
     1. 例如 A = 5 B = 3
     2. 5 / 4 = 1.25
     3. 所以把 5 分成 1 个 2 、三个 1
• 贪心算法
  • 高射炮打蚊子了解一下

代码

class Solution {
public:
	string strWithout3a3b(int A, int B) 
	{
		if (A == B)	
		{
			string result;
			while (A--)
			{
				result.append("ab");
			}
			return result;
		}
		int max, min;
		char max_c = 'a';
		char min_c = 'b';
		string result;
		if (A > B)
		{
			max = A;
			min = B;
		}
		else
		{
			max = B;
			min = A;
			max_c = 'b';
			min_c = 'a';
		}
		int num_divide_part = min + 1;
		int num_1 = num_divide_part * 2 - max;
		int num_2 = num_divide_part - num_1;
		while (num_1--)
		{
			result.push_back(max_c);
			result.push_back(min_c);
		}
		if (num_2 == 0)
			result.pop_back();
		else {
			while (num_2--)
			{
				result.push_back(max_c); result.push_back(max_c);
				result.push_back(min_c);
			}
			result.pop_back();
		}
		return result;
	}
};

基于时间的键值存储

题目

基于时间的键值存储

思路

使用map和unordered_map

1. 用map映射key到<time,stamp>
2. 用unordered_map映射time到stamp

前面用map的理由是保证常数级的查询时间

后面用unordered_map是为了尽快查出那个最大的time，如果使用map可能需要n级的时间。

代码

class TimeMap {
public:
	/** Initialize your data structure here. */
	TimeMap() {
	}
	unordered_map<string, map<int, string>> my_map;
	void set(string key, string value, int timestamp) {
		if (my_map.find(key) != my_map.end())
		{
			my_map[key][timestamp] = value;
		}
		else
		{
			my_map[key] = map<int, string>();
			my_map[key][timestamp] = value;
		}
	}

	string get(string key, int timestamp) {
		if (my_map.find(key) == my_map.end())
		{
			return "";
		}
		else
		{
			auto &find_map = my_map[key];
			for (auto it = --find_map.end(); it != find_map.begin(); it--)
			{
				if ((*it).first <= timestamp)
				{
					return (*it).second;
				}
			}
			if ((*find_map.begin()).first <= timestamp)
			{
				return (*find_map.begin()).second;
			}
			else
			{
				return "";
			}
		}
	}
};

最低票价

题目

最低票价

思路

因为求得是最优化问题，而且可以分成若干个阶段，因此我们很容易想到dp。因为最低票价显然是个一元谓词，我们就设dp(n)是第n天的最低票价。

先列出状态转移方程

$$
\begin

dp_i = 0 & i > \max(days)
\enddp_i = \min(dp_{i+1}+costs_0,dp_{i+7}+costs_1,dp_{i+2}+costs_{30}) & i\in days \dp_i = dp_{i+1}&i \notin days \and i < \max(days) \
$$

然后注意下记忆优化，避免重复的迭代展开。搞个哈希表就行(unordered_map)。

不优化的话复杂度就变成O(3 ^ n)

代码

class Solution {
public:
	unordered_map<int, int> dp_pre = unordered_map<int, int>();
	set<int> days_traval = set<int>();
	int max_days;
	int dp(int day, vector<int>& costs)
	{
		int result;
		if (dp_pre.find(day) != dp_pre.end())
			return dp_pre[day];
		if (day > max_days)
		{
			dp_pre[day] = 0;
			return 0;
		}
			
		if (days_traval.find(day) == days_traval.end())
		{
			result = dp(day + 1, costs);
			dp_pre[day] = result;
			return result;
		}
		auto && dp_datas = {dp(day+1,costs)+costs[0],dp(day + 7,costs) + costs[1],dp(day + 30,costs) + costs[2]};
		result =*min_element(dp_datas.begin(), dp_datas.end());
		dp_pre[day] = result;
		return result;

		
	}
	int mincostTickets(vector<int>& days, vector<int>& costs) 
	{
		for (auto day : days)
		{
			days_traval.insert(day);
		}
		max_days = *max_element(days.begin(),days.end());
		return dp(1,costs);
	}
};

按位与为零的三元组

题目

按位与为零的三元组

思路

这个其实是一个数论题。。。

如果硬要做还挺麻烦的，但是似乎leetcode官方没有设好时间，所以穷举也可以。。。

更好的方法就看官方的吧。

代码

class Solution {
public:
	int countTriplets(vector<int> A) {
		int sum = 0;
		for (int i = 0; i < A.size(); i++)
		{
			for (int j = 0; j < A.size(); j++)
			{
				for (int k = 0; k < A.size(); k++)
					if ((A[i] & A[j] & A[k]) == 0)
					{
						sum++;
					}
			}
		}
		return sum;
	}
};

后记

这次因为第一题看错题了，第三题摸鱼，导致没特别做好，就当长知识了吧-_-

垃圾hexo，加载latex公式时出错了。。。。。