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
  • 贪心算法
    • 高射炮打蚊子了解一下

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
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;
}
};

基于时间的键值存储

题目

基于时间的键值存储

[基于时间的键值存储](https://leetcode-cn.com/contest/weekly-contest-121/problems/time-based-key-value-store/)

思路

使用mapunordered_map

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

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

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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{cases}dp_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) \
dp_i = 0 & i > \max(days)
\end{cases}
$$

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

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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官方没有设好时间,所以穷举也可以。。。

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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公式时出错了。。。。。