力扣第451场周赛

一只鱼^_

已于 2025-05-25 18:45:58 修改

阅读量853

点赞数 7

分类专栏：力扣文章标签： leetcode 算法职场和发展 c++ 数据结构贪心算法动态规划

于 2025-05-25 18:42:57 首次发布

本文链接：https://blog.csdn.net/Script_Kids/article/details/148210844

版权

力扣专栏收录该内容

10 篇文章

订阅专栏

1. 木材运输的最小成本

给你三个整数 n、m 和 k。

有两根长度分别为 n 和 m 单位的木材，需要通过三辆卡车运输。每辆卡车最多只能装载一根长度不超过 k 单位的木材。

你可以将木材切成更小的段，其中将长度为 x 的木材切割成长度为 len1 和 len2 的段的成本为 cost = len1 * len2，并且满足 len1 + len2 = x。

返回将木材分配到卡车上的最小总成本。如果木材不需要切割，总成本为 0。

示例 1：

输入： n = 6, m = 5, k = 5

输出： 5

解释：

将长度为 6 的木材切割成长度为 1 和 5 的两段，成本为 1 * 5 == 5。现在三段长度分别为 1、5 和 5 的木材可以分别装载到每辆卡车。

示例 2：

输入： n = 4, m = 4, k = 6

输出： 0

解释：

两根木材已经可以直接装载到卡车上，因此不需要切割。

提示：

2 <= k <= 105
1 <= n, m <= 2 * k
输入数据保证木材总存在能被运输的方案。

模拟

class Solution {
public:
    long long minCuttingCost(int n, int m, int k) {
        long long sum=0;
        if(n>k) sum+=(n-k)*k;
        if(m>k) sum+=(m-k)*k;
        return sum;
    }
};

2. 移除相邻字符

给你一个由小写英文字母组成的字符串 s。

你必须在字符串 s 中至少存在两个连续字符时，反复执行以下操作：

移除字符串中最左边的一对按照字母表连续的相邻字符（无论是按顺序还是逆序，例如 'a' 和 'b'，或 'b' 和 'a'）。
将剩余字符向左移动以填补空隙。
当无法再执行任何操作时，返回最终的字符串。

注意：字母表是循环的，因此 'a' 和 'z' 也视为连续。

示例 1：

输入: s = "abc"

输出: "c"

解释:

从字符串中移除 "ab"，剩下 "c"。
无法进行进一步操作。因此，所有可能移除操作后的最终字符串为 "c"。
示例 2：

输入: s = "adcb"

输出: ""

解释:

从字符串中移除 "dc"，剩下 "ab"。
从字符串中移除 "ab"，剩下 ""。
无法进行进一步操作。因此，所有可能移除操作后的最终字符串为 ""。
示例 3：

输入: s = "zadb"

输出: "db"

解释:

从字符串中移除 "za"，剩下 "db"。
无法进行进一步操作。因此，所有可能移除操作后的最终字符串为 "db"。

提示:

1 <= s.length <= 10^5
s 仅由小写英文字母组成。

模拟

class Solution {
public:
    string resultingString(string s) {
        string ans;
        for(char x:s){
            if(ans.size()>0){
                char y=ans.back();
                int d=max(x,y)-min(x,y);
                if(d==1||d==25){ 
                    ans.pop_back();
                    continue;
                }
            }
            ans.push_back(x);
        }
        return ans;
    }
};

3. 折扣价交易股票的最大利润

给你一个整数 n，表示公司中员工的数量。每位员工都分配了一个从 1 到 n 的唯一 ID ，其中员工 1 是 CEO。另给你两个下标从 1 开始的整数数组 present 和 future，两个数组的长度均为 n，具体定义如下：
present[i] 表示第 i 位员工今天可以购买股票的当前价格。
future[i] 表示第 i 位员工明天可以卖出股票的预期价格。
公司的层级关系由二维整数数组 hierarchy 表示，其中 hierarchy[i] = [ui, vi] 表示员工 ui 是员工 vi 的直属上司。

此外，再给你一个整数 budget，表示可用于投资的总预算。

公司有一项折扣政策：如果某位员工的直属上司购买了自己的股票，那么该员工可以以半价购买自己的股票（即 floor(present[v] / 2)）。

请返回在不超过给定预算的情况下可以获得的最大利润。

注意：

每只股票最多只能购买一次。
不能使用股票未来的收益来增加投资预算，购买只能依赖于 budget。

哦，不会

4. 移除相邻字符后字典序最小的字符串

给你一个由小写英文字母组成的字符串 s。

你可以进行以下操作任意次（包括零次）：

移除字符串中任意一对相邻字符，这两个字符在字母表中是连续的，无论顺序如何（例如，'a' 和 'b'，或者 'b' 和 'a'）。
将剩余字符左移以填补空隙。
返回经过最优操作后可以获得的字典序最小的字符串。

当且仅当在第一个不同的位置上，字符串 a 的字母在字母表中出现的位置早于字符串 b 的字母，则认为字符串 a 的字典序小于字符串 b，。
如果 min(a.length, b.length) 个字符都相同，则较短的字符串字典序更小。

注意：字母表被视为循环的，因此 'a' 和 'z' 也视为连续。

示例 1：

输入： s = "abc"

输出： "a"

解释：

从字符串中移除 "bc"，剩下 "a"。
无法进行更多操作。因此，经过所有可能的移除后，字典序最小的字符串是 "a"。
示例 2：

输入： s = "bcda"

输出： ""

解释：

从字符串中移除 "cd"，剩下 "ba"。
从字符串中移除 "ba"，剩下 ""。
无法进行更多操作。因此，经过所有可能的移除后，字典序最小的字符串是 ""。
示例 3：

输入： s = "zdce"

输出： "zdce"

解释：

从字符串中移除 "dc"，剩下 "ze"。
无法对 "ze" 进行更多操作。
然而，由于 "zdce" 的字典序小于 "ze"。因此，经过所有可能的移除后，字典序最小的字符串是 "zdce"。

提示：

1 <= s.length <= 250
s 仅由小写英文字母组成。

解题思路：这道题和第二道题在题意上类似，区间DP

class Solution {
public:
    string s;
    int n;
    vector<vector<string>> memo;
    vector<vector<bool>> vis;
    vector<vector<int>> emp; 
    bool es(int l, int r) {
        if (l > r) return true;      
        if (emp[l][r] != -1) {
            return emp[l][r] == 1;
        }
        bool res = false;
        for (int k = l + 1; k <= r; ++k) {
            char c1 =s[l];
            char c2 = s[k];
            bool c = false;
            if (abs(c1 - c2) == 1) {
                c = true;
            } else if ((c1 == 'a' && c2 == 'z') || (c1 == 'z' && c2 == 'a')) {
                c = true;
            }
            if (!c) continue;
            bool me = (k == l + 1) ? true : es(l + 1, k - 1);
            if (!me) continue;
            bool se = (k == r) ? true : es(k + 1, r);
            if (se) {
                res = true;
                break;
            }
        }
        emp[l][r] = res ? 1 : 0;
        return res;
    }
    string dfs(int l, int r) {
        if (l > r) return "";               
        if (vis[l][r]) return memo[l][r];
        string b = s.substr(l, 1) + dfs(l + 1, r);
        for (int k = l + 1; k <= r; ++k) {
            char c1 = s[l];
            char c2 = s[k];
            bool c = false;
            if (abs(c1 - c2) == 1) {
                c = true;
            } else if ((c1 == 'a' && c2 == 'z') || (c1 == 'z' && c2 == 'a')) {
                c = true;
            }
            if (!c) continue;
            bool me = (k == l + 1) ? true : es(l + 1, k - 1);
            if (!me) continue;
            string z = dfs(k + 1, r);
            if (z < b) {
                b = z;
            }
        }
        vis[l][r] = true;
        memo[l][r] = b;
        return b;
    }
public:
    string lexicographicallySmallestString(string s) {
        this->s=s;
        n = s.size();
        if (n == 0) return "";
        memo.resize(n, vector<string>(n, ""));
        vis.resize(n, vector<bool>(n, false));
        emp.resize(n, vector<int>(n, -1)); 
        return dfs(0, n - 1);
    }
};