LeetCode5377. 將二進制表示減到 1 的步驟數

文章目錄

• LeetCode5377. 將二進制表示減到 1 的步驟數
• • 題目描述
  • 解題思路
  • AC代碼

題目描述

給你一個以二進制形式表示的數字 s 。請你返回按下述規(guī)則將其減少到 1 所需要的步驟數：

• 如果當前數字為偶數，則將其除以 2 。
• 如果當前數字為奇數，則將其加上 1 。

題目保證你總是可以按上述規(guī)則將測試用例變?yōu)?1 。

示例 1：

輸入：s = “1101”
輸出：6
解釋：“1101” 表示十進制數 13 。
Step 1) 13 是奇數，加 1 得到 14
Step 2) 14 是偶數，除 2 得到 7
Step 3) 7 是奇數，加 1 得到 8
Step 4) 8 是偶數，除 2 得到 4
Step 5) 4 是偶數，除 2 得到 2
Step 6) 2 是偶數，除 2 得到 1

示例 2：

輸入：s = “10”
輸出：1
解釋：“10” 表示十進制數 2 。
Step 1) 2 是偶數，除 2 得到 1

示例 3：

輸入：s = “1”
輸出：0

提示：

• 1 <= s.length <= 500
• s 由字符 ‘0’ 或 ‘1’ 組成。
• s[0] == ‘1’

解題思路

此題來源于 LeetCode第183場周賽，題目難度是 Medium，大約80%的參賽用戶都成功通過了此題。

一看到題目就給人一種熟悉的感覺，似乎以前見過這個題。周賽結束后我去百度上搜索了這個題，各大 OJ里是有這個題的。這個題的來源是數學的角谷定理（原來叫角谷猜想，后來已經被成功證明了）。

所謂角谷猜想，是指對于任意一個正整數，如果是奇數，則乘3加1，如果是偶數，則除以2，得到的結果再按照上述規(guī)則重復處理，最終總能夠得到1。例如，假定初始整數為5，計算過程分別為16、8、4、2、1。

這里 LeetCode官方對題目進行了一些更改，題目原本是整數的運算，這里改成了二進制+字符串的形式。同時將難度調低了一些，奇數時僅進行加1運算。

看到題目第一個想到的就是二進制轉為十進制，然后進行運算。瞅了一眼題目提示，s.length<=500，轉換出來的數據太大了，直接放棄了這一想法。

然后想到的是針對字符串進行按位處理。對于偶數來說，直接舍去后面的‘0’字符即可；對于奇數來說，加1就涉及到進位的問題，如果每一位都是1則全部要進位，處理起來很麻煩。

仔細思考了一會后覺得可以用按位翻轉的思想進行模擬。最后一位是1，加1之后就變成0，同時進位；如果倒數第二位也是1，加上進位的1也變成0，再進位。這就相當于將每一位上的1翻轉為0，層層向上翻轉，遇到第一個0將其翻轉為1即完成了整個進位過程。

對于用例“11111”來說，全部翻轉為0之后前面應該還有個1才能保證值不變，因此我想到在字符串前面添加一個‘0’用來解決這種情況，“011111”翻轉之后變成“100000”，偶數處理一步一步舍去“0”，剩下為“1”，這樣保證了一定有一個“0”來完成進位過程。

這里有一個特殊情況：“10”。對于“10”來說舍去“0”已經變成“1”了，只需要處理一次就行。我的方法在前面添加“0”之后變成“010”，偶數舍去最后一位“0”后還剩“01”，這個時候對“01”進行特判輸出即可。

因此輸出條件有兩個：

• 字符串處理后僅為“1”
• 字符串處理后為“01”

AC代碼

代碼采用 Java語言進行書寫。

這里采用 StringBuilder而不用String是為了節(jié)省內存空間，因為對 String的操作是每次新生成一個 String對象，然后將引用更改到這個對象上。StringBuilder是只創(chuàng)建一個對象，所有的操作都針對的是對象本身。

這里對 “1” 進行特判主要是省內存，當然也可以不用特判，因為 “1” 最終也會轉換為 “01” 進行判斷的。

class Solution {public int numSteps(String s) {int len=s.length();if(len==1){return 0;}else{int num=0;StringBuilder str=new StringBuilder("0");str.append(s);while(true){len=str.length();if(len==1||(len==2&&str.charAt(0)=='0'&&str.charAt(1)=='1')){break;}else{if(str.charAt(len-1)=='1'){for(int i=len-1;i>=0;i--){if(str.charAt(i)=='0'){str.setCharAt(i,'1');num++;break;}else{str.setCharAt(i,'0');}}}else{str.deleteCharAt(len-1);num++;}}}return num;}} }

本來我是想用 StringBuilder的 equals方法直接比較相等的，結果運行起來總是報錯，百度后才發(fā)現原來 StringBuilder是沒有 equals方法的。

因為這次的相等只判斷兩個數位，所以就直接寫了一個樸素版的判斷。

len == 2 && str.charAt(0) == ‘0’ && str.charAt(1) == ‘1’

周賽結束后馬上提交了測評看看數據，很 nice。

總結

以上是生活随笔為你收集整理的LeetCode5377. 将二进制表示减到1的步骤数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。