Codility支架挑战性能问题

尝试一个简单的编码挑战（检查一串{}字符是否合格）我已经陷入了困境，因为我的解决方案的性能得分很差，甚至超过了一些他们的测试用例。Codility支架挑战性能问题

，规格为“返回1，如果很好地形成。否则为0”：

class Solution { 
public int solution(String S) { 

    Deque<String> stack = new LinkedList<String>(); 
    while (S.length() > 0) { 
     String firstChar = S.substring(0, 1); 
     if (isOpenBracket(firstChar)) { 
      stack.addFirst(firstChar); 
     } 
     else { 
      String matchingOpen = closedToOpen(firstChar); 
      if (matchingOpen == null) return 0; 

      String topOfStack = stack.pollFirst(); 
      if (!matchingOpen.equals(topOfStack)) { 
       return 0; 
      } 
     } 
     S = S.substring(1); 
    } 
    return stack.isEmpty() ? 1 : 0; 
} 

public boolean isOpenBracket(String s) { 
    return ("{".equals(s) || "[".equals(s) || "(".equals(s)); 
} 

public String closedToOpen(String closed) { 
    if ("}".equals(closed)) return "{"; 
    if ("]".equals(closed)) return "["; 
    if (")".equals(closed)) return "("; 
    return null; 
} 
}

起初我以为的罪魁祸首是addfirst仅/ pollFirst实际上附加在链表的尽头，但是这不是该案例（改变添加/ pollLast实际上产生相同的分数配置文件）。

我可以看到，使用字符，而不是字符串将加快东西，但我不认为它太不够有关超时测试（预计时间< 3秒，运行时间> 8秒）...

我最后的猜测是辅助方法会在每次调用时重新分配常量...但这仍然是如此大的影响？

任何想法？

来源

2015-03-02 Diego Martinoia

子串会让你活着吃 – jn1kk 2015-03-02 15:03:37

摆脱子串的调用。 – IVlad 2015-03-02 15:04:38

他们那么糟糕？如果我只是采取charAt，那么它仍然会像砖块一样缓慢？ – 2015-03-02 15:05:22

问题是调用长度为n的字符串的子字符串的成本为O(n)，因为它会生成副本。不要一直复制字符串，而是要保留一个字符串并访问每个字符。

来源

2015-03-02 15:06:41 btilly

明白了。这很明显，当你想到它。我知道当我只有3个小时的睡眠时，我应该停止做这些事情^^。干杯。 – 2015-03-02 15:10:06

Codility支架挑战性能问题

回答

相关问题