首页 > 试题广场 >

打字

[编程题]打字
  • 热度指数:6148 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
牛妹在练习打字,现在按照时间顺序给出牛妹按下的键(以字符串形式给出,'<'代表回退backspace,其余字符均是牛妹打的字符,字符只包含小写字母与'<'),牛妹想知道最后在屏幕上显示的文本内容是什么。若为空则返回一个空串。

在文本内容为空的时候也可以按回退backspace(在这种情况下没有任何效果)。

示例1

输入

"acv<"

输出

"ac"

说明

牛妹在打完"acv"之后按了回退,所以最后是"ac"

备注:
给定一个字符串s,代表牛妹所按下的按键。
class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string Typing(string s) {
        stack<char> S;
        string t = "";
        for(auto &c: s){
            if(c=='<'){
                if(!S.empty())
                    S.pop();
            }else
                S.push(c);
        }
        while(!S.empty()){
            t += S.top();
            S.pop();
        }
        for(int i=0,j=t.length()-1;i<j;i++,j--)
            swap(t[i], t[j]);
        return t;
    }
};

发表于 2020-06-28 11:22:53 回复(0)

我是菜鸡。目前java 66ms(勿喷)
题目是很简单,但我还是想在这里记录下为什么我没有使用Stack或者StringBuilder。

  1. 关于Stack,或许是这道题目的初衷,并且也是很好理解。但是在Java中,Stack是继承于Vector的,出栈与入栈会有加解锁,并且最后还得面临一个字符串反转的问题(StringBuilder.reverse)
  2. 关于StringBuilder,它提供了append与deleteCharAt,但是删除与添加会带来数组的扩容缩容性能损耗,虽然不大

结合实际情况看来,或许直接莽是最快速的实现方式:

    public String Typing (String s) {
        // write code here
        char[] tmp = new char[s.length()];
        int cur = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c != '<') {
                tmp[cur++] = c;
            } else {
                cur = cur > 0 ? cur - 1 : 0;
            }
        }
        return new String(tmp).substring(0, cur);
    }
发表于 2020-06-15 23:53:49 回复(1)
求大佬看看,我这个错在哪
发表于 2020-07-15 23:29:43 回复(1)
import java.util.*;

public class Solution {
    public String Typing (String s) {
        // 入栈
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '<') {
                if (!stack.empty()) {
                    stack.pop();
                }
                continue;
            }
            stack.push(c);
        }
        // 出栈
        String result = "";
        while (!stack.empty()) {
            result = stack.pop() + result;
        }
        return result;
    }
}

发表于 2021-11-15 14:25:33 回复(0)
func Typing(s string) string {

    nb := []byte{}
    b := []byte(s)
    for i := 0; i < len(b); i++ {
        if b[i] == 60 && len(nb) > 0 {
            nb = nb[:len(nb)-1]
        }else{
        nb=append(nb,b[i])}
    }
    nnb:=[]byte{}
    for _,v:=range nb{
        if v != 60{
            nnb=append(nnb,v)
        }
    }
    sb:=string(nnb)
    return sb
}
发表于 2021-06-04 21:39:26 回复(0)
public String Typing (String s) {
        // write code here
        char[] ch = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        for(char c:ch){
            if(c == '<'){
                if(sb.length()!=0){
                    sb.deleteCharAt(sb.length()-1);
                }
            }else{
                sb.append(c);
            }
        }
        return sb.toString();
    }

发表于 2021-02-22 11:15:58 回复(0)
class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string Typing(string s) {
        stack<char> st;
        for(int i = 0; i < s.size(); i++)
        {
            if(!st.empty() && s[i] == '<')
                st.pop();
            else if(s[i] != '<')
                st.push(s[i]);
        }
        char t[100000] = "\0";
        int len = st.size() - 1;
        while(len >= 0)
        {
            t[len--] = st.top();
            st.pop();
        }
        return t;
    }
};

发表于 2020-11-05 18:55:07 回复(0)
import java.util.*;
public class Solution {
    public String Typing (String s) {
        // write code here
        Stack st=new Stack();
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)!='<')
                st.push(s.charAt(i));
            else if(!st.isEmpty())
                st.pop();
        }
        StringBuffer ans =new StringBuffer();//由于String是不可变的,这里使用StringBuffer
        while(! st.isEmpty())
            ans.append(st.pop());//这个顺序应该是和答案反序的,使用reverse方法反序;
         return  new String(ans.reverse());
}}
发表于 2020-10-09 20:56:43 回复(0)
function Typing( s ) {
    // write code here
    let str = [];
    for (let i in s) {
        if (s[i] === '<') {
            str.pop();
        } else {
            str.push(s[i]);
        }
    }
    return str.join('')
}

发表于 2020-09-09 18:44:01 回复(0)
import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return string字符串
     */
    public String Typing (String s) {
        // write code here
        Stack<String> stack = new Stack<>();
        String[] str = s.split("");
        for (int i = 0; i< str.length;i++){
            if ("<".equals(str[i]) ){
                if (!stack.isEmpty()){
                    stack.pop();
                }
                continue;
            }
            stack.push(str[i]);
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()){
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }
}

发表于 2020-08-19 18:30:43 回复(0)
import java.util.*;


public class Solution {
  /**
   *
   * @param s string字符串
   * @return string字符串
   */
  public String Typing (String s) {
    if(s == null || s.length() == 0){
      return null;
    }

    Stack<Character> stack = new Stack<>();
    char[] chars = s.toCharArray();
    for(char ch : chars){
      if(ch != '<'){
        stack.push(ch);
      }else{
        if(!stack.isEmpty()){
          stack.pop();
        }
      }
    }

    StringBuilder str = new StringBuilder();
    while(!stack.isEmpty()){
      str.append(stack.pop());
    }

    return str.reverse().toString();
  }
}

发表于 2020-08-16 17:19:41 回复(1)
import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return string字符串
     */
    public String Typing (String s) {
        // write code here
        String str = "";
        char[] list = s.toCharArray();
        for(int i = 0;i<list.length;i++){
            if(list[i]=='<'){
                if(i>0){
                str = str.substring(0,i-1);
                continue;
                }
                else{
                    continue;
                }
            }
            str +=list[i];
        }
        return str;
    }
}
本地对于用例“<” 输出为空字符串,这样写有什么问题吗?用例的通过率很低
发表于 2020-08-05 21:53:24 回复(0)
function Typings ) {
    //1.切割以>符号的数组
    let strings = s.split("");
    let res = [];//模拟栈
    for (let i = 0i < strings.lengthi++) {

        const element = strings[i];
        //2.退格删除数组字母
        if(element!="<"){
            res.push(element);
        }else{
            res.pop();
        }
    }
    return res.join("");
}

发表于 2020-08-02 22:11:54 回复(0)
//感觉应该将所有情况都考虑了
string Typing(string s)
{
	string res;
	if (s.empty())
	{
		return res;
	}
	int len = s.length();
	deque<char>de;
	for (int i = 0; i < len; i++)
	{
		if (de.empty())
		{
			if (s[i]=='<')
			{
				continue;
			}
			else
			{
				de.push_back(s[i]);
			}
		}
		else
		{
			if (s[i]=='<')
			{
				de.pop_back();
			}
			else
			{
				de.push_back(s[i]);
			}
		}
	}
	while (!de.empty())
	{
		res.push_back(de.front());
		de.pop_front();
	}
	return res;
}

发表于 2020-08-02 20:23:31 回复(0)
不知道为什么错,在这里就只能通过28%
import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return string字符串
     */
    public String Typing (String s) {
        if(s==null || s.length()==0){
            return "";
        }
        if(s.equals("<")){
            return "";
        }
        
        int index;
        while((index=s.indexOf('<'))!=-1){
            if(s.charAt(0)=='<'){
                s = s.substring(1,s.length());
            }
          
            s = s.substring(0,index-1)+s.substring(index+1,s.length());
        }
        return s;
    }
}

发表于 2020-06-29 16:53:16 回复(0)
用栈模拟
# @param s string字符串 
# @return string字符串
#
class Solution:
    def Typing(self , s ):
        # write code here
        stack = []
        for c in s:
            if c!='<':
                stack.append(c)
            elif stack:
                stack.pop()
        return ''.join(stack)


发表于 2020-06-09 09:58:28 回复(0)
JAVA的要69ms,Go的只用5ms。我吐了。
 public String Typing (String s) {
        StringBuilder sb=new StringBuilder();
        int i=0;
        if(s.charAt(0)=='<'){
            i++;
            sb.append("");
        }
        while(i<=s.length()-1){
            if(s.charAt(i)=='<'){
                if(sb.length()>0)
                    sb.deleteCharAt(sb.length()-1);
                else
                    ;
            }
            else{
                sb.append(s.charAt(i));
            }
            i++;
        }
        return sb.toString();
    }
发表于 2020-06-08 23:49:42 回复(0)
class Solution:
    def Typing(self , s ):
        num = 0
        for char in s:
            if char == "<":
                num = num + 1;
        if num == 0:
            return s;
        for i in range(num):
            if s.index("<") == 0 or s.index("<") == 1:
                s = s[s.index("<")+1:];
            else:
                s = s[:s.index("<")-1] + s[s.index("<")+1:];
        return s;

编辑于 2020-06-08 00:47:35 回复(0)
import java.util.*;
public class Solution {
    /**
     *
     * @param s string字符串
     * @return string字符串
     */
    public String Typing (String s) {
        // write code here
        StringBuilder sb = new StringBuilder();//定义新的字符串
        for(int i=0;i<s.length();i++){//以字符的格式便利原来的字符串
            if(s.charAt(i)!='<'){//遇到的字符不是<就在新的字符串中添加原来的字符
                sb.append(s.charAt(i));
            }else{//遇到的字符是<且新的字符串长度大于1就删除新加字符串中前一个字符
                if(sb.length()>=1){//
                    sb.deleteCharAt(sb.length()-1);
                }
            }
        }
        return sb.toString();
    }
}
发表于 2020-06-03 10:39:28 回复(0)
public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return string字符串
     */
    public String Typing (String s) {
        // write code here
        char[] array = s.toCharArray();
        if(array.length == 0){
            return null;
        }
        
        LinkedList<Character> deque  = new LinkedList<>();

        for(Character ch : array){
            if(!ch.equals('<')){
                deque.push(ch);
            }else if(!(deque.size() == 0)){
                deque.pop();
            }
        }

        StringBuilder str = new StringBuilder();
        while(!(deque.size() == 0)){
            str.append(deque.pollLast());
        }
        
        return str.toString();
    }
}

发表于 2020-05-16 13:22:57 回复(0)