leetcode 224. Basic Calculator 很绝望的超时求助帖

刷题有一段时间了，做到第224道题，https://leetcode.com/problems/basic-calculator/，题目很有意思也很明确，实现简化版的内建的eval函数(没有*/，只有+,-,(,),space,数字)，无奈最后一个case超时了，贴上代码，向大家求助

1. class Solution {
   
2. public:
   
3.     long getNum(string s, int& idx)
   
4.     {
   
5.         long num =0;
   
6.         while(idx < s.length() && s[idx] >= '0' && s[idx] <= '9')
   
7.         {
   
8.             num = 10*num + (s[idx]-'0');
   
9.             idx++;
   
10.         }
    
11.         return num;
    
12.     }
    
13. 
    
14.     int calculate(string s, int& idx)
    
15.     {
    
16.         int val = 0;
    
17.         char pre = 0;
    
18.         long num = 0;
    
19. 
    
20.         while(idx < s.length())
    
21.         {
    
22.             char cur = s[idx];
    
23.             if(cur >= '0' && cur <= '9')
    
24.             {
    
25.                 num = getNum(s,idx);
    
26.                 val += (pre == '-')?(-1*num):num;
    
27.                 continue;
    
28.             }
    
29.             else if(cur == ' ');
    
30.             else if(cur == '+' || cur == '-') pre = cur;
    
31.             else if(cur == '(')
    
32.             {
    
33.                 int su = calculate(s,++idx);
    
34.                 val += (pre == '-')?-su:su;
    
35.             }
    
36.             else if(cur == ')') return val;
    
37. 
    
38.             idx++;
    
39.         }
    
40.         return val;
    
41.     }
    
42. 
    
43.     int calculate(string s)
    
44.     {
    
45.         int start = 0;
    
46.         return calculate(s,start);
    
47.     }
    
48. };

复制代码

中间确实有递归，但每个字符只扫描一次，所以时间复杂度是O(n)，应该没错，不知道还可以怎么优化才能过，先谢过各位大佬和看官了

你看一下那个测试数据，非常长。虽然递归的算法理论上是o(n)，但是函数的递归调用是很耗时的（如果你懂一点计算机理论的话）。
这题请不要用递归来做。事实上，你的递归思想，完全用一个栈的数据结构就可以手工实现，不会很麻烦。

把各个函数参数列表中的string s换成const string& s试试

现在的代码每调用一层calculate都会拷贝一次整个s字符串

谢谢大佬提醒，换成引用就过了。感谢感谢，我的疏忽

Runtime: 12 ms, faster than 99.39% of C++ online submissions for Basic Calculator.
Memory Usage: 10.1 MB, less than 100.00% of C++ online submissions for Basic Calculator.

wisdompeak2 发表于 2019-5-1 15:03
你看一下那个测试数据，非常长。虽然递归的算法理论上是o(n)，但是函数的递归调用是很耗时的（如果你懂一点 ...

是的，我会再用堆试下的，谢谢回复的两位大佬。五一快乐 哈哈