Python solution is Time Out


  • 0
    M

    Someone can help why this got Time Out:

    class Solution:
        # @param n, an integer
        # @return an integer
        def climbStairs(self, n):
            f = []
            f.append(1)
            f.append(1)
            for i in range(2, n + 1):
                f.append(f[i - 1] + f[i - 2])
                
            return f[n]
    

    Same algorithm but a bit different in implementation is AC:

    class Solution:
        # @param n, an integer
        # @return an integer
        def climbStairs(self, n):
            f = [0] * (n + 1)
            f[0] = 1
            f[1] = 1
            for i in range(2, n + 1):
                f[i] = f[i - 1] + f[i - 2]
                
            return f[n]

  • 0
    S

    Time Out means the server is very busy, you may need to re-submit it.

    Time Limit Exceed indicates your algorithm is not efficient enough.

    Sorry for making this misunderstanding.


  • 0
    C
    class Solution:
    def climbStairs(self, n):
        if n<=2:
            return n
        pre1=2
        pre2=1
        for i in range(3,n+1):
            current=pre1+pre2
            pre2=pre1
            pre1=current
        return current

  • 0
    S
    This post is deleted!

  • 0
    S
        o(log n) solution
    
    int multiply( int mat1[2][2], int mat2[2][2] )
    {
    	int i, j, k, l;
    	i = mat1[0][0] * mat2[0][0] + mat1[0][1] * mat2[1][0];
    	j = mat1[0][0] * mat2[0][1] + mat1[0][1] * mat2[1][1];
    	k = mat1[1][0] * mat2[0][0] + mat1[1][1] * mat2[1][0];
    	l = mat1[1][0] * mat2[0][1] + mat1[1][1] * mat2[1][1];
    	
    	mat1[0][0] = i;
    	mat1[0][1] = j;
    	mat1[1][0] = k;
    	mat1[1][1] = l;
    	return 0;
    }
    
    int power( int F[2][2], int n )
    {
    	if( n <= 1 )
    		return 0;
    	power( F, n/2 );
    	multiply( F, F );
    	if( n % 2 == 1 )
    	{
    		int M[2][2] = { {1, 1},{1, 0} };
    		multiply( F, M );
    	}
    	return 0;
    }
    
    int noOfWays( int n )
    {
    	if( n <= 1 )
    		return 0;
    	int F[2][2] = { {1, 1},{1, 0} };
    	power( F, n );
    	return F[0][0];
    }
    
    
    class Solution {
    public:
        int climbStairs(int n) {
           if( n == 0 || n ==1 )
           return n;
           else
           return noOfWays(n);
             
        }
    };

Log in to reply
 

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