Ако предпочитате бърза разходка през:

Като се има предвид двоичното представяне на цяло число като низ s, върнете броя стъпки, за да го намалите до1съгласно следните правила:

  • Ако текущото число е четно, трябва да го разделите на 2.
  • Ако текущото число е нечетно, трябва да добавите 1 към него.

Гарантирано е, че винаги можете да достигнете до един за всички тестови случаи.

Пример 1:

Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14. 
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.  
Step 5) 4 is even, divide by 2 and obtain 2. 
Step 6) 2 is even, divide by 2 and obtain 1.

Пример 2:

Input: s = "10"
Output: 1
Explanation: "10" corressponds to number 2 in their decimal representation.
Step 1) 2 is even, divide by 2 and obtain 1.

Пример 3:

Input: s = "1"
Output: 0

Ограничения:

  • 1 <= s.length <= 500
  • s се състои от знаци '0' или '1'
  • s[0] == '1'

Проблемна връзка: https://leetcode.com/problems/number-of-steps-to-reduce-a-number-in-binary-representation-to-one/

Интуицията

За да разрешим този въпрос, трябва да разберем, че последната цифра на всяко четно двоично число е 0, а последната цифра на всяко нечетно двоично число е 1.

За да разделим четно двоично число на 2, трябва само да отрежем последната цифра. Например 110 делено на 2 е 11, тъй като деленето на 2 означава минус едно от всяка степен на 2 в 2² + 2¹, което е 2¹ + 2⁰. Това е 11 в двоичното число.

За всяко нечетно двоично число добавянето на 1 го превръща в четно число с последната цифра 0, а „едно“ се пренася към предпоследната цифра. като 101 + 1 = 110. Ако няма предпоследна цифра, „единицата“ се пренася и ще доведе до нов бит. Като 1 + 1 = 10.

Пример

Да предположим, че ни е дадено двоичното число 1101 и искаме да го намалим до 1, ние не променяме оригиналното двоично число и вместо това използваме променлива „carry“, за да запишем пренесената цифра.

Започваме от последната цифра на двоичното число.
Тъй като е нечетно, първо добавяме единица към числото, а „1“ се пренася към предпоследната цифра. Сега числото е четно, разделяме го на 2, като го нарязваме на 110, с пренесена цифра 1. Това отнема 2 стъпки.

Сега числото все още е нечетно, добавяме 1 към него и го разделяме на 2, така че да имаме 11 с друга пренесена цифра 1. Това отнема 2 стъпки.

11 с пренесена цифра 1 е четно, така че разделянето на 2 означава нарязване на още една цифра, което води до 1, с пренесена цифра 1. Това отнема 1 стъпка.

Сега числото има само една цифра, пренасящата цифра ще доведе до още една цифра вляво и ще доведе до двоичния низ 10.

Знаем, че 10 е четно число, така че го разделяме на 2 и получаваме 1, което е последната ни стъпка.

Така че общо 6 стъпки.

Приближаване

Първо инициализираме променливата l да бъде с дължината на s-1. Променливите carry и count се инициализират на 0. Функцията влиза в цикъл while и чете s отдясно наляво и повтаря, когато l е по-голямо от 0.
Ако числото е четно и carry = 0, резултатът ще бъде четен и разделено на 2, така че увеличаваме count с 1 и задаваме carry на 0.
Ако числото е нечетно и carry = 1, резултатът ще бъде четен и разделен на 2, освен че трябва да пренесем цифра. Така че увеличаваме count с 1 и задаваме carry на 1.
Когато числото е четно и carry = 1, или когато числото е нечетно и carry = 0, и двата резултата ще бъдат нечетни. Така че добавяме едно към него, за да направим резултата четен и разделяме на 2. Това отнема две стъпки, така че увеличаваме count с 2 и задаваме carry на 1.
Цикълът while спира, когато достигнем първата цифра на дадено двоично число, което винаги е 1. След това проверяваме стойността на пренасянето. Ако е 1, това означава, че трябва да се добави пренесена цифра 1, което дава 10. Така че имаме нужда от още едно деление, за да стане 1, което е още една стъпка и увеличава count с 1.
Накрая , функцията връща броя стъпки, необходими за намаляване на двоичното число до 1.

class Solution:
    def numSteps(self, s):
        """
        :type s: str
        :rtype: int
        """
        l = len(s) - 1
        carry = 0
        count = 0
        while (l > 0):
            ##even number with carry = 0, result even
            if int(s[l]) + carry == 0:
                carry = 0
                count += 1
            ##odd number with carry = 1, result even
            elif int(s[l]) + carry == 2:
                carry = 1
                count += 1
            ##even number with carry = 1, result odd
            ##odd number with carry = 0, result odd
            else:
                carry = 1
                count += 2
            l -= 1
        #last digit 1 needs to add a carried over digit 1, which gives 10. 
        #So need one more divide to make it 1 (one more step)
        if carry == 1:
            count += 1
        return count

Следете нашия Youtube канал за нови актуализации:

https://www.youtube.com/@algo.monster

AlgoMonster се фокусира както върху ученето, така и върху практиката. Получавате всичко необходимо, за да се отличите на вашите технически интервюта: подробно въведение в ключовите модели на кодиране, примери и проблеми, представени в изключително визуална и интерактивна среда. Следете нашия уебсайт за повече информация:

https://algo.monster/