5213.玩筹码
解法1：
本质是找奇数的个数和偶数的个数，输出较小值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int minCostToMoveChips(vector<int>& chips) {
int n=chips.size();
int ji=0,ou=0;
for(int i=0;i<n;i++)
{
if(chips[i]%2)
ji++;
else ou++;
}
return min(ji,ou);
}
};
|
5214.最长定差子序列
解法1：map
用map存当前元素的下个数值arr[i]+difference表示当前子序列的最大长度
以arr = [1,5,7,8,5,3,4,2,1], difference = -2为例
1的下一个子序列数字应该-1，我们存m[-1]=max(m[-1],m[1]+1)；
5的下一个子序列数字应该3，我们存m[3]=max(m[3],m[5]+1)；
7的下一个子序列数字应该5，我们存m[5]=max(m[5],m[7]+1)；
8的下一个子序列数字应该6，我们存m[6]=max(m[6],m[8]+1)；
5的下一个子序列数字应该3，我们存m[3]=max(m[3],m[5]+1)；
3的下一个子序列数字应该1，我们存m[1]=max(m[1],m[3]+1)；
依次类推，找到map中存的最大数值就是要返回的最大子序列长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int longestSubsequence(vector<int>& arr, int difference) {
map<int,int> m;
int n=arr.size();
for(int i=0;i<n;i++)
{
m[arr[i]+difference]=max(m[arr[i]]+1,m[arr[i]+difference]);
}
int res=INT_MIN;
for(map<int,int>::iterator ite=m.begin();ite!=m.end();ite++)
{
res=max(res,ite->second);
}
return res;
}
};
|
5215.黄金矿工
解法1：dfs
因为数据量很小，所以可以采用dfs来解决该题。
用一个used记录走过的点，temp记录当前获得黄金，dir是4个行进方向
注意跳过为0的点
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
| class Solution {
int res=INT_MIN;
int n,m;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
public:
int getMaximumGold(vector<vector<int>>& grid) {
n=grid.size(),m=grid[0].size();
int temp=0;
vector<vector<bool>> used(n,vector<bool>(m,false));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(grid[i][j]==0)
continue;
used[i][j]=true;
temp=temp+grid[i][j];
res=max(res,temp);
dfs(i,j,temp,grid,used);
temp=temp-grid[i][j];
used[i][j]=false;
}
}
return res;
}
void dfs(int i,int j,int temp,vector<vector<int>>& grid,vector<vector<bool>>& used)
{
for(int k=0;k<4;k++)
{
int x=dir[k][0]+i,y=dir[k][1]+j;
if(x>=0&&x<n&&y>=0&&y<m&&!used[x][y]&&grid[x][y]!=0)
{
used[x][y]=true;
temp=temp+grid[x][y];
dfs(x,y,temp,grid,used);
res=max(res,temp);
temp=temp-grid[x][y];
used[x][y]=false;
}
}
return ;
}
};
|
5216.统计元音字母序列的数目
解法1：map
map 存当前长度下以这种字母结尾的字符串个数
注意一个公式(a+b)%c=(a%c+b%c)%c;
最后找到长度为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
| class Solution {
public:
int countVowelPermutation(int n) {
long long res;
long long mod=(pow(10,9)+7);
map<char,long long> m;
m['a']=1;
m['e']=1;
m['i']=1;
m['o']=1;
m['u']=1;
map<char,long long> mnew;
while(n-->1)
{
mnew['a']=(m['e']%mod+m['i']%mod+m['u']%mod)%mod;
mnew['e']=(m['a']%mod+m['i']%mod)%mod;
mnew['i']=(m['e']%mod+m['o']%mod)%mod;
mnew['o']=m['i']%mod;
mnew['u']=(m['o']%mod+m['i']%mod)%mod;
m['o']=mnew['o'];
m['i']=mnew['i'];
m['a']=mnew['a'];
m['e']=mnew['e'];
m['u']=mnew['u'];
}
res=(m['a']%mod+m['e']%mod+m['i']%mod+m['o']%mod+m['u']%mod)%mod;
return res;
}
};
|