领扣×天池|超级码力在线编程大赛 第1场题解

正三角形拼接

解题思路

分类讨论

  1. 存在 [a,a,a] 的情况,0 次切割。
  2. 存在 [a,a*2] 的情况,1 次切割即可。
  3. 存在 [a,a,b]a \lt b1 次切割即可。
  4. 其它情况,保留最短的那根,2 次切割。

代码思路

维护一个哈希表,记录每个长度的数量。然后根据上述逻辑进行判断。

复杂度分析

设木棍数量为 N

时间复杂度

  • 时间复杂度为 O(N)

空间复杂度

  • 空间复杂度为 O(N)

源代码

// 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

树木规划

解题思路

正序遍历数组,如果有两棵树发生冲突(间隔小于 d),贪心地将坐标大的树优先移除,这样对后续的树木的影响最小。

复杂度分析

设树木的棵数为 N

时间复杂度

  • 需要遍历 1 遍数组,时间复杂度为 O(N)

空间复杂度

  • 空间复杂度为 O(1)

源代码

// 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

对称前后缀

解题思路

对于一个区间,我们可以用一个值记录它的最长对称前后缀。并且我们可以由小区间的值来推导出大区间的值,我们可以用动态规划来结局。

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
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

大楼间穿梭

解题思路

对于一个数组,计算每个数右侧第一个大于它的数,我们可以用 单调栈 这一数据结构解决。

每次当我们将一个数压入栈中时,就不断地将小于等于它的栈顶元素弹出,这样我们就可以得到栈中最后一个入栈且大于它的数。并且保持栈中的元素从栈底到栈顶单调递减。(出题人在生成输出数据时,弹出元素的判断将小于等于写成了小于,所以导致实际结果变成了找到大于等于入栈元素的值。)

例如,[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
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)

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,098评论 5 476
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,213评论 2 380
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 149,960评论 0 336
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,519评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,512评论 5 364
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,533评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,914评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,574评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,804评论 1 296
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,563评论 2 319
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,644评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,350评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,933评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,908评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,146评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,847评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,361评论 2 342

推荐阅读更多精彩内容