LeetCode同一Valid Tic-Tac-Toe代码提交运行时差异巨大原因咨询

问题描述 #

在LeetCode上解决Valid Tic-Tac-Toe问题时，多次提交完全相同的代码，运行时却波动极大，有时为0ms，有时为9ms、7ms或5ms。想知道这是什么原因，是否是代码结构存在问题（比如内存泄漏）？

附上的代码如下：

class Solution {

public:
        
    bool validTicTacToe(vector<string>& board) {
        
        int i,j,a[8]={0},b[8]={0};
        int o=0,x=0;
        string s="";
        
        for(i=0;i<3;i++)
        {
            for(j=0;j<3;j++)
            {
                if(board[i][j]=='X')
                {x++;
                 a[i]++;
                 a[j+3]++;
                if(i==j)
                    a[6]++;
                if(j==2-i)
                    a[7]++;
                }
                else if(board[i][j]=='O')
                {   o++;
                    b[i]++;
                    b[j+3]++;
                if(i==j)
                    b[6]++;
                if(j==2-i)
                    b[7]++;
                }
                
            }
        }
        
        for(i=0;i<8;i++)
        {
            if(a[i]==3)
            {s="a";
             break;
            }
             
            if(b[i]==3)
            {s="b";break;

            }
        }
        
        
        if(s=="" && o+x<9)
            s="p";
        else if(s=="")
            s="d";
        
        if(s=="d" && x!=5)
            return false;
        
        if(s=="b" && o!=x)
            return false;
        
        if(s=="a" && ((o+1)!=x))
            return false;
        
        
        if(s=="p")
        {
            if(o==x)
                return true;
            else if(x==o+1)
                return true;
            else
                return false;
        }
        
        return true;
    }
};

原因分析 #

首先可以明确：你的代码没有内存泄漏，运行时波动和代码结构无关，主要是LeetCode的评测环境导致的，具体原因包括：

• 服务器负载波动：LeetCode的评测服务器同时处理大量用户的提交请求，当服务器繁忙时，分配给你的代码的CPU时间片会被其他任务挤占，导致运行时变长；空闲时则能快速执行，出现0ms的情况。
• 计时精度与误差：LeetCode的运行时统计本身存在一定精度误差，尤其是当代码执行时间极短（比如小于1ms）时，会被显示为0ms，而实际执行时间可能在0-1ms之间波动，当系统调度有微小延迟时，就会被统计为5ms、7ms等数值。
• 编译器优化差异：虽然你提交的代码相同，但LeetCode的编译器可能会根据当前环境的不同，应用不同的优化策略，或者缓存的编译结果不同，也会导致运行时出现小幅波动。

你的代码逻辑清晰，使用的都是栈上变量（a、b数组，o、x等），没有动态分配内存，不存在内存泄漏问题。这类小规模算法题的运行时波动是正常现象，不需要过度担心。

内容的提问来源于stack exchange，提问作者Linico