检查是否为直线,暴力算斜率,但要注意分母为0的情况
class Solution {
public:
bool checkStraightLine(vector<vector<int>>& coordinates) {
double n1 = coordinates[1][0] - coordinates[0][0];
double n2 = coordinates[1][1] - coordinates[0][1];
if (n2 == 0) {
for (auto v : coordinates) {
if (v[1] != coordinates[0][1])
return false;
}
return true;
}
double p = n1 / n2;
for (int i = 1; i < coordinates.size(); i++) {
double p1 = coordinates[i][0] - coordinates[i - 1][0];
double p2 = coordinates[i][1] - coordinates[i - 1][1];
double m = p1 / p2;
if (abs(p - m) > 0.000005)
return false;
}
return true;
}
};
删除子文件,即找出子串,删除对应串
class Solution {
public:
vector<string> removeSubfolders(vector<string>& folder)
{
sort(folder.begin(),folder.end());
vector<string> result;
for(string &s:folder)
if(result.empty()||result.back().compare(0,result.back().length(),s,0,result.back().length())!=0||s[result.back().length()]!='/')
return result;
}
};
找出最小替代数可以使其平衡
int balancedString(string s) {
unordered_map<int, int> count;
int n = s.length(), res = n, i = 0;
for (int j = 0; j < n; ++j) {
count[s[j]]++;
}
for (int j = 0; j < n; ++j) {
count[s[j]]--;
while (i < n && count['Q'] <= n / 4 && count['W'] <= n / 4 && count['E'] <= n / 4 && count['R'] <= n / 4) {
res = min(res, j - i + 1);
count[s[i++]] += 1;
}
}
return res;
}
最大区间和
class Solution {
public:
int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
int vsize = startTime.size();
vector<vector<int>> v(vsize, vector<int>(3));
for (int i = 0; i < vsize; i++) {
v[i][1] = startTime[i];
v[i][0] = endTime[i];
v[i][2] = profit[i];
}
sort(v.begin(), v.end());
map<int,int> dp;
dp[0] = 0;
for (auto ve : v) {
auto it = dp.upper_bound(ve[1]);
it--;
int cur = it->second + ve[2];
if (cur > dp.rbegin()->second)
dp[ve[0]] = cur;
}
return dp.rbegin()->second;
}
};