昨日回顾
昨天作为这个系列的第一篇文章，分别介绍了Java与Python的以下内容：
- 整数类型与考点
- 二进制与十进制的转换
- 与、或、异或的操作
- 位移操作
以上内容，如果遗忘了，一定要定时复习啊...今天是整数的第二篇文章，会和大家稍有跳跃分享一道简单题+一道中等题目，用来对二进制算法完成进一步的巩固。
每道题涉及的知识点会在题目分析中给出整理。让我们开始吧！
剑指OfferII002.二进制加法
https://leetcode-cn.com/problems/JFETK5/solution/shua-chuan-jian-zhi-offer-day02-zheng-sh-obx6/
难度：简单
题目
给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。
输入为 非空 字符串且只包含数字 1 和 0。
提示：
- 每个字符串仅由字符 '0' 或 '1' 组成。
- 1 <= a.length, b.length <= 10^4
- 字符串如果不是 "0" ，就都不含前导零。
示例
示例 1:
输入: a = "11", b = "10"
输出: "101"
示例 2:
输入: a = "1010", b = "1011"
输出: "10101"
分析
正如昨天提到的，在做整数题目时，Python与Java的差别是什么呢？
- Python： 放心大胆无脑冲！
- Java：在越界的边缘战战兢兢。
所以很多时候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:]
可如果在面试中这样写，那真是一首凉凉送给你。 但这毕竟是一道简单题目，作为今天的开胃菜，并没有太大的难度。
对于这道题，我们只需要牢记以下三点即可：
- 逢二进一是二进制的法则
- 进位的这个一，我们需要找个变量才存储它，才能在下一次的循环中获取
- 对于不等长的字符串，我们需要进行适当的优化与判断
解题
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();
}
}
作为开胃菜的第一道题，就到这里，如此的难度，能否唤起你重拳出击的气势，那么继续看下一道题吧！
剑指OfferII004.只出现一次的数字
https://leetcode-cn.com/problems/WGki4K/solution/shua-chuan-jian-zhi-offer-day02-zheng-sh-tlce/
难度：中等
题目
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。
请你找出并返回那个只出现了一次的元素。
提示：
- 1 <= nums.length <= 3 * 10 ^ 4
- -2 ^ 31 <= nums[i] <= 2 ^ 31 - 1
- nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例
示例 1：
输入：nums = [2,2,3,2]
输出：3
示例 2：
输入：nums = [0,1,0,1,0,1,100]
输出：100
分析
如果考虑进阶中说到的不使用额外空间，那这道题真的是一道很简单的题目了。我们可以通过以下两种方法实现：
-
哈希表
- 创建一个哈希表
- 循环数组，将每个元素挨个加入哈希表中
- 遍历哈希表中的数据，查找哪个数字只出现了一次返回。
-
集合+数学
- 既然数组中只有一个数出现1次，其他的都出现三次，那么我们先创建一个集合
- 将数组加入集合s中，保持每个数字的唯一性
- 然后分别求sum(nums)、sum(s)
- 将sum(s) * 3 - sum(nums)会得到什么结果，是否为多那个只出现一次数字所缺失的两倍数字
- 然后将上一步的结果除以2，就得到了最终的结果。
以上两种方式，均可以计算出结果，但是都因为开辟了额外空间而不满足进阶的要求。那么，进阶该如何操作呢？
这里先简单介绍下力扣136题，只出现一次的数字。
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
遇到这道题同样上面的两个方法可以使用，但通过昨天的学习，我们应该第一时间想到异或操作，相同的二进制异或为0。
那么将数组挨个异或后的结果，不就是那个数字了么？
理解了这个思路，再看当前这道题目。这里我们有三个相同的数字，没办法通过异或操作完成判断，那如何换一种思路实现呢？
让我们看看下面这张图吧：
如果我们可以将所有的数字都转化为二进制，然后根据每一位对3其余，最终不就是我们要的结果吗？
最方便的是我们创建一个32位长度的数组，然后针对每个数字的二进制位对该数组对应下标进行累加，最终计算结果。
这里存在一个空间复杂度的计算规则，跟时间复杂度类似，如果是常数的空间申请，是可以忽略为O(1)的。
但为了严格按照题目要求，我们通过左位移配合二进制加法来实现累加操作，具体如图：
- 初始ret = 0
- 循环32位二进制位数i
- 计算循环数组该i位之和对3求余
- 若余数为1，则 ret |= 1 << i即可
- 最终返回ret即可
这里要注意下由于Python是无符号位的二进制，所以需要对最高位进行判断。
若为1则表示负数，需要对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;
}
}
欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
我的个人博客：https://qingfengpython.cn
