Python 35ms with list and dictionary


  • 0
    Y
    class Solution(object):
        def integerReplacement(self, n):
            """
            :type n: int
            :rtype: int
            """
            stack = []
            dic = {}
            
            stack.append(n)
            dic[n] = 0
            
            while stack.__len__() > 0:
                cur = stack.pop()
                while cur > 1:
                    if cur % 2 == 0:
                        if (cur/2 in dic) and (dic[cur] + 1 >= dic[cur/2]):
                            break
                        dic[cur/2] = dic[cur] + 1
                        cur = cur / 2
                    else:
                        if not (cur+1 in stack):
                            stack.append(cur+1)
                            dic[cur+1] = dic[cur] + 1
                        if (cur-1 in dic) and (dic[cur] + 1 >= dic[cur-1]):
                            break
                        dic[cur-1] = dic[cur] + 1
                        cur = cur - 1
            return dic[1]
    

Log in to reply
 

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