1. 正三角形拼接

解题思路

分类讨论

1. 存在 $[a,a,a]$ 的情况，$0$ 次切割。
2. 存在 $[a,a*2]$ 的情况，$1$ 次切割即可。
3. 存在 $[a,a,b]$，$a \lt b$，$1$ 次切割即可。
4. 其它情况，保留最短的那根，$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 result

Java题解相见 九章算法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_count

Java题解相见 九章算法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 resultx

Java题解相见 九章算法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