文章目录
1. 比赛结果
通过了 3 题，第245名，进入复赛了，收获 T恤 一件，哈哈。
2. 题目
1. 树木规划
描述
在一条直的马路上，有 n 棵树，每棵树有一个坐标，代表它们距离马路起点的距离。 如果每相邻的两棵树之间的间隔不小于 d，那么我们认为这些树是美观的。 请计算出最少移除多少棵树，可以让这些树变得美观。
树木的棵树为 n，1 <= n <= 10^5。 树木的坐标用 trees 表示，0 <= trees[i] <= 10^9。 最小美观间隔为 d，1 <= d <= 10^9。 保证输入的坐标是排好序的，且两两不相同。
说明
样例中，将位置 2 和 6 的树木移走，剩下 [1, 3, 5] ，它们是美观的。
示例
输入：
[1,2,3,5,6]
2
输出：
2
解题：
- 直接遍历，不满足的移除
class Solution {
public:
/**
* @param trees: the positions of trees.
* @param d: the minimum beautiful interval.
* @return: the minimum number of trees to remove to make trees beautiful.
*/
int treePlanning(vector<int> &trees, int d) {
// write your code here.
int prev = trees[0], s = 0;
for(int i = 1; i < trees.size(); ++i)
{
if(trees[i]-prev < d)//不满足
{
s++;//移除
}
else
{
prev = trees[i];
}
}
return s;
}
};
2. 正三角形拼接
描述
给出 n 根木棍，每次切割可以将1根木棍切成 2 段。请计算出最少切割几次，可以从所有木棍中选出 3 根，组成一个正三角形。
一开始的木棍根数为 n，3 ≤ n ≤ 1000。所有木棍的长度为一个整型数组 lengths，1 < length_i ≤ 10^9。
切割必须要将木棍分成 2 根整数长度的木棍，而且总长度要和原木棍相等。
说明
可以从长为7的木棍中，切出2根长为3的木棍，那么木棍的长度应该为[2，3，1，3，3，5]，可以拼出边长为3的正三角形。
示例
输入：
[2，3，7，5]
输出：
2
解题：
class Solution {
public:
/**
* @param lengths: the lengths of sticks at the beginning.
* @return: return the minimum number of cuts.
*/
int makeEquilateralTriangle(vector<int> &lengths) {
// write your code here.
map<int, int> m;
int cut = 2;//最多切两次
for(int i = 0; i < lengths.size(); i++)
m[lengths[i]]++;//长度计数
for(auto& mi : m)
{
if(mi.second == 2)//有2段了
{
if(m.lower_bound(mi.first+1) != m.end())
cut = min(cut, 1);//有更长的，切1次
}
else if(mi.second >= 3)//有3段了，不用切
return 0;
if(mi.first%2==0 && m.count(mi.first/2))
cut = min(cut, 1);//如果能被平均切开，且有1段一样的，切1次就可以
}
return cut;
}
};
3. 大楼间穿梭
描述
蜘蛛侠在大楼间穿梭。大楼的高度可以看作是一个从左到右排列的数组。
现在蜘蛛侠站在第一栋大楼上，他想跳到最后一栋上。
- 蜘蛛侠的视野为 k，他可以花费 x 点体力，用蛛丝移动到右侧k幢建筑中第一栋比当前位置高的大楼（
应该是 高或者相同高度，题目有问题）。 - 或者蜘蛛侠可以花费 y 点体力，跳跃到右侧接下来两栋大楼其中一栋。
请计算蜘蛛侠最少花费多少体力，到达最后一栋上。
大楼的高度为数组 heights，一共有 n 栋大楼，2 ≤ n ≤ 10^5，1 <= heights_i ≤ 10^9.蜘蛛侠的视野为 k，1 ≤ k ≤ n。两种行动的体力花费满足 1 ≤ x，y ≤ 10^9。
说明
样例中，先花费6点体力跳到第三栋建筑，再花费10点到达最后一栋。
示例
输入：
heights=[1，5，4，3，3，5]
k=3
x=10
y=6
输出：
16
解题：
- 单调栈算出右侧高度 >= 当前的 第一个位置（逆序遍历）
- 然后简单的动态规划即可
class Solution {
public:
/**
* @param heights: the heights of buildings.
* @param k: the vision.
* @param x: the energy to spend of the first action.
* @param y: the energy to spend of the second action.
* @return: the minimal energy to spend.
*/
long long shuttleInBuildings(vector<int> &heights, int k, int x, int y) {
// write your code here.
int n = heights.size(), i, j, K;
stack<int> s;
vector<int> rightTall(n, -1);//右侧高或者相等的第一个位置
for(int i = n-1; i >= 0; i--) //单调栈
{
while(!s.empty() && heights[s.top()] < heights[i])
//右侧比我小的，没有用
s.pop();
if(!s.empty() && s.top()-i <= k)//有大于等于我的，且距离在 k 以内
rightTall[i] = s.top();//记录下来
s.push(i);
}
vector<long long> dp(n, LONG_LONG_MAX);
dp[0] = 0;
for(int i = 0; i < n; i++) // DP
{
if(dp[i] == LONG_LONG_MAX)
continue;
if(i+1 < n && dp[i+1] > dp[i]+y)//右侧1
dp[i+1] = dp[i]+y;
if(i+2 < n && dp[i+2] > dp[i]+y)//右侧2
dp[i+2] = dp[i]+y;
if(rightTall[i] != -1 && dp[rightTall[i]] > dp[i]+x)
dp[rightTall[i]] = dp[i]+x;
//直接跳到 k 以内的 第一个 >= 我的位置
}
return dp[n-1];
}
};
4. 对称前后缀
描述
给定一个字符串 s。我们令一个字符串的权值为一个字符串的最长对称前后缀长度。
请求出 s 的所有子串的权值的总和。
例如，”abcxyzcba” 的最长对称前后缀的长度为3，因为“abc”和“cba”对称。
字符串的长度为 n，1 ≤ n ≤ 3*10^3。字符串均由小写英文字符组成。
说明
样例中，单个字符的子串的权值为1，它们的和为 7。
另外的权值为：
"bacb"->1，
"bacbdab"->2，
"bdab"->1，
"acbda'->1，
所以权值和为12。
示例
输入：
"bacbdab
输出：
12
解题：
- 区间DP
class Solution {
public:
/**
* @param s: a string.
* @return: return the values of all the intervals.
*/
long long suffixQuery(string &s) {
// write your code here
long long n = s.size(), ans = n;
//区间DP，dp[i][j] 表示区间内的 子串的最大权值
vector<vector<int>> dp(n, vector<int>(n, 0));
for(int i = 0; i < n; i++)
dp[i][i] = 1;
for(int len = 1, i; len < n; len++)
{
for(i = 0; i+len < n; i++)
{
if(s[i] == s[i+len])//子串首尾相同
{
int length = len-1;
//除去首尾 里面的子串[i+1, i+len-1]的长度
if(dp[i+1][i+len-1] == length)// 里面正反序都相同
dp[i][i+len] = dp[i+1][i+len-1]+2;
//把两个端点都可以加上
else
dp[i][i+len] = dp[i+1][i+len-1]+1;
//只能加上1端
}
ans += dp[i][i+len];
}
}
return ans;
}
};
我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！