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