解法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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| class Solution {
public:
string tictactoe(vector<vector<int>>& moves) {
int n=moves.size();
vector<vector<char>> res(3,vector<char>(3,' '));
for(int i=0;i<n;i++)
{
if(i%2==0)
res[moves[i][0]][moves[i][1]]='X';
else
{
res[moves[i][0]][moves[i][1]]='O';
}
}
bool f1=true,f2=true,f3=true,f4=true;
for(int i=0;i<3;i++)
{
if(n%2)
{
if(res[moves[n-1][0]][i]!='X')
{
f1=false;
}
if(res[i][i]!='X')
{
f2=false;
}
if(res[2-i][i]!='X')
{
f3=false;
}
if(res[i][moves[n-1][1]]!='X')
f4=false;
}
else
{
if(res[moves[n-1][0]][i]!='O')
{
f1=false;
}
if(res[i][i]!='O')
{
f2=false;
}
if(res[2-i][i]!='O')
{
f3=false;
}
if(res[i][moves[n-1][1]]!='O')
f4=false;
}
}
if(f1||f2||f3||f4)
{
if(n%2)
{
return "A";
}
return "B";
}
if(n==9) return "Draw";
return "Pending";
}
};
|
解法1：解方程
小学方程题。。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
vector<int> numOfBurgers(int tomatoSlices, int cheeseSlices) {
vector<int> res;
int x,y;
for(int i=0;i<=cheeseSlices;i++)
{
if(4*i+2*(cheeseSlices-i)==tomatoSlices)
{
res.push_back(i);
res.push_back(cheeseSlices-i);
return res;
}
}
return res;
}
};
|
解法1：dp动态规划
1.dp[i][j]表示以i,j为正方形右下角点所能组成的最长的正方形
2.初始化dp[i][0]=matrix[i][0];dp[0][j]=matrix[0][j];
3.状态转移方程,
若dp[i-1][j-1]==dp[i-1][j]&&dp[i-1][j-1]==dp[i][j-1]&&matrix[i][j], dp[i][j]=dp[i-1][j-1]+1;
否则若matrix[i][j] dp[i][j]=min(min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1;
4.返回res=sum(dp[i][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
| class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int n=matrix.size(),m=matrix[0].size();
vector<vector<int>> dp(n,vector<int>(m,0));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(j==0)
dp[i][j]=matrix[i][j];
if(i==0)
dp[i][j]=matrix[i][j];
}
}
for(int i=1;i<n;i++)
{
for(int j=1;j<m;j++)
{
if(dp[i-1][j-1]==dp[i-1][j]&&dp[i-1][j-1]==dp[i][j-1]&&matrix[i][j])
dp[i][j]=dp[i-1][j-1]+1;
else if(matrix[i][j])
dp[i][j]=min(min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1;
}
}
int res=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
res+=dp[i][j];
}
}
return res;
}
};
|
解法1：dp
1.dp[i][j]表示,[0,i]位置字符串分成j份，需要的最少修改字符数
定义cost[i][j]数组，表示[i,j]位置字符串转化为回文串所需要的最小代价
2.初始化dp[i][1]=cost[0][i];
3.状态转移方程dp[i][j]=min(dp[x][j-1]+cost[x+1][i])其中x[0,i)
4.返回dp[n-1][k];
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:
int palindromePartition(string s, int k) {
int n=s.size();
vector<vector<int>> dp(n,vector<int>(k+1,n));
vector<vector<int>> cost(n,vector<int>(n,0));
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cost[i][j]=get_cost(i,j,s);
}
}
for(int i=0;i<n;i++)
{
dp[i][1]=cost[0][i];
for(int j=2;j<k+1;j++)
{
for(int x=0;x<i;x++)
{
dp[i][j]=min(dp[i][j],dp[x][j-1]+cost[x+1][i]);
}
}
}
return dp[n-1][k];
}
int get_cost(int i,int j,string s)
{
int res=0;
while(i<j)
{
if(s[i]!=s[j])
res++;
i++;j--;
}
return res;
}
};
|