Interesting 6ms Solution with C++ template


  • 0
    P

    I've submitted many. The running times range from 6 ms to 33 ms. Anyway,,,,,,,,

    #include<climits>
    #include<iostream>
    #define TEN 10
    
    
    template<unsigned N>
    struct ten_power {
        enum {value = TEN * ten_power<N-1>::value};
    };
    
    
    template<>
    struct ten_power<0> {
        enum {value=1};
    };
    
    
    template<int S>
    struct ten_power_has_over_flow {
        enum{value=(INT_MAX/ten_power<S-1>::value)<TEN};
    };
    
    
    template<int S, bool B>
    struct int_max_digit {
        enum {
            value = int_max_digit<S+1, ten_power_has_over_flow<S>::value>::value
        };
    };
    
    
    template<int S>
    struct int_max_digit<S, true> {
        enum {value=S-1};
    };
    
    
    const int INT_MAX_DIGIT = int_max_digit<1, false>::value;
    const unsigned FLAG_NO_THIS_DIGIT = TEN+1;
    const unsigned INT_MAX_REVERSE_TAIL = INT_MAX / 10;
    
    template<unsigned N>
    struct digit_value {
        constexpr inline static unsigned of(const unsigned & x) {
            return (x>=ten_power<N-1>::value)?((x%ten_power<N>::value) / ten_power<N-1>::value):FLAG_NO_THIS_DIGIT;
        }
         
    };
    
    template<>
    struct digit_value<INT_MAX_DIGIT> {
        constexpr inline static unsigned of(const unsigned & x) {
            return (x>=ten_power<INT_MAX_DIGIT-1>::value)?(x / ten_power<INT_MAX_DIGIT-1>::value):FLAG_NO_THIS_DIGIT;
        }
    };
    
    const unsigned INT_MAX_LAST_DIGIT = digit_value<1>::of(INT_MAX);
    const bool NEED_CMP_MAX_DIGIT = digit_value<INT_MAX_DIGIT>::of(INT_MAX) > INT_MAX_LAST_DIGIT;
    
    
    template<bool B>
    struct reverse_at_int_max_digit {
        inline static unsigned call(const unsigned & reversed, const unsigned & quotient,
                            const unsigned & last_quotient) {
            return (reversed<=INT_MAX_REVERSE_TAIL)?(reversed*TEN+last_quotient):0;
        }
    };
    
    
    template<>
    struct reverse_at_int_max_digit<true> {
        inline static unsigned call(const unsigned & reversed, const unsigned & quotient,
                            const unsigned & last_quotient) {
            return ((last_quotient<=INT_MAX_LAST_DIGIT)&&(reversed<=INT_MAX_REVERSE_TAIL))?(reversed*TEN+last_quotient):0;
        }
    };
    
    
    
    template<unsigned N>
    struct reverse_at_n{
        inline static unsigned call(const unsigned & reversed, const unsigned & quotient,
                            const unsigned & last_quotient) {
            unsigned this_digit = last_quotient - TEN * quotient;
            unsigned new_reversed = reversed * TEN + this_digit;
            return quotient?(reverse_at_n<N+1>::call(new_reversed,quotient/10,quotient)):new_reversed;
        }
    };
    
    template<>
    struct reverse_at_n<INT_MAX_DIGIT> {
        inline static unsigned call(const unsigned & reversed, const unsigned & quotient,
                            const unsigned & last_quotient) {
            return reverse_at_int_max_digit<NEED_CMP_MAX_DIGIT>::call(reversed,quotient,last_quotient);
        }
    };
    
    
    
    
    class Solution {
    public:
        int reverse(const int & x) {
            if (x>=0){
                unsigned u_x = x;
                unsigned result = reverse_at_n<1>::call(0,u_x/10,u_x);
                return static_cast<int>(result);
            } else {
                if (x==INT_MIN){
                    return 0;
                }else{
                    return -reverse(-x);
                }
            }
        }
    
    };
    
    

Log in to reply
 

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