时间戳

首页 > 解决方案 > 我的一个测试用例没有通过 .Giving TLE for one case

java - 我的一个测试用例没有通过 .Giving TLE for one case

问题描述

问题陈述来自hackerrank。

名称：简单文本编辑器
描述：我使用了一个 stackNode.in stackNode 我使用了三个变量 top 用于先前执行的操作 operation is k 和 s 用于存储在先前操作中删除或附加的字符串。

链接到问题 ：https ://www.hackerrank.com/challenges/simple-text-editor/problem?isFullScreen=false

import java.io.*;
import java.util.*;
class StackNode
{
int top;
int operat;
String s;
}
public class Solution 
{
static String S="";
static Stack<StackNode> stack=new Stack<>();
public static void main(String[] args) 
{
    Scanner sc=new Scanner(System.in);
    int t=sc.nextInt();
    while(t-- >0)
    {
        int operation=sc.nextInt();
        if(operation == 1)
        {
            String st=sc.next();
            S=S+st;
            StackNode node=new StackNode();
            node.top=operation;
            node.s=st;
            stack.push(node);
        }
        else
        if(operation == 2)
        {
            int k=sc.nextInt();
            delete(k,operation);
        }
        else
        if(operation == 3)
        {
            int k=sc.nextInt();
            print(k);
        }
        else
        if(operation == 4)
           undo();
    }
}
static void delete(int k,int operation)
{
    StackNode node=new StackNode();
    node.top=operation;
    node.operat=k;
    if(S.length() < k)
    {
        node.s=S;
        S="";
        return;
    }
    else
    {
        node.s=S.substring(S.length()-k);
        S=S.substring(0,S.length()-k);
    }
    stack.push(node);
    }
    static void print(int k)
{
    if(k<=S.length())
       System.out.println(S.charAt(k-1));
}
static void undo()
{
    if(stack.isEmpty())
      return;
    StackNode node=stack.pop();
    if(node.top == 1)
    {
        S=S.substring(0,S.length()-node.s.length());
    }
    else
    if(node.top == 2)
    {
        S=S+node.s;
    }
   }
}

标签： javastringobjecttimestack

解决方案

问题：当字符串很长时，在每个追加和删除操作上复制整个编辑器内容需要很长时间。解决方案：而不是将编辑器内容保留在String使用 aStringBuffer或StringBuilder.

编辑器的内容可能多达一百万个字符。以下每个代码行都将此内容复制到一个新的String：

        S=S+st;

    S=S.substring(0,S.length()-k);

    S=S.substring(0,S.length()-node.s.length());

    S=S+node.s;

StringBuffer相反，当您从or追加或删除时StringBuilder，操作中未涉及的字符可以保留在原处。

其他可能的轻微优化：

  1. 在撤消堆栈上不存储附加的字符串，而只存储它的长度。该长度足以撤消附加操作。
  2. 使用switch语句来选择正确的操作，而不是链接 if-else。

就时间复杂度和空间复杂度而言，switch和chained if-else有什么区别吗

在大多数情况下，打开一个int值应该比链式 if-else 更快。

文档链接： StringBuilder

推荐阅读