Leetcode 1404. Number of Steps to Reduce a Number in Binary Representation to One (python)

题目

解法1：

一板一眼的按照二进制来做

class Solution:
    def numSteps(self, s: str) -> int:
        def divide(s):
            return s[:-1]
        
        def add(s):
            carry = 1
            ans = ''
            for c in reversed(s):
                val = carry + int(c)
                remain = val%2
                ans = str(remain) + ans
                carry = val//2
            if carry:
                ans = str(carry) + ans
            return ans
        #print(divide('1110'))
        count = 0
        #for _ in range(7):
        while s!='1':
            if s[-1] == '0':
                s = divide(s)
            else:
                s = add(s)
            #print(s)
            count += 1
        return count

解法2：

直接转成十进制来做

class Solution:
    def numSteps(self, s: str) -> int:
        count = 0
        n = int(s, 2)
        while n > 1:
            if n % 2 == 1:
                count += 2
                n = (n+1)//2
            else:
                count +=1 
                n = n//2
        return count