First O(1) submission on this topic, 0ms


  • 0
    0
    class Solution {
    public:
        static char d[100000];
        static int v[100001];
        static bool did;
    
        Solution() {
            if (did) return;
            int value = 0, write = 0, read = 0;
            bool one = true;
            while (write < 100000) {
                d[write] = one ? value++, '1' : '2';
                v[++write] = value;
    
                if (d[read++] == '2') {
                    d[write] = one ? value++, '1' : '2';
                    v[++write] = value;
                }
                one = !one;
            }
            did = true;
        }
    
        int magicalString(int n) {
            return v[n];
        }
    };
    
    char Solution::d[100000] = {'1','2','2','1','1'};
    int Solution::v[100001] = {0};
    bool Solution::did = false;

  • 0
    J

    Bro, It's boring. If you really want to do it, at least you should use C++ 14 constexpr constructor or template trick.


  • 0
    0

    @jimzuolin talk is cheap, show me the code!


  • 0
    J

    @0xFFFFFFFF I mean no offense.
    Option 1 C++ 14, works under clang++ -std=14 flag, failed in LeetCode C++ 11 compiler, could be better with static nested class.

    class Solution {
    public:
        char d[100000];
        int v[100001];
    
        constexpr Solution() : d(), v() {
            int value = 0, write = 0, read = 0;
            bool one = true;
            while (write < 100000) {
                d[write] = one ? value++, '1' : '2';
                v[++write] = value;
    
                if (d[read++] == '2') {
                    d[write] = one ? value++, '1' : '2';
                    v[++write] = value;
                }
                one = !one;
            }
        }
    
        int magicalString(int n) {
            return v[n];
        }
    };
    

    C++ 11 template solution, I could just give you a possible way, it could be really complex. I don't have much motivation to do it since people already have C++ 14 constexpr constructor.

    The code below I wrote is about generating an array during compiler time, try it out, then try to modify it, afters days of torment, hopefully you will make it work and admit C++ is broken somehow +_+.

    #include <array>
    #include <iostream>
    
    template<typename T>
    struct TplArray {
    
        template<T... ITEMS>
        struct ArrayHolder {
            static const std::array<T, sizeof...(ITEMS)> data;
        };
    
        template<size_t SIZE, template<size_t> class FUNCTOR, T... ITEMS>
        struct Maker {
            typedef typename Maker<SIZE - 1, FUNCTOR, FUNCTOR<SIZE - 1>::value, ITEMS...>::tunnel tunnel;
        };
    
        template<template<size_t> class FUNCTOR, T... ITEMS>
        struct Maker<0, FUNCTOR, ITEMS...> {
            typedef ArrayHolder<ITEMS...> tunnel;
        };
    };
    
    template<typename T>
    template<T... ITEMS>
    const std::array<T, sizeof...(ITEMS)> TplArray<T>::ArrayHolder<ITEMS...>::data = {ITEMS...};
    // --- impl over
    
    template<size_t IDX>
    struct Functor {
        constexpr static int value = IDX + 1;
    };
    
    int main() {
        typedef TplArray<int>::Maker<10, Functor>::tunnel tunnel;
        for (auto i = tunnel::data.cbegin(); i != tunnel::data.cend(); ++i) {
            std::cout << *i << std::endl;
        }
    }
    

  • 0
    0

    @jimzuolin

    Thanks for your code. two issues.

    1. about your constexpr version. there is no improvements when test case calls like following code, your constexpr version will still calc twice. but static version is only one time calculation.
    int main() {
        cout << Solution().magicalString(100) << endl;
        cout << Solution().magicalString(100) << endl;
        return 0;
    }
    
    1. I did think about template version but it is kind of "hard-coded" (like template version of Fibonacci numbers). you can not submit your code to leetcode to accept run time input.

  • 0
    J

    @0xFFFFFFFF
    Improved Version, guaranteed to calc during compiler time,

    class Hepler {
      public:
        char d[100000];
        int v[100001];
        constexpr Hepler() : d(), v() {
            int value = 0, write = 0, read = 0;
            bool one = true;
            while (write < 100000) {
                d[write] = one ? value++, '1' : '2';
                v[++write] = value;
    
                if (d[read++] == '2') {
                    d[write] = one ? value++, '1' : '2';
                    v[++write] = value;
                }
                one = !one;
            }
        }
    };
    
    class Solution {
        static constexpr Hepler hepler{};
    
      public:
        int magicalString(int n) const { return Solution::hepler.v[n]; }
    };
    

    I think it's best now.
    YES! It does. I just check out the LLVM IR, works like charm! Just few lines of mov ops.


Log in to reply
 

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