我的解决方案如何比给定的示例解决方案慢？

Question

这是 2021 年 8 月 26 日的 Leet 代码问题。 我提交了几个解决方案，其中这个是最好的。然而，它花了 7 毫秒，当我看到示例 0 毫秒的解决方案时，我震惊地发现解决方案有多么复杂以及有多少条件检查。

---

问题（已编辑）

给定一串逗号分隔的值preorder,returntrue如果是二叉树的正确前序遍历序列化

保证字符串中每个逗号分隔的值必须是整数或表示空指针的字符'#'。

---

所以我在 discussion 中发布了这个：

我的解决方案（用了 7 毫秒）

class Solution
{
public:
    bool isValidSerialization(string preorder)
    {
        int c = 1;
        const int L = preorder.length();
        bool state = true;
        for (int i = 0; i < L; i++)
        {
            if (state)
            {
                state = false;
                if (!c)
                    return false;
                if (preorder[i] != '#')
                    c++;
                else
                    c--;
            }
            else
                state = preorder[i] == ',';
        }
        return !c;
    }
};

采样 0 毫秒解决方案

class Solution {
public:
    bool isValidSerialization(string pre) {
        stack<int> s;
        if(pre.length()==1 && pre[0]=='#'){
            return true;
        }
        string num = "";
        for(int i=0; i<pre.length(); i++){
            if(pre[i]==','){
                continue;
            }
            if(s.empty() && i>0){
                return false;
            }
            if(pre[i]=='#'){
                if(s.empty()){return false;}
                s.top()--;
                while(!s.empty() && s.top()==0){
                    s.pop();
                    if(!s.empty()){s.top()--;}
                    if(!s.empty() && s.top()<0){
                        return false;
                    }
                }
            }
            else{
                int j=i;
                while(j<pre.size() && pre[j]!=','){
                    j++;
                }
                i = j-1;
                s.push(2);
            }
            //cout << i << " -> " << s.size() << endl; 
        }
        if(s.size()>0){
            //cout << s.size() << endl;
            return false;
        }
        return true;
    }
};

当我的程序没有复杂的对象和较少的条件语句时，它是如何变慢的？

---

因为我没有希望在那里得到任何回应，所以我把它贴在这里。

Answer 1

Leetcode 可以 运行 在不同状态下的不同机器上使用不同的解决方案 - 因此即使提交相同的代码也会得到不同的结果。有时 +100ms，认为 C++ 时间的变化小于解释语言。编译器标志在常见问题解答中给出。 leetcode上关于时间测量不一致的讨论：one, two，你可以找到更多。