1. 正三角形拼接
解题思路
分类讨论
- 存在 $[a,a,a]$ 的情况，$0$ 次切割。
- 存在 $[a,a*2]$ 的情况，$1$ 次切割即可。
- 存在 $[a,a,b]$，$a \lt b$，$1$ 次切割即可。
- 其它情况，保留最短的那根，$2$ 次切割。
代码思路
维护一个哈希表，记录每个长度的数量。然后根据上述逻辑进行判断。
复杂度分析
设木棍数量为 $N$。
时间复杂度
- 时间复杂度为 $O(N)$。
空间复杂度
- 空间复杂度为 $O(N)$。
源代码
// This solution is powered by @lintcode.com
class Solution {
public:
/**
* @param lengths: the lengths of sticks at the beginning.
* @return: return the minimum number of cuts.
*/
int makeEquilateralTriangle(vector<int> &lengths) {
unordered_map<int, int> lengthCount;
// 最多 2 次一定可行
int result = 2;
int maxLen = 0;
for (int length: lengths) {
lengthCount[length]++;
maxLen = max(maxLen, length);
}
for (int length: lengths) {
// 如果存在 3 个相同的，0 次
if (lengthCount[length] >= 3) {
result = 0;
}
// 如果有 2 根相同，且有 1 根更大的，1 次
else if (lengthCount[length] == 2) {
if (length < maxLen) {
result = min(result, 1);
}
}
// 如果有 1 根是当前两倍的，1 次
else {
if (lengthCount[length * 2] > 0) {
result = min(result, 1);
}
}
}
return result;
}
};# This solution is powered by @lintcode.com
class Solution:
"""
@param lengths: the lengths of sticks at the beginning.
@return: return the minimum number of cuts.
"""
def makeEquilateralTriangle(self, lengths):
length_count = collections.defaultdict(int)
# 最多 2 次一定可行
result = 2
max_length = 0
for length in lengths:
length_count[length] += 1
max_length = max(max_length, length)
for length in lengths:
# 如果存在 3 个相同的，0 次
if length_count[length] >= 3:
result = 0
# 如果有 2 根相同，且有 1 根更大的，1 次
elif length_count[length] == 2:
if length < max_length:
result = min(result, 1)
# 如果有 1 根当前两倍的，1次
else:
if length_count[length * 2] > 0:
result = min(result, 1)
return resultJava题解相见 九章算法solution
2. 树木规划
解题思路
正序遍历数组，如果有两棵树发生冲突（间隔小于 $d$），贪心地将坐标大的树优先移除，这样对后续的树木的影响最小。
复杂度分析
设树木的棵数为 $N$。
时间复杂度
- 需要遍历 $1$ 遍数组，时间复杂度为 $O(N)$。
空间复杂度
- 空间复杂度为 $O(1)$
源代码
// This solution is powered by @lintcode.com
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) {
int n = trees.size();
int removeCount = 0;
int lastPosition = trees[0];
for (int i = 1; i < n; i++) {
if (trees[i] - lastPosition < d) {
removeCount++;
}
else {
lastPosition = trees[i];
}
}
return removeCount;
}
};# This solution is powered by @lintcode.com
class Solution:
"""
@param trees: the positions of trees.
@param d: the minimum beautiful interval.
@return: the minimum number of trees to remove to make trees beautiful.
"""
def treePlanning(self, trees, d):
n = len(trees)
remove_count = 0
last_position = trees[0]
for i in range(1, n):
if trees[i] - last_position < d:
remove_count += 1
else:
last_position = trees[i]
return remove_countJava题解相见 九章算法solution
3. 对称前后缀
解题思路
对于一个区间，我们可以用一个值记录它的最长对称前后缀。并且我们可以由小区间的值来推导出大区间的值，我们可以用动态规划来结局。
令 $dp(left, right)$ 为区间 $[left, right]$ 的最长对称前后缀。
如果 $s[left] \neq s[right]$，那么 $dp(left, right) = 0$。
如果 $s[left] = s[right]$，那么：
如果区间 $[left+1,right-1]$ 是回文的，那么 $dp(left, right) = dp(left + 1, right - 1) + 2$。
否则 $dp(left, right) = dp(left + 1, right - 1) + 1$。
复杂度分析
设字符串长度为 $N$， 查询次数为 $M$。
时间复杂度
- $O(N^2)$ 的时间计算出所有区间的值，每次查询时间为 $O(1)$，总时间复杂度为 $O(N^2 + M)$。
空间复杂度
- 空间复杂度为 $O(N^2)$。
源代码
// This solution is powered by @lintcode.com
class Solution {
public:
/**
* @param s: a string.
* @return: return the values of all the intervals.
*/
long long suffixQuery(string &s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
long long result = 0;
for (int right = 0; right < n; right++) {
for (int left = 0; left <= right; left++) {
if (s[left] != s[right]) {
continue;
}
if (left == right) {
dp[left][right] = 1;
}
// 如果 [left + 1, right - 1] 是回文的话，+2，否则+1
else if (dp[left + 1][right - 1] == right - left - 1) {
dp[left][right] = dp[left + 1][right - 1] + 2;
}
else {
dp[left][right] = dp[left + 1][right - 1] + 1;
}
result += dp[left][right];
}
}
return result;
}
};# This solution is powered by @lintcode.com
class Solution:
"""
@param s: a string.
@return: return the values of all the intervals.
"""
def suffixQuery(self, s):
n = len(s)
dp = [[0] * n for _ in range(n)]
result = 0
for right in range(n):
for left in range(right + 1):
if s[left] != s[right]:
continue
if left == right:
dp[left][right] = 1
# 如果 [left + 1, right - 1] 是回文的话，+2，否则+1
elif dp[left + 1][right - 1] == right - left - 1:
dp[left][right] = dp[left + 1][right - 1] + 2
else:
dp[left][right] = dp[left + 1][right - 1] + 1
result += dp[left][right]
return resultxJava题解相见 九章算法solution
4. 大楼间穿梭
解题思路
对于一个数组，计算每个数右侧第一个大于它的数，我们可以用 单调栈 这一数据结构解决。
每次当我们将一个数压入栈中时，就不断地将小于等于它的栈顶元素弹出，这样我们就可以得到栈中最后一个入栈且大于它的数。并且保持栈中的元素从栈底到栈顶单调递减。（出题人在生成输出数据时，弹出元素的判断将小于等于写成了小于，所以导致实际结果变成了找到大于等于入栈元素的值。）
例如，$[5, 4, 2, 1]$ 已经按序入栈，当我们要将 $3$ 压入栈中时，找到最后一个大于它的数，那么应该将 $1, 2$ 弹出，最后一个大于 $3$ 的数应该是 $4$。
我们可以逆序地扫描数组，计算右侧第一个大于当前元素，并将当前元素压入栈中。栈中需要维护的应该是下标值。
在做好上述的处理后，就是线性的 $dp$ 了，$dp(i)$ 代表到第 $i$ 栋大楼的花费。应该根据当前位置更新后继位置的 $dp$ 值。设右侧第一栋更高的楼的距离是 $t$。
$dp(i + t) = min(dp(i + t), dp(i) + x)$
$dp(i + 1) = min(dp(i + 1), dp(i) + y)$
$dp(i + 2) = min(dp(i + 2), dp(i) + y)$
复杂度分析
设大楼数量为 $N$。
时间复杂度
- 时间复杂度为 $O(N)$。
空间复杂度
- 空间复杂度为 $O(N)$。
源代码
// This solution is powered by @lintcode.com
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) {
int n = heights.size();
stack<int> maxStack;
vector<int> rightFirst(n);
for (int i = n - 1; i >= 0; i--) {
while (maxStack.size() && heights[maxStack.top()] <= heights[i]) {
maxStack.pop();
}
if (maxStack.empty()) {
rightFirst[i] = n;
}
else {
rightFirst[i] = maxStack.top();
}
maxStack.push(i);
}
vector<long long> dp(n, -1);
dp[0] = 0;
for (int i = 0; i < n; i++) {
update(dp, n, i + 1, dp[i] + y);
update(dp, n, i + 2, dp[i] + y);
if (rightFirst[i] < n && rightFirst[i] - i <= k) {
update(dp, n, rightFirst[i], dp[i] + x);
}
}
return dp[n - 1];
}
void update(vector<long long>& dp, int n, int position, long long value) {
if (position >= n) {
return;
}
if (dp[position] == -1) {
dp[position] = value;
}
else {
dp[position] = min(dp[position], value);
}
}
};# This solution is powered by @lintcode.com
class Solution:
"""
@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.
"""
def shuttleInBuildings(self, heights, k, x, y):
n = len(heights)
max_stack = []
right_first = [0] * n
for i in range(n - 1, -1, -1):
while max_stack and heights[max_stack[-1]] <= heights[i]:
max_stack.pop()
if max_stack:
right_first[i] = max_stack[-1]
else:
right_first[i] = n
max_stack.append(i)
dp = [-1 for _ in range(n)]
dp[0] = 0
for i in range(n):
self.update(dp, n, i + 1, dp[i] + y)
self.update(dp, n, i + 2, dp[i] + y)
if right_first[i] < n and right_first[i] - i <= k:
self.update(dp, n, right_first[i], dp[i] + x)
pass
return dp[n - 1]
def update(self, dp, n, position, value):
if position >= n:
return
if dp[position] == -1:
dp[position] = value
else:
dp[position] = min(dp[position], value)
Java题解相见 九章算法solution
