解法：
基本思路，判断每两点的斜率，注意斜率无穷大时的判断
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
| class Solution {
public:
bool checkStraightLine(vector<vector<int>>& coordinates) {
double k;
if((coordinates[1][1]-coordinates[0][1])==0)
k=0;
else if((coordinates[1][0]-coordinates[0][0])==0)
k=INT_MAX;
else k=(coordinates[1][1]-coordinates[0][1])/((coordinates[1][0]-coordinates[0][0])*1.0);
int n=coordinates.size();
for(int i=0;i<n-1;i++)
{
double k1;
if((coordinates[i+1][1]-coordinates[i][1])==0)
k1=0;
else if((coordinates[i+1][0]-coordinates[i][0])==0)
k1=INT_MAX;
else k1=(coordinates[i+1][1]-coordinates[i][1])/((coordinates[i+1][0]-coordinates[i][0])*1.0);
if(k1!=k)
return false;
}
return true;
}
};
|
解法1：set
思路：
1.先将字符串排序，保证后面的若是子文件夹，在前面必然已经出现过他的父文件夹
2.遍历每个字符串，遇到‘/’就判断当前路径是否已经存在，若存在直接进行下一循环，若单个字符串到达最后也没有父文件夹，就将这个路径添加到set集合中作为父文件夹
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
| class Solution {
public:
vector<string> removeSubfolders(vector<string>& folder) {
sort(folder.begin(),folder.end());
int n=folder.size();
set<string> s;
for(int i=0;i<n;i++)
{
string temp=folder[i];
int size=temp.size();
string t="";
for(int j=0;j<size;j++)
{
if(temp[j]=='/'&&t!="")
{
if(s.find(t)!=s.end())
{
break;
}
}
t+=temp[j];
}
if(s.find(t)==s.end())
{
s.insert(t);
}
}
vector<string> res(s.begin(),s.end());
return res;
}
};
|
解法1：滑动窗口
思路：
1.统计四个字符出现的次数
2.比较四个字符出现的次数和当前窗口内各字符出现次数
3.滑动窗口进行比较找到最短符合子串
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 balancedString(string s) {
int n=s.size();
int k=n/4;
map<char,int> count;
for(int i=0;i<n;i++)
{
count[s[i]]++;
}
map<char,int> a;
int res=n;
int i=0;
int j=0;
while(i<n)
{
while(j<n&&(count['Q']-a['Q']>k||count['W']-a['W']>k||count['E']-a['E']>k||count['R']-a['R']>k))
{
a[s[j]]++;
j++;
}
if(count['Q']-a['Q']<=k&&count['W']-a['W']<=k&&count['E']-a['E']<=k&&count['R']-a['R']<=k)
res=min(res,j-i);
a[s[i]]--;
i++;
}
return res;
}
};
|
解法1：动态规划
动态规划。在开始计算之前，先把题目给出的数据整理一下。将 [startTime[i], endTime[i], profit[i]] 整理为数组，并按 startTime[i] - endTime[i] - profit[i]] 排序。
用 dp[i] 表示完成第 i 份工作所能获得的最大收益。假设有第 x 份工作（x < i）：
如果 x 与 i 时间上不重合，表示即可完成工作 x 又可以完成工作 i，那么有：dp[i] = max(dp[i], dp[x] + profit[i])
如果 x 与 i 在时间上重合了，那么将无法完成工作 x
由此可见，dp[i] 的值取决于在它前面所有与之时间不重合的工作收益，即：
dp[i] = max(dp[0], dp[1], …, dp[j]) + profit[i] （j 为 i 之前最后一个与之时间区域不重合的工作）
但是，如果每次都遍历 0 ~ j 必然会超时，所以需要记录下时间区域不重合的工作所在的最大位置。
作者：jalan
链接：https://leetcode-cn.com/problems/maximum-profit-in-job-scheduling/solution/python-dong-tai-gui-hua-xiang-jie-by-jalan-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
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
| class Solution {
public:
int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
int n=startTime.size();
vector<vector<int>> time(n,vector<int>(3,0));
for(int i=0;i<n;i++)
{
time[i][0]=startTime[i];
time[i][1]=endTime[i];
time[i][2]=profit[i];
}
sort(time.begin(),time.end());
int res=0;
int s=0;
vector<int> dp(n,0);
int p=0;
for(int i=0;i<n;i++)
{
for(int j=p;j<i;j++)
{
if(time[i][0]>=time[j][1])
{
if(j==p)
p++;
s=max(s,dp[j]);
}
}
dp[i]=s+time[i][2];
res=max(res,dp[i]);
}
return res;
}
};
|