昨日回顧
昨天作為這個系列的第一篇文章痹升，分別介紹了Java與Python的以下內(nèi)容：
- 整數(shù)類型與考點
- 二進制與十進制的轉(zhuǎn)換
- 與了袁、或贷屎、異或的操作
- 位移操作
以上內(nèi)容舀奶，如果遺忘了，一定要定時復(fù)習(xí)啊...今天是整數(shù)的第二篇文章仗扬，會和大家稍有跳躍分享一道簡單題+一道中等題目症概，用來對二進制算法完成進一步的鞏固。
每道題涉及的知識點會在題目分析中給出整理早芭。讓我們開始吧彼城！
劍指OfferII002.二進制加法
https://leetcode-cn.com/problems/JFETK5/solution/shua-chuan-jian-zhi-offer-day02-zheng-sh-obx6/
難度：簡單
題目
給定兩個 01 字符串 a 和 b ，請計算它們的和退个，并以二進制字符串的形式輸出募壕。
輸入為 非空 字符串且只包含數(shù)字 1 和 0。
提示：
- 每個字符串僅由字符 '0' 或 '1' 組成帜乞。
- 1 <= a.length, b.length <= 10^4
- 字符串如果不是 "0" 司抱，就都不含前導(dǎo)零。
示例
示例 1:
輸入: a = "11", b = "10"
輸出: "101"
示例 2:
輸入: a = "1010", b = "1011"
輸出: "10101"
分析
正如昨天提到的黎烈，在做整數(shù)題目時习柠，Python與Java的差別是什么呢匀谣？
- Python： 放心大膽無腦沖！
- Java：在越界的邊緣戰(zhàn)戰(zhàn)兢兢资溃。
所以很多時候Python在刷題上簡直是作弊武翎，拿這道題來說，a溶锭、b的長度都為10 ^ 4宝恶，
在Java中是沒辦法表示的，對于Python只需要一行趴捅，簡直了：
class Solution:
def addBinary(self, a: str, b: str) -> str:
return bin(int(a, 2) + int(b, 2))[2:]
可如果在面試中這樣寫垫毙，那真是一首涼涼送給你。 但這畢竟是一道簡單題目拱绑，作為今天的開胃菜综芥，并沒有太大的難度。
對于這道題猎拨，我們只需要牢記以下三點即可：
- 逢二進一是二進制的法則
- 進位的這個一膀藐，我們需要找個變量才存儲它，才能在下一次的循環(huán)中獲取
- 對于不等長的字符串红省，我們需要進行適當?shù)膬?yōu)化與判斷
解題
Python
class Solution:
def addBinary(self, a: str, b: str) -> str:
ret, count = '', 0
i, j = len(a) - 1, len(b) - 1
while i >= 0 or j >= 0 or count:
if i >= 0:
count += ord(a[i]) - ord('0')
if j >= 0:
count += ord(b[j]) - ord('0')
ret += str(count % 2)
count //= 2
i, j = i - 1, j - 1
return ret[::-1]
Java
class Solution {
public String addBinary(String a, String b) {
StringBuilder ret = new StringBuilder();
int count = 0;
for (int i = a.length() - 1, j = b.length() - 1;
i >= 0 || j >= 0 || count > 0; i--, j--) {
int total = count;
total += i >= 0 ? a.charAt(i) - '0' : 0;
total += j >= 0 ? b.charAt(j) - '0' : 0;
count = total > 1 ? 1 : 0;
ret.append(total - count * 2);
}
return ret.reverse().toString();
}
}
作為開胃菜的第一道題额各，就到這里，如此的難度吧恃，能否喚起你重拳出擊的氣勢虾啦，那么繼續(xù)看下一道題吧！
劍指OfferII004.只出現(xiàn)一次的數(shù)字
https://leetcode-cn.com/problems/WGki4K/solution/shua-chuan-jian-zhi-offer-day02-zheng-sh-tlce/
難度：中等
題目
給你一個整數(shù)數(shù)組 nums 蚜枢，除某個元素僅出現(xiàn) 一次 外缸逃，其余每個元素都恰出現(xiàn) 三次 针饥。
請你找出并返回那個只出現(xiàn)了一次的元素厂抽。
提示：
- 1 <= nums.length <= 3 * 10 ^ 4
- -2 ^ 31 <= nums[i] <= 2 ^ 31 - 1
- nums 中，除某個元素僅出現(xiàn) 一次 外丁眼，其余每個元素都恰出現(xiàn) 三次
進階：你的算法應(yīng)該具有線性時間復(fù)雜度筷凤。 你可以不使用額外空間來實現(xiàn)嗎？
示例
示例 1：
輸入：nums = [2,2,3,2]
輸出：3
示例 2：
輸入：nums = [0,1,0,1,0,1,100]
輸出：100
分析
如果考慮進階中說到的不使用額外空間苞七，那這道題真的是一道很簡單的題目了藐守。我們可以通過以下兩種方法實現(xiàn)：
-
哈希表
- 創(chuàng)建一個哈希表
- 循環(huán)數(shù)組，將每個元素挨個加入哈希表中
- 遍歷哈希表中的數(shù)據(jù)蹂风，查找哪個數(shù)字只出現(xiàn)了一次返回卢厂。
-
集合+數(shù)學(xué)
- 既然數(shù)組中只有一個數(shù)出現(xiàn)1次，其他的都出現(xiàn)三次惠啄，那么我們先創(chuàng)建一個集合
- 將數(shù)組加入集合s中慎恒，保持每個數(shù)字的唯一性
- 然后分別求sum(nums)任内、sum(s)
- 將sum(s) * 3 - sum(nums)會得到什么結(jié)果，是否為多那個只出現(xiàn)一次數(shù)字所缺失的兩倍數(shù)字
- 然后將上一步的結(jié)果除以2融柬，就得到了最終的結(jié)果死嗦。
以上兩種方式，均可以計算出結(jié)果粒氧，但是都因為開辟了額外空間而不滿足進階的要求越除。那么，進階該如何操作呢外盯？
這里先簡單介紹下力扣136題摘盆，只出現(xiàn)一次的數(shù)字。
給定一個非空整數(shù)數(shù)組饱苟，除了某個元素只出現(xiàn)一次以外骡澈，其余每個元素均出現(xiàn)兩次。找出那個只出現(xiàn)了一次的元素掷空。
遇到這道題同樣上面的兩個方法可以使用肋殴，但通過昨天的學(xué)習(xí)，我們應(yīng)該第一時間想到異或操作坦弟，相同的二進制異或為0护锤。
那么將數(shù)組挨個異或后的結(jié)果，不就是那個數(shù)字了么酿傍？
理解了這個思路烙懦，再看當前這道題目。這里我們有三個相同的數(shù)字赤炒，沒辦法通過異或操作完成判斷氯析，那如何換一種思路實現(xiàn)呢？
讓我們看看下面這張圖吧：
如果我們可以將所有的數(shù)字都轉(zhuǎn)化為二進制莺褒，然后根據(jù)每一位對3其余掩缓，最終不就是我們要的結(jié)果嗎？
最方便的是我們創(chuàng)建一個32位長度的數(shù)組遵岩，然后針對每個數(shù)字的二進制位對該數(shù)組對應(yīng)下標進行累加你辣，最終計算結(jié)果。
這里存在一個空間復(fù)雜度的計算規(guī)則尘执，跟時間復(fù)雜度類似舍哄，如果是常數(shù)的空間申請，是可以忽略為O(1)的誊锭。
但為了嚴格按照題目要求表悬，我們通過左位移配合二進制加法來實現(xiàn)累加操作，具體如圖：
- 初始ret = 0
- 循環(huán)32位二進制位數(shù)i
- 計算循環(huán)數(shù)組該i位之和對3求余
- 若余數(shù)為1丧靡，則 ret |= 1 << i即可
- 最終返回ret即可
這里要注意下由于Python是無符號位的二進制蟆沫，所以需要對最高位進行判斷叉讥。
若為1則表示負數(shù)，需要對ret進行減等操作饥追。
解題
Python
class Solution:
def singleNumber(self, nums) -> int:
ret = 0
for i in range(32):
cnt = 0
for num in nums:
cnt += num >> i & 1
if cnt % 3:
if i == 31:
ret -= (1 << i)
else:
ret |= 1 << i
return ret
Java
class Solution {
public int singleNumber(int[] nums) {
int ret = 0;
for (int i = 0; i < 32; i++) {
int cnt = 0;
for (int num : nums) {
cnt += num >> i & 1;
}
if (cnt % 3 != 0) {
ret |= 1 << i;
}
}
return ret;
}
}
歡迎關(guān)注我的公眾號: 清風(fēng)Python图仓，帶你每日學(xué)習(xí)Python算法刷題的同時，了解更多python小知識但绕。
我的個人博客：https://qingfengpython.cn
