Hacks


  • 5

    Ruby:

    def find_contest_match(n)
      a = (1..n).map(&:to_s)
      a.map! { |x| "(#{x},#{a.pop})" } while a.size > 1
      a[0]
    end
    

    Python:

    def findContestMatch(self, n):
        a = range(1, n+1)
        while len(a) > 1:
            a = zip(a, a[:len(a)/2-1:-1])
        return str(a[0]).replace(' ', '')

  • 0
    Z

    @StefanPochmann I like this hack!
    By the way my solution seems very slow, what do you think is the bottleneck?

    class Solution(object):
        def findContestMatch(self, n):
            def helper(m):
                if len(m) == 2:
                    return "(%s,%s)" % tuple(m)
                return helper([helper((m[i], m[~i])) for i in xrange(len(m)/2)])
            return helper(map(str, range(1, n + 1)))

  • 0

    @zhongyuan9817 said in Hacks:

    my solution seems very slow

    What makes you think so?


  • 0
    Z

    @StefanPochmann I copied your solution, run it 3 times, average 44, mine average 80. So I just wonder where slow it down.


  • 1

    @zhongyuan9817 Looks like it's both the "(%s,%s)" % tuple(m) and the fact that you call your helper all the time for every single pair. That's a lot of function calls.

    I did some local testing, as that's much easier and more reliable.

    Mine:

    >>> from timeit import timeit
    >>> timeit(lambda: [Solution().findContestMatch(2 << i) for i in range(12)], number=1000)
    3.5428014015090166
    

    Yours:

    >>> timeit(lambda: [Solution().findContestMatch(2 << i) for i in range(12)], number=1000)
    5.033923284778492
    

    The below:

    >>> timeit(lambda: [Solution().findContestMatch(2 << i) for i in range(12)], number=1000)
    2.6449636687542295
    

    Code:

    def findContestMatch(self, n):
        def helper(m):
            if len(m) == 1:
                return m[0]
            return helper(['(' + m[i] + ',' + m[~i] + ')' for i in xrange(len(m)/2)])
        return helper(map(str, range(1, n + 1)))
    

    Though without the double usage, the helper/recursion doesn't make sense. A while loop is simpler:

    def findContestMatch(self, n):
        a = map(str, range(1, n + 1))
        while n > 1:
            n /= 2
            a = ['(' + a[i] + ',' + a[~i] + ')' for i in xrange(n)]
        return a[0]
    

    Same speed:

    >>> timeit(lambda: [Solution().findContestMatch(2 << i) for i in range(12)], number=1000)
    2.6232860104196902
    

  • 1
    K

    @StefanPochmann

    Java solution using two linked lists:

    public String findContestMatch(int n) {
            LinkedList<String> list = new LinkedList<>();
            for (int i = 1; i <= n; i ++) {
                list.add(String.valueOf(i));
            }
            
            LinkedList<String> tmp = new LinkedList<>();
            while (list.size() != 1) {
                while (list.size() >= 2) {
                    tmp.add(String.format("(%s,%s)", list.removeFirst(), list.removeLast()));
                }
                list.addAll(tmp);
                tmp.clear();
            }
            
            return list.getFirst();
        }
    

Log in to reply
 

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