好久没有写解题报告了，今天做了一下比赛，这场比赛的题目比较简单。一二题代码很短，题意明白会很快写完，第三题看着很难，但是测试数据简单，直接暴力就可以过。
第四题也是一道简单的动态规划题，只是模拟规则比较复杂。
下面是详细的题解和思考。
比赛的地址 Weekly Contest 157
https://leetcode-cn.com/contest/weekly-contest-157
1. 玩筹码
题目：
玩筹码(Play with Chips)
地址：
https://leetcode-cn.com/contest/weekly-contest-157/problems/play-with-chips/
题意：
数轴上放置了一些筹码，每个筹码的位置存在数组 chips 当中。
你可以对 任何筹码 执行下面两种操作之一（不限操作次数，0 次也可以）：
将第 i 个筹码向左或者右移动 2 个单位，代价为 0。
将第 i 个筹码向左或者右移动 1 个单位，代价为 1。
最开始的时候，同一位置上也可能放着两个或者更多的筹码。
返回将所有筹码移动到同一位置（任意位置）上所需要的最小代价。
示例 1：
输入：chips = [1,2,3]
输出：1
解释：第二个筹码移动到位置三的代价是 1，第一个筹码移动到位置三的代价是 0，总代价为 1。
思路：
所有奇数位的筹码，经过多次移动两格都能移动到坐标1位置，所有偶数位筹码都能移动到坐标0位置。
最后合成一堆的时候，最小代价就是坐标0或1筹码的总数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int minCostToMoveChips(vector<int>& chips) {
int a = 0;
int b = 0;
for(auto n : chips)
{
if(n%2==0)
a++;
else
b++;
}
return min(a, b);
}
};
|
2. 最长定差子序列
题目：
最长定差子序列(Longest Arithmetic Subsequence of Given Difference)
地址：
https://leetcode-cn.com/contest/weekly-contest-157/problems/longest-arithmetic-subsequence-of-given-difference/
题意：
给你一个整数数组 arr 和一个整数 difference，请你找出 arr 中所有相邻元素之间的差等于给定 difference 的等差子序列，并返回其中最长的等差子序列的长度。
示例 1：
输入：arr = [1,2,3,4], difference = 1
输出：4
解释：最长的等差子序列是 [1,2,3,4]。
思路：
只需要三个元素：等差差值，数列长度，等差数列最后一个数的大小，就可以表示一个等差数列。
对于整数数组arr遍历，对于每个arr[i]，设arr[i]-diff表示的等差数列长度为m，则arr[i]表示的等差数列大小为m+1。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
int longestSubsequence(vector<int>& arr, int diff) {
map<int, int> mp;
int ans = 0;
for(auto n : arr)
{
mp[n]=mp[n-diff]+1;
ans = max(ans, mp[n]);
}
return ans;
}
};
|
3. 黄金矿工
题目：
黄金矿工(Path with Maximum Gold)
地址：
https://leetcode-cn.com/contest/weekly-contest-157/problems/path-with-maximum-gold/
题意：
在一个m*n的地图中，每个格子都用个整数表示，为0的格子不能走，只能走正整数的格子，只能上下左右相邻格子移动，移动过的格子不能再回头经过。
要求移动路径和最大的值是多少。
1 <= grid.length, grid[i].length <= 15
0 <= grid[i][j] <= 100
最多 25 个单元格是正整数。
思路：
由于题目的测试数据很简单，直接暴力深搜就能过。还可以做下记忆化搜索，搜过的位置和状态下次直接返回。
代码：
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
51
52
53
54
55
56
57
58
59
60
61
62
| class Solution {
public:
int dirx[4]={1,-1,0,0};
int diry[4]={0,0,-1,1};
map<pair<int, int>, int> pos2num;
map<int, int> memo;
int N = 0;
int calHash(int r, int c, int status)
{
int hash = 0;
hash = pos2num[{r, c}];
hash <<= N;
hash |= status;
return hash;
}
int dfs(int r, int c, vector<vector<int>>& grid, int status)
{
int hash = calHash(r, c, status);
if(memo.find(hash)!=memo.end())
return memo[hash];
int value = grid[r][c];
int ret = 0;
for(int i = 0; i < 4; ++i)
{
int x = dirx[i]+r;
int y = diry[i]+c;
if(x>=0&&x<grid.size()&&y>=0&&y<grid[x].size()&&grid[x][y]>0)
{
grid[r][c] = 0;
int tmp = dfs(x, y, grid, status | (1<<pos2num[{x, y}]));
ret = max(tmp, ret);
grid[r][c] = value;
}
}
return memo[hash] = ret + value;
}
int getMaximumGold(vector<vector<int>>& grid) {
int ans = 0;
for(int i = 0; i < grid.size(); ++i)
{
for(int j = 0; j < grid[i].size(); ++j)
{
if(grid[i][j] && pos2num.find({i, j}) == pos2num.end())
pos2num[{i, j}] = N++;
}
}
for(int i = 0; i < grid.size(); ++i)
{
for(int j = 0; j < grid[i].size(); ++j)
{
if(grid[i][j])
{
int status = 1 << pos2num[{i, j}];
int get = dfs(i, j, grid, status);
ans = max(ans, get);
}
}
}
return ans;
}
};
|
4. 统计元音字母序列的数目
题目：
统计元音字母序列的数目(Count Vowels Permutation)
地址：
https://leetcode-cn.com/contest/weekly-contest-157/problems/count-vowels-permutation/
题意：
给你一个整数 n，请你帮忙统计一下我们可以按下述规则形成多少个长度为 n 的字符串：
字符串中的每个字符都应当是小写元音字母（’a’, ‘e’, ‘i’, ‘o’, ‘u’）
每个元音 ‘a’ 后面都只能跟着 ‘e’
每个元音 ‘e’ 后面只能跟着 ‘a’ 或者是 ‘i’
每个元音 ‘i’ 后面 不能 再跟着另一个 ‘i’
每个元音 ‘o’ 后面只能跟着 ‘i’ 或者是 ‘u’
每个元音 ‘u’ 后面只能跟着 ‘a’
由于答案可能会很大，所以请你返回 模 10^9 + 7 之后的结果。
思路：
典型的动态规划，长度为n的字符串的个数可以从n-1长度字符串的个数中计算出来。
例如：长度为n-1的以a结尾的字符串，可以转换成长度为n的以’e’结尾的字符串。
通过搜索枚举出所有符合要求的字符串，每个加一，最后记忆搜索即可。
代码：
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
| class Solution {
public:
map<char, vector<char>> relation;
vector<char> letter = {'a', 'e', 'i', 'o', 'u'};
const int MOD = 1e9 + 7;
map<pair<int, char>, int> memo;
int dfs(int i, int n, char ch)
{
if(i==n)
return 1;
if(memo.find({i, ch})!=memo.end())
return memo[{i, ch}];
int ans = 0;
for(auto c : relation[ch])
{
ans += dfs(i+1, n, c);
ans %= MOD;
}
return memo[{i, ch}] = ans;
}
int countVowelPermutation(int n) {
relation['a'] = {'e'};
relation['e'] = {'a', 'i'};
relation['i'] = {'a', 'e', 'o', 'u'};
relation['o'] = {'i', 'u'};
relation['u'] = {'a'};
int ans = 0;
for(char ch : letter)
{
ans += dfs(1, n, ch);
ans %= MOD;
}
return ans;
}
};
|
