NC 560 题解 | #打字#

题意分析

• 依次打出一个字符串，其中字符<表示将前一个字符删除，问最后打出的字符串是什么？

思路分析

• 一个很简单的模拟题目，我们可以明显的看出需要使用栈的思想来进行解决。我们首先需要了解什么是栈？栈是一种先进后出的数据结构。如下图

• 其实利用栈的原因是我们可以在O(1)的情况下取到上一个字符。所以我们大致的思路就是先将所有的字符按照顺序依次放进栈里面，如果遇到<字符的话。我们就将栈顶的元素拿出去，直到为空。最后，将栈里面的字符依次取出来，然后进行反转就能得到最终的答案了。

• 由于本题的思路比较单一，这里我用了两种语言实现。

写法一 C++

• C++很好进行实现，由于有现成的STL，这里，我用的是vector向量模拟的栈。
• 代码如下
  • 需要对字符串执行遍历的操作，出栈的操作是$O\left(1\right)O(1)$O(1),时间复杂度为$O\left(n\right)O(n)$O(n)
  • 过程中利用了vecotr模拟栈，空间复杂度为$O\left(n\right)O(n)$O(n)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string Typing(string s) {
        // write code here
        vector<char>  v;
        // 循环遍历整个字符串
        for(auto x:s){
            // 如果是回退
            if(x=='<'){
                // 先要判断当前是否还有可以回退的字符串
                if(v.size()) v.pop_back();
            }else{
                v.push_back(x);
            }
        }
        string ans="";
        // 遍历一遍得到最终的字符串
        for(auto x:v){
            ans+=x;
        }
        
        return ans;
    }
};

写法二 Go

• 如果用Go实现栈的话是比较复杂的。所以这里对于删除的操作，我是利用重新构建一个新的字符串，删除原字符串的最后一个字符然后返回这个新的字符串的方式进行处理。
• 代码如下
  • 遍历字符串需要$O\left(n\right)O(n)$O(n)，然后执行删除的操作也是$O\left(n\right)O(n)$O(n)的，所以最坏的时间复杂度为$O\left(n^2\right)O(n^2)$O(n2)
  • 过程中在删除上一个字符的过程中需要开一个新的字符串进行存储，所以空间复杂度是$O\left(n\right)O(n)$O(n)

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @return string字符串
*/
// 定义一个函数最后一个字符串的函数
func del(s string) string {
    t := ""
    // 只需要遍历前len(s)-1个字符即可
    for i := 0; i < len(s)-1; i++ {
        t += string(s[i])
    }
    return t
}
func Typing( s string ) string {
    // write code here
    a := ""
    // 循环遍历字符串进行处理
    for i := 0; i < len(s); i ++ {
        if s[i] == '<' {
            a = del(a)
        }else{
            a += string(s[i])
        }
    }
    
    return a
}