解法：切比雪夫距离
计算max(dx,dy)取较大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int minTimeToVisitAllPoints(vector<vector<int>>& points) {
int res=0;
int n=points.size();
for(int i=1;i<n;i++)
{
int x=abs(points[i][0]-points[i-1][0]);
int y=abs(points[i][1]-points[i-1][1]);
res+=max(x,y);
}
return res;
}
};
|
解法：
1.计算各列存在的服务器数量，各行服务器存在的数量，记录服务器的总数量sum
2.当该行该列服务器为1时，表示这个服务器没有连接，统计数量s_res
3.返回sum-s_res
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
| class Solution {
public:
int countServers(vector<vector<int>>& grid) {
int n=grid.size(),m=grid[0].size();
vector<int> col(m,0);
vector<int> row(n,0);
int sum=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
row[i]+=grid[i][j];
col[j]+=grid[i][j];
sum+=grid[i][j];
}
}
int s_res=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(row[i]==1&&col[j]==1&&grid[i][j])
s_res++;
}
}
return sum-s_res;
}
};
|
解法：map
思路：
1.利用map存储产品，遍历每个产品数组字符串，将其产品各位数组成的前缀字符串，添加产品到map中，map的名就是前缀字符串
2.遍历searchword，在map中搜索各前缀字符串
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 Solution {
public:
vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
map<string,vector<string>> m;
int n=products.size();
for(int i=0;i<n;i++)
{
string t=products[i];
int size=t.size();
string temp="";
for(int j=0;j<size;j++)
{
temp+=t[j];
m[temp].push_back(t);
}
}
vector<vector<string>> res;
int len=searchWord.size();
string c="";
for(int i=0;i<len;i++)
{
c+=searchWord[i];
if(m.count(c))
{
sort(m[c].begin(),m[c].end());
if(m[c].size()>3)
{
vector<string> temp(m[c].begin(),m[c].begin()+3);
res.push_back(temp);
}
else
{
vector<string> temp(m[c].begin(),m[c].end());
res.push_back(temp);
}
}
else
{
res.push_back({});
}
}
return res;
}
};
|
解法1：动态规划
1.dp[i][j]表示移动i步，停在j位置的总方案数
2.得到dp[i][j]=sum(dp[i-1][j],dp[i-1][j-1],dp[i-1][j+1])
注意：判断steps和arrlen的关系，可以减少时间复杂度，可行位置必然不会超过steps的长度
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 numWays(int steps, int arrLen) {
int arrlen=min(steps,arrLen);
int mod=pow(10,9)+7;
vector<vector<long long>> dp(steps+1,vector<long long>(arrlen,0));
dp[0][0]=1;
for(int i=1;i<steps+1;i++)
{
for(int j=0;j<arrlen;j++)
{
dp[i][j]=dp[i-1][j];
if(j!=0)
dp[i][j]+=dp[i-1][j-1];
if(j!=arrlen-1)
dp[i][j]+=dp[i-1][j+1];
dp[i][j]%=mod;
}
}
return dp[steps][0]%mod;
}
};
|