wordpress附件页面,随州抖音seo收费标准,优化绿松石是什么意思,海南省建设网站首页大家好#xff0c;欢迎来到无限大的频道。
今日继续给大家带来力扣题解。
题目描述#xff08;中等#xff09;#xff1a;
从字符串中移除星号
给你一个包含若干星号 * 的字符串 s 。
在一步操作中#xff0c;你可以#xff1a; 选中 s 中的一个星号。 移除星号…大家好欢迎来到无限大的频道。
今日继续给大家带来力扣题解。
题目描述中等
从字符串中移除星号
给你一个包含若干星号 * 的字符串 s 。
在一步操作中你可以 选中 s 中的一个星号。 移除星号 左侧 最近的那个 非星号 字符并移除该星号自身。
返回移除 所有 星号之后的字符串。
注意 生成的输入保证总是可以执行题面中描述的操作。 可以证明结果字符串是唯一的。
解题思路 我看到这个题思路就是直接抽象题目要求的就是字符串当中的星号和非星号区分开来每当遇到一个星号时移除前面最近的一个字符。这种行为可以被抽象为一个栈的操作当遇到字符时将其压入栈中当遇到星号时从栈中弹出一个字符。作为一个中等题来说多少有些简单了 使用栈结构我们可以使用一个栈来存储字符串中的字符。栈的顶端代表最近添加的字符。 遍历字符串遍历给定的字符串 s 如果遇到一个普通字符非星号将其压入栈中。 如果遇到一个星号*则从栈中弹出一个字符如果栈不为空。 重建字符串遍历完字符串后栈中剩下的字符就是移除星号后所需的字符串。将这些字符复制回原始字符串 s 中并在末尾添加字符串结束符 \0。 释放内存最后释放用于存储栈的动态分配内存。 参考代码
char* removeStars(char* s) {char* stack malloc(strlen(s) 1);int top -1;for(int i 0;s[i] ! \0; i){if (s[i] ! *){stack[top] s[i];}else{if (top ! -1){top--;}}}for (int i 0; i top; i){s[i] stack[i];}s[top 1] \0;free(stack);return s;
} 时间复杂度 遍历字符串字符串的长度为 n我们需要遍历每个字符一次因此这一部分的时间复杂度为 O(n)。 重建字符串在遍历完字符串后我们还需要将栈中的字符复制回字符串中这也是 O(n) 的操作。
综上所述整体时间复杂度为 O(n)。 空间复杂度 栈的使用我们使用了一个与输入字符串长度相同的栈来存储字符最坏情况下没有星号的情况下栈的大小可以达到 n。 额外的空间除了栈之外算法没有使用其他显著的额外空间。
因此空间复杂度为 O(n)。
