Why is it that sometimes on LeetCode, Run Code is correct and Submit prompts Wrong Answer?

Read this article and you’ll know it’s not a Bug in LeetCode.

Hello everyone, I am “negative Xueming Candle”, a programmer who has written 1000 LeetCode algorithm solutions for 7 years. Welcome to follow.

The interview will be a series of algorithm questions in writing —

  1. Interview algorithmic questions — prefix and
  2. Interview will be the algorithm problem — add

Why does a test case, in “execute code” result is correct, but in “commit” run error?

Once upon a time in

Talking about this subject, I can’t help recalling the past.

The first time I encountered this problem was when I started to brush LeetCode at the beginning of my sophomore year (there was no Chinese version of LeetCode yet). At that time, my main language was Java. I wrote the Code on the local compiler Eclipse and pasted it into the Code box of LeetCode. Then “Submit”.

In anticipation of a green Accept!

A few seconds later, I was stunned, I saw the red Wrong Answer!

At that time was a new entry of the small white, completely can not understand why the error, still think is LeetCode Bug πŸ˜‚

At that time, I was the only one among my classmates who was swiping questions, and there was no wechat group communication, so I had to figure it out by myself. It took me a while to find the answer online — it had something to do with LeetCode’s evaluation mechanism.

repetition

Here I will reproduce the scene on the Chinese button.

Just like this, LeetCode number 1: Sum of two numbers.

If my code looks like this, notice the location defined by Visited:

unordered_map<int.int> visited;
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(a); ++i) {if (visited.count(target - nums[i])) {
                return {visited[target - nums[i]], i};
            }
            visited[nums[i]] = i;
        }
        return{}; }};Copy the code

The default test cases are:

,7,11,15 [2]

9

Click “Execute code” — OK, no problem, output is as expected.

​

Click “submit” – there is a “solution error”!

​

The test cases that went wrong were:

[3, 3]

6

But goose, I see my code should be no problem. So I put the test case in the test case execution box, click “Execute code”, and the result is [0, 1]! The result is the same as expected!

What’s going on here? Is there a Bug in the force buckle?

why

In fact, it is not a Bug, but we do not have the evaluation mechanism of understanding button.

After reading your code, likey’s test machine initializes the class once for each test case, but you need to manually initialize global and in-class static variables.

You can think of the evaluation process as follows:

unordered_map<int.int> visited;
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // Your code}};int main(a) {
    string line;
    while (getline(cin, line)) {
        // Read the input NUMs
        vector<int> nums = stringToIntegerVector(line);
        // Read the input target
        getline(cin, line);
        int target = stringToInteger(line);
        
        // Instantiate Solution() one at a time and execute its twoSum method
        vector<int> ret = Solution().twoSum(nums, target);
		
        // Output the result
        string out = integerVectorToString(ret);
        cout << out << endl;
    }
    return 0;
}
Copy the code

See?

  • For each test case, the link instantiates oneSolution()And execute ittwoSummethods
  • If thevisitedIn the classSolutionAs a “global variable”, it is shared with all test cases.Therefore, the results of the previous test case will affect the next test case, resulting in a “solution error.”
  • Putting the “answer error” test cases in the “Test Case” box and running them again gives the correct result because only one test case is run and does not interfere with each other.

The correct approach

To avoid interference with “global variables” or “static in-class variables” between test cases, we have two approaches:

  1. Recommended practice: Do not use “global variables” or “static variables in a class”;
  2. Perform an initialization on a “global variable” or “static variable in a class” within a class/function.

For example, we move visited’s position inside the class/function to avoid “global variables”.

class Solution {
private:
    / / class
    unordered_map<int.int> visited;
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        / / function
        // unordered_map<int, int> visited;
        for (int i = 0; i < nums.size(a); ++i) {if (visited.count(target - nums[i])) {
                return {visited[target - nums[i]], i};
            }
            visited[nums[i]] = i;
        }
        return{}; }};Copy the code

Or initialize Visited within a function, such as visiting.clear() in the twoSum() method.

unordered_map<int.int> visited;
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        visited.clear(a);for (int i = 0; i < nums.size(a); ++i) {if (visited.count(target - nums[i])) {
                return {visited[target - nums[i]], i};
            }
            visited[nums[i]] = i;
        }
        return{}; }};Copy the code

In the above formulation, I most recommend writing the visited variable within twoSum.

Why is that?

This is consistent with the principle of minimum scope.

The principle of minimum scope means that each variable is defined to be visible only to the smallest code segment that needs to see it.

This avoids a lot of unexpected mistakes.

conclusion

Avoid using “global variables” or “static variables in a class” as they may cause different “test cases” to interfere with each other and lead to “wrong answers”.

Variables should be defined according to the “principle of minimum scope” to avoid many unexpected errors.

After understanding the evaluation mechanism of LeetCode (force buckle), we can brush the question not confused πŸ‘¨πŸ’»πŸ‘©πŸ’»

Reference:

  1. Support.leetcode-cn.com/hc/kb/artic…
  2. www.ituring.com.cn/article/216…