遂宁网站建设,东莞seo关键词排名优化排名,网络营销推广方法选择,个人简历 网站开发题目
力扣第2390. 从字符串中移除星号
中等
给你一个包含若干星号 * 的字符串 s 。
在一步操作中#xff0c;你可以#xff1a;
选中 s 中的一个星号。移除星号 左侧 最近的那个 非星号 字符#xff0c;并移除该星号自身。
返回移除 所有 星号之后的字符串。
注意你可以
选中 s 中的一个星号。移除星号 左侧 最近的那个 非星号 字符并移除该星号自身。
返回移除 所有 星号之后的字符串。
注意
生成的输入保证总是可以执行题面中描述的操作。可以证明结果字符串是唯一的。 示例 1
输入s leet**cod*e
输出lecoe
解释从左到右执行移除操作
- 距离第 1 个星号最近的字符是 leet**cod*e 中的 t s 变为 lee*cod*e 。
- 距离第 2 个星号最近的字符是 lee*cod*e 中的 e s 变为 lecod*e 。
- 距离第 3 个星号最近的字符是 lecod*e 中的 d s 变为 lecoe 。
不存在其他星号返回 lecoe 。
示例 2
输入s erase*****
输出
解释整个字符串都会被移除所以返回空字符串。提示
1 s.length 105s 由小写英文字母和星号 * 组成s 可以执行上述操作
思路和解题方法一不行超内存 首先创建一个栈st用于存储非星号字符。然后遍历字符串s中的每个字符 如果当前字符是星号*并且栈st不为空则将栈顶的元素弹出表示移除星号左侧最近的非星号字符。如果当前字符不是星号则将其入栈st。创建一个空字符串result用于存储最终结果。最后从栈底到栈顶依次弹出字符将每个字符拼接到result的前面。返回result作为最终的结果字符串。 这段代码使用了栈的特性通过判断当前字符是否是星号以及栈是否为空来实现移除星号左侧最近的非星号字符的操作。最后将栈中剩余的字符拼接成结果字符串返回。 复杂度 时间复杂度: O(n) 其中n是字符串的长度。在遍历过程中每个字符最多入栈和出栈一次因此栈的操作总体上可以看作是线性时间复杂度的。所以总的时间复杂度为O(n)。 空间复杂度 O(n) 算法使用了一个栈来存储非星号字符栈的大小最坏情况下可能与输入字符串的长度相同。 c 代码 class Solution {
public:std::string removeStars(string s) {stackchar st; // 创建一个栈用于存储非星号字符for (char c : s) { // 遍历字符串s中的每个字符if (c * !st.empty()) { // 如果当前字符是星号且栈不为空则将栈顶元素弹出表示移除星号左侧最近的非星号字符st.pop();} else if (c ! *) { // 如果当前字符不是星号则将其入栈st.push(c);}}string result; // 创建一个空字符串用于存储最终结果while (!st.empty()) { // 从栈底到栈顶依次弹出字符将每个字符拼接到result的前面result st.top() result;st.pop();}return result; // 返回最终结果字符串}
}; 思路和解题方法二
首先我们定义了两个指针i和j。i是慢指针指向当前要处理的字符j是快指针用于遍历字符串。同时我们也记录了字符串的长度n
int n s.length(); int i 0;
// 慢指针指向当前要处理的字符 int j 0; // 快指针用于遍历字符串
接下来我们开始遍历字符串。对于每一个字符如果它是星号我们需要移除星号左侧最近的非星号字符。我们可以通过将慢指针i往前移动来找到最近的非星号字符直到遇到一个非星号字符或者到达字符串开头。注意我们需要判断i是否大于0以避免数组越界错误。然后我们将慢指针i再往前移动一位即移除了最近的非星号字符
if (s[j] *) {// 找到星号时移除星号左侧最近的非星号字符while (i 0 s[i-1] *) {i--;}if (i 0) {i--; // 移除非星号字符}
}如果当前字符不是星号我们将其放到当前慢指针i的位置并同时移动慢指针i和快指针j
else {// 非星号字符将其放到当前慢指针的位置s[i] s[j];i;
}
j;
最后我们返回从字符串开头到慢指针i的子串即移除了所有星号之后的字符串。注意这里需要使用substr函数获取子串其第一个参数是子串的起始位置第二个参数是子串的长度
return s.substr(0, i);
复杂度 时间复杂度: O(n) 时间复杂度是O(n)其中n是输入字符串的长度。因为我们需要遍历整个字符串一次来处理每个字符。 空间复杂度 O(1) 空间复杂度是O(1)因为我们只使用了常数个变量来保存指针和临时变量没有使用额外的数据结构。 c 双指针 代码 class Solution {
public:std::string removeStars(string s) {stackchar st; // 创建一个栈用于存储非星号字符for (char c : s) { // 遍历字符串s中的每个字符if (c * !st.empty()) { // 如果当前字符是星号且栈不为空则将栈顶元素弹出表示移除星号左侧最近的非星号字符st.pop();} else if (c ! *) { // 如果当前字符不是星号则将其入栈st.push(c);}}string result; // 创建一个空字符串用于存储最终结果while (!st.empty()) { // 从栈底到栈顶依次弹出字符将每个字符拼接到result的前面result st.top() result;st.pop();}return result; // 返回最终结果字符串}
}; 觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
