昨日回顾
昨天作为这个系列的第一篇文章，分别介绍了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; } }
