当前位置：首页 > backend >正文

力扣第451场周赛

backend 2025/8/5 15:58:27

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);}
};