My c code with 0ms ~ 4ms, why got different speed?


  • 0
    T

    I have a question is that why speed is not always the same?

    My idea is scan once or almost twice (from head to tail and if need from tail to somewhere again.)
    Please see my code and give some advice. If need more explian, please let me know.

    comp :O(n)
    space:O(1)

    int longestValidParentheses(char* s)

    {
        int lvp = 0, lvp1 = 0, l = 0, r = 0, complete = 0;
        int i, len = strlen(s);
    
        for (i = 0; i < len; ++i)
        {
        	if (s[i] == '(')
        	{
        		++l;
        	}
        	else if (s[i] == ')')
        	{
        		++r;
        	}
    
     		if (l == r)
    		{
    			if (complete == 0)
    			{
    				lvp1 += r;
    			}
    			else
    			{
    				lvp1 = r;
    			}
    
    		    l = 0;
    			r = 0;
    			lvp = (lvp > lvp1 ? lvp : lvp1);
    			complete = 0;
    		}
    		else if (l < r)// too much right bracket(s). but the only possible is l == 0 && r == 1.
    		{
    			// no need to update lvp1 and lvp.
    			r = 0;
    			lvp1 = 0;
    			complete = -1;
    		}
    		else if (l > r && i == len - 1)
    		{
    			lvp1 = reverse_lvp(s, l + r);
    			lvp = (lvp > lvp1 ? lvp : lvp1);
    		}
        }
    
    	lvp *= 2;
    
        return lvp;
    }
    

    // and

    int reverse_lvp(char *s, int len_to_deal)

    {
    	int rev_lvp = 0, lvp1 = 0, l = 0, r = 0, complete = 0;
    	int i, len = strlen(s);
    
    	for (i = 1; i <= len_to_deal; ++i)
    	{
    		if (s[len - i] == ')')
        	{
        		++l;
        	}
        	else if (s[len - i] == '(')
        	{
        		++r;
        	}
    
        	if (l == r)
    		{
    			if (complete == 0)
    			{
    				lvp1 += r;
    			}
    			else
    			{
    				lvp1 = r;
    			}
    
    		    l = 0;
    			r = 0;
    			rev_lvp = (rev_lvp > lvp1 ? rev_lvp : lvp1);
    			complete = 0;
    		}
    		else if (l < r)// too much right bracket(s). but the only possible is l == 0 && r == 1.
    		{
    			// no need to update lvp1 and rev_lvp.
    			r = 0;
    			lvp1 = 0;
    			complete = -1;
    		}
    	}
    
    	return rev_lvp;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.