解法：
遍历一遍，记录R，L,R==L时同时清零且res++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
int balancedStringSplit(string s) {
int l=0,r=0;
int res=0;
int n=s.size();
for(int i=0;i<n;i++)
{
if(s[i]=='R')
r++;
else if(s[i]=='L')
l++;
if(r==l)
{
res++;
r=0;
l=0;
}
}
return res;
}
};
|
解法1：DFS
思路：
从国王出发，最多有8个皇后能攻击到国王，建立方向数组，8个方向都从国王走一遍，
1.遇到皇后记录位置且进行下一方向，
2.遇到边界进行下一方向
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
| class Solution {
public:
vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {
vector<vector<bool>> used(8,vector<bool>(8,false));
int dir[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
vector<vector<int>> res;
for(int i=0;i<queens.size();i++)
{
used[queens[i][0]][queens[i][1]]=true;
}
for(int k=0;k<8;k++)
{
int x=king[0],y=king[1];
while(x+dir[k][0]>=0&&x+dir[k][0]<8&&y+dir[k][1]>=0&&y+dir[k][1]<8)
{
x+=dir[k][0];
y+=dir[k][1];
if(used[x][y])
{
vector<int> temp;
temp.push_back(x);
temp.push_back(y);
res.push_back(temp);
break;
}
}
}
return res;
}
};
|
解法1：动态规划
思路：采用动态规划策略
1.dp[n][i][l]表示掷第n次数字i-1连续出现l次能组成的最多序列数
2.状态转移方程
（1）如果当前数字j与上一数字k相同，对全部符合的l来说：dp[i][j][l+1]=dp[i-1][k][l];即数字j连续出现，当前情况数量等于上一轮连续掷出i-1次j的情况数量
（2）如果不相等,对全部符合的l来说：dp[i][j][1]+=dp[i-1][k][l];即数字j并非连续出现，等于上一轮掷出非数字j的所有情况和
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
| class Solution {
public:
int dieSimulator(int n, vector<int>& rollMax) {
int dp[n+1][6][20];
memset(dp,0,sizeof(dp));
int mod=pow(10,9)+7;
for(int i=0;i<6;i++)
{
dp[1][i][1]=1;
}
for(int i=2;i<=n;i++)
{
for(int j=0;j<6;j++)
{
for(int k=0;k<6;k++)
{
if(k!=j)
{
for(int l=1;l<=rollMax[k];l++)
{
dp[i][j][1]+=dp[i-1][k][l];
dp[i][j][1]%=mod;
}
}
else
{
for(int l=1;l<rollMax[k];l++)
{
dp[i][j][l+1]=dp[i-1][k][l];
dp[i][j][l+1]%=mod;
}
}
}
}
}
int res=0;
for(int j=0;j<6;j++)
{
for(int l=1;l<=rollMax[j];l++)
{
res+=dp[n][j][l];
res%=mod;
}
}
return res;
}
};
|
解法1：map，考虑4种情况
问题分析：能够满足答案的条件
1.只有一种数字。 如：1 1 1 1 1
2.有多种数字，每个数字只出现1次。如： 1 2 3 4 5
3.有多种数字，其中一种数字出现n+1次，其他出现n次。如：1 1 1 2 2 2 3 3 3 4 4 4 4
4.有多种数字，其中一种数字出现1次，其他出现n次。如：1 2 2 2 3 3 3 4 4 4
建立两个数字count和f_count，count用来统计当前各个数字出现的次数，f_count[i]用来统计频率为i的数字个数。
因此成立的条件为，f_count[1]==n||最高频次==1||(f_count[最高频次]==1&&f_count[最高频次-1]==n-1)||f_count[最高频次]==(n-1)&&f_count[1]==1)
因此，需要两个变量,n表示有多少种数字，f_max表示最高频次为多少
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int maxEqualFreq(vector<int>& nums) {
int count[100005],f_count[100005];
memset(count,0,sizeof(count));
memset(f_count,0,sizeof(f_count));
int n=0,f_max=0,res=0;
for(int i=0;i<nums.size();i++)
{
int num=nums[i];
if(count[num]==0)
n++;
count[num]++;
if(count[num])
f_count[count[num]-1]--;
f_count[count[num]]++;
f_max=max(f_max,count[num]);
if(f_count[1]==n||f_max==1||f_count[f_max]==1&&f_count[f_max-1]==n-1||f_count[f_max]==n-1&&f_count[1]==1)
res=i+1;
}
return res;
}
};
|