Ако предпочитате бърза разходка през:
Като се има предвид двоичното представяне на цяло число като низ 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 се фокусира както върху ученето, така и върху практиката. Получавате всичко необходимо, за да се отличите на вашите технически интервюта: подробно въведение в ключовите модели на кодиране, примери и проблеми, представени в изключително визуална и интерактивна среда. Следете нашия уебсайт за повече информация: